Wednesday, September 21, 2011

Point inside convex hull test

Assume we want to check if a given point is inside a convex hull or not, we will do the following:
v  Divide the convex hull to triangles where all of these triangles have a common vertex which is arbitrarily chosen
v  Check if the point is inside one of the triangles. If the point is inside one of the triangles then it is inside the convex hull. Else if the point is not inside any triangle then it is out the convex hull.

The method used to detect if a point is inside a triangle looks like the following:
v  The prescribed triangle has three edges. For each edge create a triangle composed of the test point and an edge
v  Compute the area of the main triangle and the other three triangles. If the sum of areas of the constructed three triangles equals that area of the main triangle then the point is inside.

Note: I don’t know if this method is previously used or not, but what I know is that my mind gifted me this method.