The point of polygon problem for arbitrary polygons. (English) Zbl 0990.68173
Summary: 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.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
winding numberReferences:
| [1] | Foley, J. D.; van Dam, A.; Feiner, S. K.; Hughes, J. F., Computer Graphics: Principles and Practice (1990), Addison-Wesley |
| [2] | R. Franklin, pnpoly, http://www.ecse.rpi.edu/Homepages/wrf/geom/pnpoly.html; R. Franklin, pnpoly, http://www.ecse.rpi.edu/Homepages/wrf/geom/pnpoly.html |
| [3] | E. Haines, CrossingsMultiplyTest, http://www.acm.org/tog/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c; E. Haines, CrossingsMultiplyTest, http://www.acm.org/tog/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c |
| [4] | Haines, E., Point in polygon strategies, (Heckbert, P., Graphic Gems IV (1994), Academic Press: Academic Press Boston, MA), 24-46 |
| [5] | Harrington, S., Computer Graphics: A Programming Approach (1983), McGraw-Hill |
| [6] | Mehlhorn, K.; Näher, S., LEDA: A Platform for Combinatorial and Geometric Computing (1999), Cambridge University Press · Zbl 0976.68156 |
| [7] | Nievergelt, J.; Hinrichs, K., Algorithms and Data Structures: With Applications to Graphics and Geometry (1993), Prentice-Hall |
| [8] | O’Rourke, J., Computational Geometry in C (1998), Cambridge University Press · Zbl 0912.68201 |
| [9] | Rogers, D. F., Procedural Elements for Computer Graphics (1985), McGraw-Hill |
| [10] | Sedgewick, R., Algorithms (1988), Addison-Wesley |
| [11] | Stein, B., A point about polygons, Linux Journal, 35 (March 1997) |
| [12] | Theoharis, T.; Böhm, A., Computer Graphics: Principles & Algorithms (1999), Symmetria, (in Greek) |
| [13] | Weiler, K., An incremental angle point in polygon test, (Heckbert, P., Graphic Gems IV (1994), Academic Press: Academic Press Boston, MA), 16-23 |
| [14] | Woo, M.; Neider, J.; Davis, T., OpenGL Programming Guide (1997), Addison-Wesley |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
