Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: point in convex hull

• To: mathgroup at smc.vnet.net
• Subject: [mg55515] Re: point in convex hull
• From: "Carl K. Woll" <carlw at u.washington.edu>
• Date: Sun, 27 Mar 2005 02:42:51 -0500 (EST)
• Organization: University of Washington
• References: <d1tvc0$rli$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"steve fisk" <fisk at bowdoin.edu> wrote in message 
news:d1tvc0$rli$1 at smc.vnet.net...
> If pts is a set of points, and w is a point I can use ConvexHull[pts] to
> find the convex hull of the points in pts. Is there a function to
> determine if w lies in the convex hull?
>

Hi Steve,

On further reflection, if you are interested in testing membership of a lot 
of points in your convex hull, then you should be able to use the fact that 
you have a convex hull to speed things up. You can take the information 
returned by ConvexHull to obtain the min and max x values, and then use 
Interpolation (with InterpolationOrder->1) to find an above line from min to 
max and a below line from min to max. The convex hull contains all points 
between these two lines. To find out if a point is between the two lines, 
simply take the difference between the y value of the point and the above 
and below lines, and then multiply the two values. If the value is 
nonpositive, the point is in the convex hull. Once the above and below lines 
are determined, the time to test inclusion of a point is negligible. For 
comparison purposes, this approach is orders of magnitude faster than Ray 
Koopman's for a set of data with a convex hull containing more than 100 
points.

Below I give a function that puts the above ideas together.

Needs["DiscreteMath`"]

membership[pts_] := Module[{ch},
ch = ConvexHull[pts];
al = Interpolation[
 pts[[Take[ch, Position[ch, Ordering[pts, 1][[1]]][[1,1]]]]],
 InterpolationOrder -> 1];
bl = Interpolation[
 pts[[Take[RotateLeft[ch], Position[ch, Ordering[pts, 
1][[1]]][[1,1]]-Length[ch]-2]]],
 InterpolationOrder -> 1];
includedQ[{x_, y_}] /; al[[1,1,1]]<x<al[[1,1,2]] := (y-al[x])(y-bl[x])<=0;
includedQ[{x_, y_}] = False;
]

For example, if we define pts as a subset of the points on a circle:

pts = Table[{Cos[x], Sin[x]}, {x, 0, 2Pi, .01}];

The convex hull contains almost 630 points. Then use membership on the 
points.

membership[pts]

and test on some points

includedQ[{-.5, .5}]
includedQ[{.9, .9}]
includedQ[{1.1, .1}]
True
False
False

Carl Woll 

• Follow-Ups:
  • Re: Re: point in convex hull
    • From: DrBob <drbob@bigfoot.com>
  • Re: Re: point in convex hull
    • From: DrBob <drbob@bigfoot.com>