Překryvy map - algoritmus pro nalezení překryvu dvou rovinných podrozdělení

Popis rovinného podrozdělení pomocí dvojitě souvislého seznamu (double connected edge list), oblast přilehlá k hraně, následující hrana, předchozí hrana, dvojče. Tabulka pro vrcholy, hrany a oblasti. Vyhledávání potřebných údajů v tabulkách pomocí pointerů.

Překryv dvou podrozdělení pomocí algoritmu zametací přímky. Postupně ze dvou dvojitě souvislých seznamů vytváříme seznam vrcholů a hran pro podrozdělení. Je potřeba rozebrat více případů průniku úseček z obou podrozdělení. Nalezení hraničních cyklů. Zjištění, které jsou vnitřní a které vnější. Vytvoření grafu z cyklů. Komponenty tohoto grafu odpovídají oblastem podrozdělení. Ke každé takové oblasti musíme přiřadit oblasti původních podrozdělení, ve kterých leží. Časová náročnost O(n log n+k log n), kde n je komplexita vstupu a k komplexita výstupu.

Aplikace na nalezení průniku, sjednocení nebo rozdílu dvou nekonvexních mnohoúhelníků.

Pseudokód algoritmu najdete na straně 6 následujícího souboru