Re: Re: point in convex hull
- To: mathgroup at smc.vnet.net
- Subject: [mg55555] Re: [mg55515] Re: point in convex hull
- From: DrBob <drbob at bigfoot.com>
- Date: Tue, 29 Mar 2005 03:42:38 -0500 (EST)
- References: <d1tvc0$rli$1@smc.vnet.net> <200503270742.CAA06233@smc.vnet.net> <opsoa9q5xpiz9bcq@monster.ma.dl.cox.net> <011401c53310$74dde680$6400a8c0@Main> <opsob4uhh3iz9bcq@monster.ma.dl.cox.net> <02a501c533ac$f76aa4c0$6400a8c0@Main>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
That's pretty much equivalent to my last solution, but using Split is a clever shortcut for some of the work.
Bobby
On Mon, 28 Mar 2005 10:44:00 -0500, Carl K. Woll <carl at woll2woll.com> wrote:
> DrBob wrote
>
>> I'd already realized minPosition == Length@ch was OK, and I was unable to
>> concoct an example in which minPosition == 1. I don't see any
>> documentation to guarantee this, however, so even if it's true, it may not
>> be true in the next version.
>>
>> Without that assumption, I thought this would do it:
>>
>> membership[pts_] := Module[{ch, min, max},
>> ch = ConvexHull[pts];
>> max = Position[ch, Ordering[pts, -1][[1]]][[1,1]];
>> ch = RotateLeft[ch, max - 1];
>> min = Position[ch, Ordering[pts, 1][[1]]][[1,1]];
>> AppendTo[ch, ch[[1]]];
>> al = Interpolation[pts[[Take[ch, min]]],
>> InterpolationOrder -> 1];
>> bl = Interpolation[pts[[Drop[ch, min - 1]]],
>> InterpolationOrder -> 1];
>> includedQ[{x_, y_}] :=
>> al[[1,1,1]] <= x <= al[[1,1,2]] &&
>> (y - al[x])*(y - bl[x]) <= 0
>> ]
>>
>> But then I realized all these Interpolation methods fail on the following
>> example:
>>
>> pts=Distribute[{Range@2,Range@2},List]
>>
>> {{1,1},{1,2},{2,1},{2,2}}
>>
>> because of duplicated x values.
>>
>> A fix isn't conceptually hard -- just TEDIOUS. I admit I haven't tested it
>> with a convex hull that defies our expectations:
>>
>> membership[data_] := Block[
>> {pts = Union@data,
>> mod = Mod[#, Length@ch, 1] &,
>> pos = Position[ch, pts[[#]]][[-1, 1]] &,
>> x = First@ch[[mod@#]] &,
>> pair = With[{k = pos@#}, If[x[k] == x[k - 1],
>> {ch, k},
>> {Insert[ch, pts[[#]], k], k + 1}]] &,
>> first, last, ch},
>> ch = pts[[ConvexHull@pts]];
>> {ch, first} = pair[1];
>> {ch, last} = pair[-1];
>> ch = RotateLeft[ch, last - 1];
>> first = pos[1] - 1;
>> al = Interpolation[Take[ch, first], InterpolationOrder -> 1];
>> bl = Interpolation[Drop[ch, first], InterpolationOrder -> 1];
>> includedQ[{x_, y_}] := al[[1,1,1]] <= x <= al[[1,1,2]] &&
>> (y - al[x])*(y - bl[x]) <= 0
>> ]
>>
>> Bobby
>>
>
> <snip>
>
> DrBob,
>
> Good point about the possibility of vertical lines at the left and right
> ends of the convex hull. I see you also included a Union command to get rid
> of duplicate points. However, I would have approached the solution in a
> different way (I confess that I haven't spent the time to figure out what
> you did). The above interpolation line would consist of the points from the
> top most left end to the top most right end, and similarly for the below
> interpolation line. If you apply Union to the data, then the position of the
> top (bottom) most points on the left and right is easy to determine. I end
> up with the following membership function:
>
> membership[pts_] :=
> Module[{spts, ss},
> spts = Union[pts];
> ss = Split[spts[[All,1]]];
>
> aboveleft = Length[ss[[1]]];
> aboveright = Length[spts];
> belowleft = 1;
> belowright = Length[spts] - Length[ss[[-1]]] + 1;
>
> ch = ConvexHull[spts];
>
> abovefirst = RotateLeft[ch, Position[ch, aboveright][[1,1]] - 1];
> abovepts = spts[[Take[abovefirst, Position[abovefirst,
> aboveleft][[1,1]]]]];
> al = Interpolation[abovepts, InterpolationOrder -> 1];
>
> belowfirst = RotateLeft[ch, Position[ch, belowleft][[1,1]] - 1];
> belowpts = spts[[Take[belowfirst, Position[belowfirst,
> belowright][[1,1]]]]];
> bl = Interpolation[belowpts, InterpolationOrder -> 1];
>
> includedQ[{x_, y_}] := al[[1,1,1]]<=x<=al[[1,1,2]] && (y - al[x])(y -
> bl[x])<=0;
> ]
>
> Carl Woll
>
>
>
>
>
--
DrBob at bigfoot.com
- References:
- Re: point in convex hull
- From: "Carl K. Woll" <carlw@u.washington.edu>
- Re: point in convex hull