The point in polygon problem for arbitrary polygons

A detailed discussion of the point in polygon problem for arbitrary polygon s is given. Two concepts for solving this problem are known in literature: the even-odd rule and the winding number, the former leading to ray-crossin g, the latter to angle summation algorithms. First we show by mathematical means that both concepts are very closely related, thereby developing a fir st version of an algorithm for determining the winding number. Then we exam ine how to accelerate this algorithm and how to handle special cases. Furth ermore we compare these algorithms with those found in literature and discu ss the results. (C) 2001 Elsevier Science B.V. All rights reserved.