|
|||||
|
|
The point in polygon problem for arbitrary polygons |
|
| Authors: | Kai Hormann and Alexander Agathos |
| Affiliation: | a University of Erlangen, Computer Graphics Group, Am Weichselgarten 9, 91058 Erlangen, Germany b University of Athens, Department of Informatics, Athens, Greece |
| Abstract: | A detailed discussion of the point in polygon problem for arbitrary polygons 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-crossing, the latter to angle summation algorithms. First we show by mathematical means that both concepts are very closely related, thereby developing a first version of an algorithm for determining the winding number. Then we examine how to accelerate this algorithm and how to handle special cases. Furthermore we compare these algorithms with those found in literature and discuss the results. |
| Keywords: | Polygons Point containment Winding number Integer algorithms Computational geometry |
| 本文献已被 ScienceDirect 等数据库收录！ | |