From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Points inside/outside convex hull Date: 15 Nov 1999 12:20:31 GMT Newsgroups: sci.math.num-analysis In article , Hong Ooi writes: |> Hello, |> |> Say I have a bunch of points in 2D, and I determine their convex hull. |> Now I'm given a new point, and I want to know if it lies inside that |> hull. What would be the best way of doing this? |> this is information i assembled some time ago, not from me: Let me assume that your convex hull is (at least initially) defined by a set of n points. Even if you're doing the test only once, you're better off computing the planes that support the facets of the convex hull (as Gino van den Bergen pointed out in his post). You can do this in O(n log n) time, using any number of algorithms, including quickhull. Then test each facet to see if the query point is on the right side, which takes O(n) time. The overall time is O(n log n). On the other hand, if you're going to be testing several points against the same convex hull, you can do much better. By doing some extra preprocessing on the convex hull, which takes O(n) extra time, you can build a data structure that can answer a query using only O(log n) plane tests. (In practice, this is only going to be worth doing if n is fairly large.) Again, there are several different data structures that get these time bounds. The easiest to implement (although not the fastest) is based on the so-called Dobkin-Kirkpatrick hierarchy. The idea is to build a sequence of nested convex hulls, with your convex hull as the largest in the sequence. To get from one convex hull to the next smaller one, find a large independent set of vertices, no pair of which share an edge, delete them, and compute the new facets. There's a simple algorithms that lets you delete 1/7 of the vertices at once. The sequence stops when the polytope is a tetrahedron. You also need to remember a single "basepoint" somewhere in the interior of this tetrahedron. Since you're deleting a constant fraction of the vertices at every step, the length of the sequence is O(log n). To determine if a query point is inside your convex hull, first check if it's inside the tetrahedron. If it is, you're done. If it isn't, it might be in the next larger hull. Connect your query point to the base point with a line, and figure out which facet of the tetrahedron the line crosses. Now walk your way up the hierachy. At each level, see if the facet is still there. If it is, do nothing. If it isn't, then test your query point against the new facets that "hide" the old facet. If the point's inside, you're done; otherwise, find a new facet and keep walking. If you get all the way to the top and the query point is still outside, then you know the point is outside the convex hull. At each level, you do a constant amount of work, so the total query time is O(log n). I'm sure I've gone through this way too fast. For more details, see Chapters 7.5 and 7.6 of Joe O'Rourke's textbook "Computational Geometry in C" (Cambridge, 1994) and/or the Web page http://athos.rutgers.edu/~elices/529/ If you have Geomview, you can download a module from this web page that lets you see the hierarchy. -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Duke University http://www.cs.duke.edu/~jeffe (send by p.spellucci)