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>