0

There are a set of points S in n dimensional space. I want to test a given point P is inside the region of S.

Since this is n dimensional space, points should form a polytope. Then the question is to determine whether a given point is inside the convex polytope.

I find this for 3-D polyhedrons but C++ libraries were not meaningful and I couldn't find their definitions. Besides it doesn't check the boundary conditions.

Another algorithm I found is for 2D polygons. I couldn't modify it since it is not clearly written. I can extend it of course but I'm not an expert in this domain so it's better to ask first.

Finally I found an algorithm for triangulation for concave polygon but I don't think it fits to my case.

Community
  • 1
  • 1
Halil
  • 2,076
  • 1
  • 22
  • 30

2 Answers2

1

Not sure what exactly you are asking, it seems you have several problems. First to compute Convex Hull of a point set. In 2d you can use BOOST or CGAL. For 3d CGAL. Not sure if they handle higher dimensions. For interior check, one way is (as the link you posted states) to check the ray intersection from the point of query to a known exterior point. The point of intersection of the ray (for interior point) should lie on a plane with normal pointing in the same direction as your ray. Meaning you are exiting the volume. A more efficient way would be to use something like a Binary Space Partitioning Tree (BSP). There are many links with tutorials on how that works.

Nicko Po
  • 727
  • 5
  • 21
  • I created Convex Hull by using [MIConvexHull](http://miconvexhull.codeplex.com/). I'll check BSP whenever I find time for this problem. Thanks! – Halil Mar 13 '14 at 12:40
  • Sorry it took that long. Since I've already constructed a Convex Hull, I don't know how to apply BSP after that? Further, this method will be called frequently in my execution, so it needs to be quite fast algorithm. I don't aim for exact solution, even 30% error is acceptable since all I want to do with Convex Hull is to build a limitation to my search. – Halil Mar 19 '14 at 11:48
1

From your description, you have established that S is convex. If that is the case you apply the hyperplane separation theorem (http://en.wikipedia.org/wiki/Hyperplane_separation_theorem)

  1. Find the point Q in S that is closest to P.
  2. Construct a hyperplane H that lies on Q and is normal to P-Q
  3. Test all the points in S on which side of H are on.
  4. If they are all either on the plane or on the opposite side of H compared to P, then P is either on or outside of S. If some points are in front of H, and others are behind H, then P is inside S.
Phil Martin
  • 466
  • 4
  • 4
  • Phil, sorry for late answer. I need quite a fast algorithm since this will be called frequently throughout my execution. Instead of testing against all points in S, can I test it only for faces of the Convex Hull? Or does this method not require a previously built convex hull? – Halil Mar 19 '14 at 11:59
  • This method does not require a convex hull, and it isn't something clearly requires in your original problem. Speed is a very relative term, and I also don't know the size of the data you are processing. – Phil Martin Mar 19 '14 at 13:05
  • 1
    Since you have a covex hull, all you need to do is find one plane that point P is on or in front of. If you can find one of these your point is outside of S. If you can't find one, it will be inside of S. – Phil Martin Mar 19 '14 at 13:06
  • You are right, I don't need to have a Convex Hull. I was just confused because method doesn't utilize one. My data size is unknown but not in millions level (yet). However, since I want to distinguish foreign points lies under the convex hull of given points, I need to have hit-test for each point in dataset. then complexity becomes O(n^2) which is not really desirable for me. I can construct a convex hull in O(n) time using heuristics. Your last comment actually is a great idea. This will have O(n*m) where m is the number of faces in the polytope. I'll try that one. – Halil Mar 19 '14 at 14:09
  • Is this approach correct for determining point's position with respect to hyperplane? http://pastebin.com/FDqHNKug – Halil Mar 19 '14 at 15:57