RE: Point inside a plygon? and PointInsidePolyhedronQ
- To: mathgroup at smc.vnet.net
- Subject: [mg25369] RE: [mg25239] Point inside a plygon? and [mg24992]PointInsidePolyhedronQ
- From: "Self, William" <WSelf at msubillings.edu>
- Date: Sun, 24 Sep 2000 03:01:37 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I posted some code for the winding number recently. I don't
know if it appeared, but here it is. This is pretty fast.
This is for a polygonal curve. You give the vertices in
vList (don't repeat the first vertex at the last).
windingNumber[point_, vList_] := Module[
{g, ang},
g[t_] := Mod[t + Pi, 2Pi] - Pi;
ang[p_, a1_, a2_] := g[ArcTan @@ (a2 - p) - ArcTan @@ (a1 - p)];
(Plus @@ MapThread [ ang[point, #1, #2] & , {vList, RotateLeft[vList]}
])/2/Pi]
I also wrote some code that is quite fast at producing a
triangulation of any planar polygon, if anyone wants to see
that.
-----Original Message-----
From: Andrzej Kozlowski [mailto:andrzej at lineone.net]
To: mathgroup at smc.vnet.net
WSelf at msubillings.edu
Subject: [mg25369] Re: [mg25239] Point inside a plygon? and
[mg24992]PointInsidePolyhedronQ
on 98.9.4 3:07 PM, Richard I. pelletier at rip1 at home.com wrote:
> Looking at it tonight, I believe that the even-odd method is not
> equivalent to the winding number test (nor to a third proposed
> algorithm). We have not found a faster way to compute the winding
> number.
>
> Andrzej Kozlowski wrote:
>>
>> This seems
>> actually to give a fast geometric method of computing winding numbers and
>> hence can be used to write a package that would greatly improve
>> Mathematica's abilities to compute certain integrals in the complex
plane.
>
Actually you can compute winding numbers using a similar method (and indeed
it is a standard way to compute them, about which I totally forgot.). What
you have to do is not just simply count whether the number of points
intersection is odd or even. Instead you must parametrize the polygon, find
the points of intersection and check "which way" thus parametrized curve is
moving as it passes through the intersection points. Assign the number +1 to
the intersection point if the curve is moving clockwise and -1 otherwise.
Add up all the numbers and you will get the winding number.
Andrzej