1

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".

Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
tommsch
  • 582
  • 4
  • 19
  • Please clearly emphasize your question - it is not so easy to discern. – chux - Reinstate Monica May 31 '18 at 20:40
  • have you tried https://stackoverflow.com/questions/16750618/whats-an-efficient-way-to-find-if-a-point-lies-in-the-convex-hull-of-a-point-cl?noredirect=1&lq=1 ? – juvian May 31 '18 at 20:58
  • @juvian, this concerns 2D. I searched on stackoverflow a lot, and I am quite sure, that my question is indeed new. – tommsch May 31 '18 at 21:04
  • @tommsch the answer with bounty is for k dimentions:"`p` should be a `NxK` coordinates of `N` points in `K` dimensions' – juvian Jun 01 '18 at 01:50
  • @juvian thank you, I missed that one. But it does not help me either because the Delauny triangulation in high dimensions takes forever to compute. – tommsch Jun 01 '18 at 05:30
  • How do you obtain the initial convex hull ? –  Jun 05 '18 at 10:03
  • @meowgoesthedog: in what way can an octree help ??? This is a point containment test in 10-50 dimensions. –  Jun 05 '18 at 15:45
  • @YvesDaoust oh oops, i didn't notice the dimensionality; but the k-D tree is still generalizable – meowgoesthedog Jun 05 '18 at 15:49
  • @meowgoesthedog: haha, I expected such an answer. An octree is not a k-D tree and I also don't see how a k-D tree could help. The generalization of an octree is not thinkable: in dimension 50, a single node has 1125899906842624 pointers. –  Jun 05 '18 at 15:59
  • @YvesDaoust so you mean raycasting for a k-D tree of 2D/3D meshes cannot be generalized to N dimensions? – meowgoesthedog Jun 05 '18 at 16:10
  • @meowgoesthedog: I say that your suggestions are incomplete and incoherent. –  Jun 05 '18 at 16:59
  • @meowgoesthedog I think a k-d tree could work, the tree would give me be approximation of the interior of the polytope up to arbitrary precision. But I still don't know how I shall Coompute it. – tommsch Jun 06 '18 at 11:05

1 Answers1

1

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.

Iddo Hanniel
  • 1,636
  • 10
  • 18