Menu
What is the simplest way to test if a point P is inside a convex hull formed by a set of points X?
I'd like an algorithm that works in a high-dimensional space (say, up to 40 dimensions) that doesn't explicitly compute the convex hull itself. Any ideas?
558
For each of the edges, check whether your target point lies to the "left" of that edge. When doing this, treat the edges as vectors pointing counter-clockwise around the convex hull. If the target point is to the "left" of all of the vectors, then it is contained by the polygon; otherwise, it lies outside the polygon.
An extreme point of a convex set is a point in the set that does not lie on any open line segment between any other two points of the same set. For a convex hull, every extreme point must be part of the given set, because otherwise it cannot be formed as a convex combination of given points.
Iterate over all the points and find out the points, forming the convex polygon, that lies in between the start and endpoints in the counter-clockwise direction. Store these points in the vector. Check if the query point exists in the vector then the point lies outside the convex hull.
If a points (x, y) lie inside the polygon, it wont be in the convex hull and therefore won't be in the newly generated set of points of the convex hull. If points (x, y) lie outside the polygon, then they will be in the convex hull formed hence present in the set of points generated by the convex hull.
Set the bottom-left point as the start point and top-right point as the end point of the convex hull. Iterate over all the points and find out the points, forming the convex polygon, that lies in between the start and endpoints in the clockwise direction.
Below are some of the observations: Suppose the point (X, Y) is a point in the set of points of the convex polygon. If the Graham Scan Algorithm is used on this set of points, another set of points would be obtained, which makes up the Convex Hull.
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
x^T is the transpose of x [1] is the all-1 vector.The problem has a solution iff the point is in the convex hull.
155
The point lies outside of the convex hull of the other points if and only if the direction of all the vectors from it to those other points are on less than one half of a circle/sphere/hypersphere around it.
Here is a sketch for the situation of two points, a blue one inside the convex hull (green) and the red one outside:
For the red one, there exist bisections of the circle, such that the vectors from the point to the points on the convex hull intersect only one half of the circle. For the blue point, it is not possible to find such a bisection.
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
