Re: Point inside a plygon? and PointInsidePolyhedronQ
- To: mathgroup at smc.vnet.net
- Subject: [mg24341] Re: [mg25239] Point inside a plygon? and [mg24992]PointInsidePolyhedronQ
- From: Andrzej Kozlowski <andrzej at lineone.net>
- Date: Sat, 23 Sep 2000 03:35:44 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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