       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]]]]],
InterpolationOrder -> 1];
bl = Interpolation[
pts[[Take[RotateLeft[ch], Position[ch, Ordering[pts,
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

```

• Prev by Date: Re: Re: 3D Plots: Specifying GridLine spacing for FaceGrids
• Next by Date: Re: Re: Bug in Import?
• Previous by thread: Re: point in convex hull
• Next by thread: Re: Re: point in convex hull