0

I need to calculate convex hull from a set of points.

Dimensions of points is usually 10 ~ 30D

Size of the set is small, usually 2 ~ 10

And the task I need is to judge whether a point is inside the convex hull constructed from the point set.

What are some algorithms to perform that, or are there any existing libraries that I could use？

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
Alaya
  • 3,287
  • 4
  • 27
  • 39
  • 4
    You don't need to construct the convex hull to see whether a point is inside it. Just solve a linear programming problem looking to see whether that point can be produced by taking a linear combination of the set of points, with all coefficients in the range [0,1] – mcdowella Aug 15 '16 at 05:04
  • While in two dimensions, the convex hull can be represented as a polygon and some [algorithms](https://en.wikipedia.org/wiki/Quickhull) are known for it, it is unclear to me how one would represent the convex hull in suitable data structures for higher dimensions; please clarify the desired representation. – Codor Aug 15 '16 at 06:51
  • mcdowella is right, in your case you want to avoid to compute the full convex hull (the time complexity grows exponentially with D). If you need to build the convex hull for other reasons, you can use [CGAL](http://doc.cgal.org/latest/Convex_hull_d/index.html). – geoalgo Aug 15 '16 at 09:03
  • It's worth noting that as the number of dimensions increase, most points will be in the convex hull, so for 30D, computing the convex hull is probably not that useful. – Filip Haglund Aug 15 '16 at 09:09
  • 1
    Possible duplicate of [Find if a point is inside a convex hull for a set of points without computing the hull itself](http://stackoverflow.com/questions/4901959/find-if-a-point-is-inside-a-convex-hull-for-a-set-of-points-without-computing-th) – Ami Tavory Aug 17 '16 at 14:53
  • 1
    @mcdowella trhe sum of coefficients must be 1. – n. m. could be an AI Aug 17 '16 at 15:58
  • @n.m. Yes, thanks - missed that. – mcdowella Aug 18 '16 at 04:08

1 Answers1

1

Note:this raw sketch of algorithm, it requires revision.It can output wrong result (see comments below)

The following is one of a number of possible solutions to your problem.

Let D - dimension of your space, N - count of your points. You can use following algorithm:

You should compute projection convex hull for each coordinate plane of your space. You will get D convex hulls. Complexity of this step is D * N * log N

Then you should test, whether each projection of you point is located inside each appropriated convex hull. Complexity of this step is D * N (using native algorithm)

Overall execution complexity = D * N * Log N.

Note: basic idea of this algorithm is to boil down computing convex hull on plane with following testing of location of point.

P.S. Of course, you can get some degenerate cases, where convex hull can be line segment or just point. But these cases can be easlity treated

P.P.S. This algorithm only allows to check whether point lies inside convex hull or on its boundary

Alex Aparin
  • 4,393
  • 5
  • 25
  • 51
  • It's true that the title asks about calculating the convex hull, but it's misleading - the question clarifies that only inclusion/exclusion is what's necessary. This can be done without calculating the convex hull itself. – Ami Tavory Aug 17 '16 at 14:54
  • I agree with you. But it will depend on his ways to solve problem. Of course, author may not compute convex hull to solve this task (using linear programming as above example). But I think my algorithm can be easily implemented. Note: it don't involve computing multidimensional convex hull. It uses auxiliary projection to test of location of point. – Alex Aparin Aug 17 '16 at 14:59
  • 1
    Please don't get me wrong - I wasn't critisizing your fine answer. Since the title at the time when you wrote the answer was misleading, I thought to add a comment (possibly to future readers). Here, have an upvote. – Ami Tavory Aug 17 '16 at 15:01
  • And? this task boils down to check, whether point lies on line segment boundary. I think this degenerate case can be easily treated. – Alex Aparin Aug 17 '16 at 15:05
  • I don't think this is correct. A point can be in the interior of all convex hull projections but be a vertex of the convex hull. – aschepler Aug 17 '16 at 15:08
  • I don't agree with you, if it will be boundary vertex, then exists at least one convex hull, which has its point as boundary vertex (or maybe I understood you incorrectly?) P.S. I undertood, yes, you are right, it checks point on non strict location (with boundary) – Alex Aparin Aug 17 '16 at 15:12
  • No, the point can be in all plane projections but completely outside the hull. Normal 3d example: hull of {(0,0,10),(0,10,0),(10,0,0),(10,10,10)}, point (1,1,1). – n. m. could be an AI Aug 17 '16 at 15:54
  • @n.m. Oh, Yes. I pointed this fact. Algorithm only allows to check that point lies inside of convex hull or on its boundary – Alex Aparin Aug 17 '16 at 16:02
  • 1
    @АлександрЛысенко No, the point is far away fron the hull boundary. – n. m. could be an AI Aug 17 '16 at 16:04
  • @n.m. Good catch! I missed this case. – Alex Aparin Aug 17 '16 at 16:16