Tuesday, April 24, 2012

Point inside convex hull detection

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 high-tech 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