# Overlaying maps, planar graphs, polyhedra

See also Boolean operations, local topology theory and example applications .

## 1 Publications

#### 2022

- W. Randolph Franklin and Salles Viana Gomes de Magalhães.
**Implementing simulation of simplicity for geometric degeneracies.**In*4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)*. 1 Nov 2022.

[abstract▼] [details] [full text] [BibTeX▼] - 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/.

[abstract▼] [details] [full text] [BibTeX▼]

#### 2020

- Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade.
**An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters.***J. Computer Aided Design*, March 2020. online 2019-12-19. doi:https://doi.org/10.1016/j.cad.2019.102801.

[abstract▼] [details] [full text] [BibTeX▼]

#### 2019

- W. Randolph Franklin and Salles Viana Gomes de Magalhães.
**Minimal representations of polygons and polyhedra.**In John Krumm, editor,*1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)*. ACM, Nov 2019. URL: https://www.spatialgems.net/.

[abstract▼] [details] [full text] [BibTeX▼] - W. Randolph Franklin and Salles V. G. de Magalhães.
**Computing intersection areas of overlaid 2d meshes.**In*IGS2019 International Geometry Summit Posters' proceedings*. Vancouver, Canada, 17–21 June 2019. Solid Modeling Association.

[abstract▼] [details] [full text] [poster] [fastforward] [BibTeX▼]

#### 2018

- W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
**Exact fast parallel intersection of large 3-D triangular meshes (extended abstract).**In*28th Annual Fall Workshop on Computational Geometry*. Queens College, CUNY, New York City, 26–27 Oct 2018.

[abstract▼] [details] [full text] [BibTeX▼] - W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
**Exact fast parallel intersection of large 3-D triangular meshes.**In*27th International Meshing Roundtable*. Alberqueque, New Mexico, 2 Oct 2018.

[abstract▼] [details] [full text] [slides] [BibTeX▼]

#### 2017

- W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
**3D-EPUG-Overlay: intersecting very large 3D triangulations in parallel.**In*2017 SIAM conference on industrial and applied geometry*. Pittsburgh PA USA, 10–12 July 2017. (talk).

[abstract▼] [details] [slides] [BibTeX▼] - W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
**An exact and efficient 3D mesh intersection algorithm using only orientation predicates.**In*S3PM-2017: International Convention on Shape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium*. Berkeley, California, USA, 19–23 June 2017. (poster).

[abstract▼] [details] [poster] [BibTeX▼]

#### 2016

- Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi.
**Exact intersection of 3D geometric models.**In*Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics*. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).

[abstract▼] [details] [full text] [slides] [BibTeX▼] - W. Randolph Franklin and Salles Viana Gomes de Magalhães.
**Local topology and parallel overlaying large planar graphs.**15 Feb 2016. Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015.

[details] [slides] [BibTeX▼]

#### 2015

- Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
**Fast exact parallel map overlay using a two-level uniform grid.**In*4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial)*. Bellevue WA USA, 3 Nov 2015. doi:https://doi.org/10.1145/2835185.2835188.

[abstract▼] [details] [full text] [BibTeX▼] - Salles V. G. de Magalhães, W. Randolph Franklin, Marcus V. A. Andrade, and Wenli Li.
**An efficient algorithm for computing the exact overlay of triangulations.**In*25th Fall Workshop on Computational Geometry*. U. Buffalo, New York, USA, 23-24 Oct 2015. (extended abstract).

[details] [full text] [BibTeX▼]

#### 2014

- Salles V. G. de Magalhães and W. Randolph Franklin.
**Exactly computing map overlays using rational numbers.**In*Autocarto 2014*. Pittsburgh PA, 5–7 Oct 2014. Cartography and Geographic Information Society. (abstract only).

[details] [full text] [slides] [BibTeX▼]

#### 1994

- Wm. Randolph Franklin.
**Overlay area calculation program.**1994. URL: https://wrfranklin.org/wiki/Research/overlay.tgz.

[details] [BibTeX▼] - Wm Randolph Franklin, Venkateshkumar Sivaswami, David Sun, Mohan Kankanhalli, and Chandrasekhar Narayanaswami.
**Calculating the area of overlaid polygons without constructing the overlay.***Cartography and Geographic Information Systems*, pages 81–89, April 1994.

[details] [full text] [BibTeX▼]

#### 1993

- Wm Randolph Franklin and Mohan S. Kankanhalli.
**Volumes from overlaying 3-D triangulations in parallel.**In D. Abel and B.C. Ooi, editors,*Advances in Spatial Databases: Third Intl. Symp., SSD'93*, volume 692 of Lecture Notes in Computer Science, pages 477–489. Springer-Verlag, June 1993.

[details] [full text] [BibTeX▼]

#### 1992

- Wm Randolph Franklin.
**Map overlay area animation and parallel simulation.**In David H. Douglas, editor,*Proceedings, SORSA'92 Symposium and Workshop*, 200–203. July 28–August 2 1992.

[details] [full text] [BibTeX▼]

#### 1990

- Wm Randolph Franklin.
**Calculating map overlay polygon' areas without explicitly calculating the polygons — implementation.**In*4th International Symposium on Spatial Data Handling*, 151–160. Zürich, 23-27 July 1990.

[details] [full text] [BibTeX▼] - Wm Randolph Franklin and Venkatesh Sivaswami.
**OVERPROP — calculating areas of map overlay polygons without calculating the overlay.**In*Canadian National Conference on Geographic Information Systems: Challenge for the 1990's*, 1646–1654. Ottawa, 5-8 Mar 1990. Canadian Institute of Surveying and Mapping.

[details] [full text] [BibTeX▼] - Peter Y.F. Wu and W. Randolph Franklin.
**A logic programming approach to cartographic map overlay.***Journal of Computational Intelligence*, 6(2):61–70, May 1990. doi:https://doi.org/10.1111/j.1467-8640.1990.tb00290.x.

[details] [full text] [BibTeX▼] - Venkateshkumar Sivaswami.
**Point inclusion testing in polygons and point location in planar graphs using the uniform grid technique.**Master's thesis, Rensselaer Polytechnic Institute, Electrical, Computer, and Systems Engineering Dept., May 1990.

[details] [BibTeX▼]

#### 1987

- Wm Randolph Franklin and Peter YF Wu.
**A polygon overlay system in prolog.**In*Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography*, 97–106. Baltimore, Maryland, 29 Mar – 3 April 1987.

[details] [full text] [BibTeX▼]

#### 1983

- Wm Randolph Franklin.
**A simplified map overlay algorithm.**In*Harvard Computer Graphics Conference*. Cambridge, Mass, USA, 31 July – 4 August 1983.

[details] [full text] [BibTeX▼]

## 2 Program

Overpropf overlays two maps (aka planar graphs), and computes the areas of all the nonempty intersections of any polygon of one map with any polygon of the other.

One application is to interpolate some statistic of one map over to the other. E.g., we might have the population of each polygon of one map, and wish to estimate the polygon of each polygon of the other map from the fractions of intersected areas.

It is very fast because it uses my uniform grid and my local topological formulae.

*Contact:* WRF