Re: Re: point in convex hull
- To: mathgroup at smc.vnet.net
- Subject: [mg55537] Re: [mg55515] Re: point in convex hull
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Mon, 28 Mar 2005 02:42:14 -0500 (EST)
- References: <d1tvc0$rli$1@smc.vnet.net> <200503270742.CAA06233@smc.vnet.net> <opsoa9q5xpiz9bcq@monster.ma.dl.cox.net>
- Sender: owner-wri-mathgroup at wolfram.com
drbob wrote
> 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
>
<snip>
Bobby,
I believe the first point returned by ConvexHull always has the maximal x
value, and so I believe it is impossible for minPosition to be 1. That is
why membership was coded the way it was. Moreover, I used the fact that the
points returned by ConvexHull are given in counterclockwise order (as
mentioned in the Help) in order to find the points forming the above and
below lines. If the first point could possibly not be the point with the
maximal x value, it would be a simple matter to modify membership (probably
using Ordering[pts,-1]).
On the other hand, it is certainly possible that minPosition could be the
last element (Length@ch), but that would still leave two points. In your
code you append the first element of ch to the end of ch, so if minPosition
were Length@ch, bl would contain the first and last points of ch.
Carl Woll
- References:
- Re: point in convex hull
- From: "Carl K. Woll" <carlw@u.washington.edu>
- Re: point in convex hull