Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra
Loading...
Date
1987
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Eurographics Association
Abstract
Algorithms are presented for the determination of whether a given point E<sup>2</sup> in is interior to, exterior to or on an arbitrary polygonal boundary and for the determination of whether a point in E <sup>3</sup> 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.
Description
@inproceedings{10.2312:egtp.19871032,
booktitle = {EG 1987-Technical Papers},
editor = {},
title = {{Efficient and Consistent Algorithms for Determining the Containment of Points in Polygons and Polyhedra}},
author = {Chen, Min and Townsend, Teeter},
year = {1987},
publisher = {Eurographics Association},
ISSN = {1017-4656},
ISBN = {},
DOI = {10.2312/egtp.19871032}
}