Motivation (2)
 

Ad hoc Lösung:
Sequentieller Test aller Polygone

Probleme:

  1. die naive Berechnung der Prädikate ist sehr aufwändig
  2. 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

 

 
  Aktionsbutton 3x   zurückvor