Ad hoc Lösung:
Sequentieller Test aller Polygone
Probleme:
- die naive Berechnung der Prädikate ist sehr aufwändig
- Suchzeit linear von der Anzahl der Polygone abhängig (O(n))
- Nicht vertretbar für große Mengen!
Verbesserungen:
zu 1): Filterschritt: Zuerst die minimal umschließende, achsenparallele
Box (minimum Bounding Box = BB)
testen
zu 2): Indexstrukturen für BBs aufbauen
|