3. přednáška
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