MathGroup Archive 2000

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

Search the Archive

RE: Point inside a plygon? and PointInsidePolyhedronQ

  • To: mathgroup at
  • Subject: [mg25369] RE: [mg25239] Point inside a plygon? and [mg24992]PointInsidePolyhedronQ
  • From: "Self, William" <WSelf at>
  • Date: Sun, 24 Sep 2000 03:01:37 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

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]}

I also wrote some code that is quite fast at producing a
triangulation of any planar polygon, if anyone wants to see

-----Original Message-----
From: Andrzej Kozlowski [mailto:andrzej at]
To: mathgroup at
WSelf at
Subject: [mg25369] Re: [mg25239] Point inside a plygon? and

on 98.9.4 3:07 PM, Richard I. pelletier at rip1 at 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

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.


  • Prev by Date: RE: Differential operators, Help
  • Next by Date: Re: filtering data
  • Previous by thread: Re: Point inside a plygon? and PointInsidePolyhedronQ
  • Next by thread: RE: Point inside a plygon? and PointInsidePolyhedronQ