Map Overlays Implementation

Project for CS 290: Computational Geometry. This project implements key subroutines for an $O((n+k) \log n)$-time segment intersection algorithm and an algorithm to compute the overlay of two planar subdivisions, represented as doubly-connected edge lists (DCELs).

Figures

Segment Intersections

All intersections for $n=12$ segments, generated with generate_random_segments(12).

A deletion event: The segment being deleted is red, the left neighbour to the event point is orange, and the right neighbor to the event point is green.

An intersection event: The intersecting segments are red/pink. The left neighbour to the intersection is orange, and the right neighbour to the intersection is green.

Map Overlay

The before/after of overlaying the DCELs from edge_edge_test() in dcel_datasets.py. Halfedges are red on inner cycles, and blue on outer cycles. In the overlay, the purple face is contained in a bounding face of each of the original DCELs.

The before/after of overlaying the DCELs from vert_edge_test() in dcel_datasets.py. Halfedges are red on inner cycles, and blue on outer cycles. Halfedges are red on inner cycles, and blue on outer cycles. In the overlay, the purple face is contained in a bounding face of each of the original DCELs. Note the Halfedges on the (single) inner cycle of the bounded face in the overlay, which have been updated accordingly.

The before/after of overlaying the DCELs from vert_vert_test() in dcel_datasets.py. The purple arrows point from Halfedges to their previous on the same face. In the overlay, the purple face is contained in a bounding face of each of the original DCELs. Note the Halfedges on the (single) inner cycle of the bounded face in the overlay, which have been updated accordingly.