Re: Re: point in convex hull

*To*: mathgroup at smc.vnet.net*Subject*: [mg55535] Re: [mg55515] Re: point in convex hull*From*: DrBob <drbob at bigfoot.com>*Date*: Mon, 28 Mar 2005 02:42:13 -0500 (EST)*References*: <d1tvc0$rli$1@smc.vnet.net> <200503270742.CAA06233@smc.vnet.net>*Reply-to*: drbob at bigfoot.com*Sender*: owner-wri-mathgroup at wolfram.com

Here's a rewrite that seems more intuitive (but really no different): Needs["DiscreteMath`"] membership[pts_] := Module[{ch, minPosition}, ch = ConvexHull[pts]; minPosition = Position[ch, Ordering[pts, 1][[1]]][[1,1]]; AppendTo[ch, ch[[1]]]; al = Interpolation[pts[[Take[ch, minPosition]]], InterpolationOrder -> 1]; bl = Interpolation[pts[[Drop[ch, minPosition - 1]]], InterpolationOrder -> 1]; includedQ[{x_, y_}] := al[[1,1,1]] <= x <= al[[1,1,2]] && (y - al[x])*(y - bl[x]) <= 0 ] One question, though... Is it impossible for minPosition to be 1 or Length@ch in some example? If that occurred, one of the Interpolations would have only one data point (hence it would fail). Bobby On Sun, 27 Mar 2005 02:42:51 -0500 (EST), Carl K. Woll <carlw at u.washington.edu> wrote: > "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 > > > > > -- DrBob at bigfoot.com

**References**:**Re: point in convex hull***From:*"Carl K. Woll" <carlw@u.washington.edu>