Re: point in convex hull
- To: mathgroup at smc.vnet.net
- Subject: [mg55471] Re: point in convex hull
- From: Peter Pein <petsie at arcor.de>
- Date: Fri, 25 Mar 2005 05:48:13 -0500 (EST)
- References: <d1tvc0$rli$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
steve fisk wrote:
> 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?
>
If you integrate 1/(x-w) along the boundary of the convex hull you get
2Pi*I if w lies inside, 0 else.
Off[NIntegrate::ploss, General::spell1];
inConvexHull[pt_, set_, tol_:10^(-3)] := Module[{path, x},
path = Prepend[
Complex @@@ set[[(Append[#1, First[#1]] & )[ConvexHull[set]]]], x];
Abs[NIntegrate[1/(x - Complex @@ pt), Evaluate[path]] - 2*Pi*I] < tol]
data = Table[Random[], {10}, {2}];
inConvexHull[{1/2, 1/2}, data]
==>
True
inConvexHull[{1/2, -1/2}, data]
==>
False
--
Peter Pein
Berlin