Technical Reports

The ICICS/CS Reading Room


UBC CS TR-99-12 Summary

Practical Point-in-Polygon Tests Using CSG Representations of Polygons, November 12, 1999 Robert J. Walker and Jack Snoeyink, 22 pages

We investigate the use of a constructive solid geometry (CSG) representation of polygons in testing if points fall within them; this representation consists of a tree whose nodes are either Boolean operators or edges. By preprocessing the polygons, we seek (1) to construct a space-conserving data structure that supports point-in-polygon tests, (2) to prune as many edges as possible while maintaining the semantics of our tree, and (3) to obtain a tight inner loop to make testing the remaining edges as fast as possible. We utilize opportunities to optimize the pruning by permuting sibling nodes. We find that this process is less memory-intensive than the grid method and faster than existing one-shot methods.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.