If we want
to check if a point lies inside a prescribed convex hull or not, then here you
are a method. I don’t know if this method was introduced before or not (but I'm sure in such a hightech world, it was introduced by someone)
Assumptions:
1. The convex hull
is described by the indices of points according to their connectivity order.
2. If point lies
on the edge or coincides with any vertex of the polygon’s vertices, then it is not going
to be considered inside the convex hull.
Algorithm:
Create vectors
from the point to all the vertices of the convex hull. For all vectors, compute
the cross product of the vector with the next vector according to points
connectivity. If all cross products have the same sign (positive or negative)
then the point is inside, else it’s outside or on edge. One great advantage of
this method that its low sensitivity to round off errors and the reduced accumulative
errors encountered in other methods. Consider the case of the triangle shown in
figure below and see directions of cross products and their signs.
The following table shows all possible cases for the signs of the cross products and what does each case mean
Signs
of cross products of successive vectors

Means
…

All are positive

Point is inside the
convex hull

All are negative

Point is inside the convex
hull

Some are positive,
some are negative

Point is outside the
convex hull

Some are positive,
some are zeros

Point is on edge, or
outside and collinear with an edge

Some are negative,
some are zeros

Point is on edge, or
outside and collinear with an edge

All are zeros

Convex hull
collapses to a single point
