Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra

Abstract

Algorithms are presented for the determination of whether a given point E² in is interior to, exterior to or on an arbitrary polygonal boundary and for the determination of whether a point in E ³ is interior to, exterior to or on a simple polyhedral boundary. The algorithms are based on the principle of using binary coded coordinate systems and parity counting of the number of intersections of the polygon or polyhedron boundary with an infinite vector. The amount of floating-point arithmetic, including arithmetical and comparative operations has been reduced to a minimum making the algorithms very suitable for implementation in either low-level language software or by hardware. Performance of the algorithms is compared with a number of others taken from the literature and a considerable increase in efficiency is apparent. The algorithms are also shown to be consistent.