CODEWITHSUNDEEP
computational-geometryconvex-hull
tommsch
tommsch

Reputation: 688

Rough test if points are inside/outside of convex hull

I am working on an algorithm where I have to check whether points are inside or outside of the convex hull of some points. The problem is that

  1. I have to check this for a lot of points: ~2000,
  2. the point-cloud defining the convex hull has around 10000 points,
  3. the dimensions I am working in is quite high: 10-50.

The only possible positive thing for my points are, that for every point x, there is also -x, thus the points define a pointsymmetric polytope, and the convex hull is not degenerate (has non-empty interior).

Right now I am doing this with linear programming, for example as in https://stackoverflow.com/a/11731437/8052809

To speed up my program, I want to estimate whether a point is for sure inside or outside the convex hull, prior to computing it exactly. In other words, I need some fast algorithm which can determine for some points whether they are inside or not, resp. whether they are outside or not - and for some points, the fast algorithm can't decide it.

This I am doing right now by first looking at the bounding box of my pointcloud, and second, the approach in https://stackoverflow.com/a/4903615/8052809 - comment by yombo. But both methods can only determine if a point is for sure outside (and both methods are rather coarse).

Since most of the points I check are inside, I mostly need a test which determines if a point is for sure inside.

Long question short: I need an algorithm which can test very fast, whether a point is inside/outside the convex hull or not. The algorihm is allowed to report "inside", "no idea" and "outside".

Upvotes: 1

Views: 570

Answers (1)

Iddo Hanniel
Iddo Hanniel

Reputation: 2056

In order to quickly purge away points that are certified to be inside the convex hull you can reuse the points you found in your bounding box computation. Namely, the 2k points (of dimension k) containing the min and max value in every dimension.

You can construct a small (2k constraints) linear programming problem and purge away any point that is within the convex hull of these 2k points.

You can do this both for the query points and for the original point cloud, which will leave you with a smaller linear programming problem to solve for the remaining points.

Upvotes: 1

Related Questions