Geometrické algoritmy
Map Overlap
Algorithm for finding the overlap of two planar subdivisions
Description of planar subdivisions by doubly connected edge list.
Algorithm has two steps. In the first one we make modifiocation of tables for vertices and edges using speep line method. In the second spet we look for faces of the overlap using cycles of edges. Moreover, to every face of the overlap we find the faces of original maps in which the face lies.
Time complexity is O(n log n+k log n), where n is the complexity of the input and k is the complexity of the output.
Application. Intersection and union of two polygons.
Blackboards
Diploma thesis Map Overlap and Segment Intersection by Dominik Janků (in Czech)
Implementace pod windows
Zazipovaný soubor se soubory sweepline.exe na počítání průsečíků úseček a mapoverlay.exe na počítání překryvů map ve windows vytvořený Mgr. Dominikem Janků v rámci jeho diplomové práce.