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)