Convex Hulls : Preliminaries

"Left Of" Queries

For points a, b, c, in the plane, the signed area of triangle abc is half the cross product (b-a)×(c-a).

signedArea[a_,b_,c_]:=((b[[1]]-a[[1]])(c[[2]]-a[[2]])-(b[[2]]-a[[2]])(c[[1]]-a[[1]]))/2

We can use this to define Boolean functions (i.e., functions that return true or false) to determine whether point c is to the left of directed segment ab or collinear to ab.

leftOf[a_,b_,c_]:=(signedArea[a,b,c] > 0)
leftOn[a_,b_,c_]:=(signedArea[a,b,c] >= 0)
collinear[a_,b_,c_]:=(signedArea[a,b,c]==0)

Try them out:

leftOf[{1,0},{2,2},{0,5}]

leftOn[{1,1},{2,2},{3,3}]

collinear[{1,2},{2,0},{3,-2}]

Caution: If we use floating-point input, we might sometimes get the wrong answer due to round-off error. For example:

collinear[{1.45,2},{2,0},{2.55,-2}]

Plotting random points

The following code generates n random points in a plane with coordinates between 0 and 10.

n=20;
pts=RandomReal[{0,10},{n,2}]

Here is how to plot points in Mathematica:

Graphics[{Blue,PointSize[0.02],Point[pts]},Frame->True]