A Containment Algorithm for Point Sets Determined by Polygonal Paths
J. V. Petty · SIAM Journal on Applied Mathematics · 1977
An algorithm which determines the set-theoretic containment relation for pairs of polygonal regions in 2-dimensional space is given, where a polygonal region consists of the interior and the trace of a simple closed polygonal path. The algorithm is designed to be implemented on a general purpose digital computer. The main feature of the algorithm is that path direction is not assumed to be known. Also, the algorithm has other features which make it suitable for real-time minicomputer applications. The algorithm has been implemented in Fortran on both a large scale computer and a minicomputer. The algorithm does not easily generalize to higher dimensions.