[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**Re: Re: Re: Bug in Import?**
Next by Date:
**Re: Simplifying ArcTan**
Previous by thread:
**Re: Re: point in convex hull**
Next by thread:
**Re: Re: point in convex hull**
| |