MathGroup Archive 2005

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

Search the Archive

Re: Re: point in convex hull

  • To: mathgroup at
  • Subject: [mg55537] Re: [mg55515] Re: point in convex hull
  • From: "Carl K. Woll" <carl at>
  • Date: Mon, 28 Mar 2005 02:42:14 -0500 (EST)
  • References: <d1tvc0$rli$> <> <>
  • Sender: owner-wri-mathgroup at

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



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 

  • Prev by Date: Re: Questions about Abs[_]
  • Next by Date: Re: Questions about Abs[_]
  • Previous by thread: Re: point in convex hull
  • Next by thread: Re: Re: point in convex hull