W. Randolph Franklin and Salles Viana Gomes de Magalhães. Minimal representations of polygons and polyhedra. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 5. ACM, 2022. URL: https://www.spatialgems.net/.
[full text] [BibTeX▼]


We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.