Services & ResourcesWolfram ForumsMathGroup Archive

[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

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