From: Dana Swift Newsgroups: sci.math.num-analysis Subject: Re: Evaluating the convex hull of a number of points Date: Thu, 24 Oct 1996 17:46:25 -0700 On 24 Oct 1996, Michael C. Herron wrote: > > In order to evaluate a function f(x), I have to determine if x is in > the convex hull of a bunch of points (in R^2). Some code I am writing > must evaluate f thousands of times. > > Can someone refer me to efficient methods that people have developed > to do this? I can code up inefficient algorithms to determine if a > given x is in the convex hull of the points, but I am curious as to > existing algorithms. The most efficient method known for constructing the convex hull of an arbitrary set of points in 2-D is referred to as the Graham Scan. It's really pretty straightforward to code. The inefficient method you are might be referring to is often called a "shrink-wrap" and requires a number of comparisons that is proportional to the square of the number (n) of points. The Graham Scan is an order n*log2(n) which is considerably more efficient than n^2. I'd refer you to Sedgewick's book "Algorithms in C" (now also available for C++) for a reasonably good description. Detecting if a point is inside a convex hull is not too hard either and is also discussed in Sedgewick's book. -dds ========================================================================= = Dana D. Swift Office: (206) 543-6697 = = School of Oceanography o__ ____ Fax: (206) 685-3354 = = University of Washington _,>/'_ ----- swift@ocean.washington.edu = = Box 357940 (_) \(_) ------ ORB 106 = = Seattle, WA 98195 = = http://www.ocean.washington.edu/people/staff/swift/Swift.html = ========================================================================= ============================================================================== Newsgroups: sci.math.num-analysis From: clarkson@research.att.com (Ken Clarkson) Subject: Re: Evaluating the convex hull of a number of points Date: Tue, 29 Oct 1996 14:35:44 GMT In article <54omos\$6b2@gsb-birr.Stanford.EDU>, pherron@gsb-birr.Stanford.EDU (Michael C. Herron) writes: |> Can someone refer me to efficient methods that people have developed |> to do this? I can code up inefficient algorithms to determine if a |> given x is in the convex hull of the points, but I am curious as to |> existing algorithms. At http://www.geom.umn.edu:80/software/cglist/ there is a collection of links to code for geometric problems, and at http://www.geom.umn.edu:80/software/cglist/lowdvod.html, there are pointers to various low-dimensional geometric algorithms, including a few 2-dimensional convex hull codes. I wrote one of these, in C; it's at http://cm.bell-labs.com/who/clarkson/2dch.c. My code is somewhat like Graham scan, but uses two sorts by x-coordinate instead of one sort by angle, and explicitly computes the "upper hull" and the "lower hull" of the points. I take it that you want to compute the hull, and then check for various points p if they are in the hull. You could do this with my code by checking if p is above the upper hull or below the lower hull. To check if p is above the upper hull, you'd find the two consecutive hull vertices whose x coordinates bracket the x-coordinate of p, and then check if p is above the line segment between them. This could be done using the primitives already in my code. The dominant cost here is probably finding those two consecutive points, which could be done by binary search in O(log n) time for n vertices, or by bucketing in expected constant time for reasonable point sets. In any case, the test should take fewer than maybe 20 lines of code. -Ken