Journal for Geometry and Graphics 19 (2015), No. 2, 283--300
Copyright Heldermann Verlag 2015
Point in Polygon Problem via Homotopy and Hopf's Degree Theorem
Shriprakash Sinha
104 - Madhurish Heights Phase 1, Risali, 490006 Bhilai, India
sinha.shriprakash@yandex.com
Luca Nanetti
Neuroimaging Center, University Medical Center, Antonious Deusinglaan 2, P.O.Box 196, 9700 AD Groningen, Netherlands
l.nanetti@med.umcg.nl
Remco J. Renken
Neuroimaging Center, University Medical Center, Antonious Deusinglaan 2, P.O.Box 196, 9700 AD Groningen, Netherlands
r.j.renken@med.umcg.nl
Gert J. ter Horst
Neuroimaging Center, University Medical Center, Antonious Deusinglaan 2, P.O.Box 196, 9700 AD Groningen, Netherlands
g.j.ter.horst@med.umcg.nl
The current work revisits the point-in-polygon problem by providing a novel solution that explicitly employs the properties of epigraphs and hypographs. A new definition of inaccessibility and inside is provided in order to accurately specify the meaning of inclusion of a point within or without a polygon. Via Poincaré's ideas on homotopy and Hopf's Degree Theorem from topology, a relationship between inaccessibility and inside is established, and it is shown that consistent results are obtained for peculiar cases of both non-intersecting and self-intersecting polygons while investigating the point inclusion test w.r.t. a polygon. Through illustrative examples, the novel method addresses the issues of ambiguous solutions given by the Cross Over for both non-intersecting and self-intersecting polygons and a point being labeled as multi-ply inside a self-intersecting polygon by the Winding Number Rule, by providing an unambiguous and singular result for both kinds of polygons. The proposed solution bridges the gap between Cross Over and Winding Number Rule for complex cases.
Keywords: Point in polygon, epigraph, hypograph, homotopy, Hopf's degree theorem.
MSC: 65D18; 68U05
[ Fulltext-pdf (2989 KB)]