Find if a point is inside a convex hull for a set of points without computing the hull itself

by

The problem can be solved by finding a feasible point of a Linear Program. If you’re interested in the full details, as opposed to just plugging an LP into an existing solver, I’d recommend reading Chapter 11.4 in Boyd and Vandenberghe’s excellent book on convex optimization.

Set A = (X[1] X[2] ... X[n]), that is, the first column is v1, the second v2, etc.

Solve the following LP problem,

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  \forall i

where

  1. x^T is the transpose of x
  2. [1] is the all-1 vector.

The problem has a solution iff the point is in the convex hull.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Algorithm to detect intersection of two rectangles?
  3. Sort points in clockwise order?
  4. How do I efficiently determine if a polygon is convex, non-convex or complex?
  5. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  6. How to Compute OBB of Multiple Curves?
  7. Largest circle inside a non-convex polygon
  8. How to check if line segment intersects a rectangle?
  9. Sort Four Points in Clockwise Order
  10. What is the most efficient algorithm to find a straight line that goes through most points?
  11. How can I create an internal spiral for a polygon?
  12. How do you find a point at a given perpendicular distance from a line?
  13. Compute the area of intersection between a circle and a triangle?
  14. Location of highest density on a sphere
  15. Circle line-segment collision detection algorithm?
  16. How do I calculate the area of a 2d polygon?
  17. Simple calculations for working with lat/lon and km distance?
  18. Finding whether a point lies inside a rectangle or not
  19. How do you calculate the average of a set of circular data? [closed]
  20. What is an Efficient algorithm to find Area of Overlapping Rectangles
  21. Millions of 3D points: How to find the 10 of them closest to a given point?
  22. Precise subpixel line drawing algorithm (rasterization algorithm)
  23. How to compare two shapes?
  24. Combined area of overlapping circles
  25. Calculate largest inscribed rectangle in a rotated rectangle
  26. What is the fastest way to find the closest point to a given point?
  27. Circular approximation of polygon (or its part)
  28. how do I create a line of arbitrary thickness using Bresenham?
  29. Distance from a point to a polygon
  30. Best algorithm for matching colours.

Leave a Comment