An algorithm for set operations on nonconvex polygons (with an application to census tracts)

摘要

The main purpose of this paper is to make available an algorithm to perform Boolean set operations on nonconvex polygons. Along the way the representation of polygons by oriented boundaries and vertex sets is discussed. It is found that the logical core of the method is simple due to a topological steering criterion that applies equally to all Boolean operations. The computational provisions are briefly explained, and an example and an application end the paper. There are three figures and an Appendix with APL codes.