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>