MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: point in convex hull

  • To: mathgroup at smc.vnet.net
  • Subject: [mg55532] Re: [mg55515] Re: point in convex hull
  • From: DrBob <drbob at bigfoot.com>
  • Date: Mon, 28 Mar 2005 02:42:08 -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

That fails on the first point in your example "pts" array, but this seems to fix it:

includedQ[{x_, y_}] /; al[[1,1,1]] <= x <=
      al[[1,1,2]] :=
    (y - al[x])*(y - bl[x]) <= 0;

Unless there's some reason I'm missing, to use Less in the condition?

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: Recursion question
  • Next by Date: front end complaint (ui design flaw?)
  • Previous by thread: Re: Re: point in convex hull
  • Next by thread: Re: Re: point in convex hull