Point in Polygon Determination Algorithm for 2-D Vector Graphics Applications
Damith Kularathne, Lakshman Jayarathne · 2018
Point in polygon (PIP) determination is a common problem of determining whether a given point is inside or outside of a given polygon. The polygon is a complex closed object that consists of a number of vertices, where some of its edges might intersect any of the other edges. Determination of PIP in 2-D vector graphics application is an essential part for interaction with objects such as selection using a pointing device. Unlike in the case of basic geometric shapes such as circle and rectangle, evaluation PIP for complex polygons has become complicated. There are algorithms invented for this task, but their implementation is difficult. Ray Casting algorithm is one of the popular algorithms based on simple phenomena, but its implementation is difficult for complex polygons. Therefore, a new algorithm called Progressive Vertical Range Scanning algorithm is introduced in this research paper.