Flächenüberschneidung suchen

[Medium]

Standardverfahren: Segmentierung.
Unterteile deine gesamte Fläche in N*M gleich große Quadrate, und eine Listenstruktur, in die du für jedes der Quadrate hinterlegst, welche Rechtecke dieses Quadrat beinhaltet.
Kommt nun ein einzelner Punkt, reicht ein Modulo N bzw. Modulo M der Koordinaten um das Quadrat in dem sich der Punkt befindet zu bestimmen, und nur dessen Rechtecke sind zu überprüfen.
Analog dazu bei einem Rechteck: Bestimme alle Quadrate die das neue Rechteck beinhalten würden, und prüfe auf die in diesen bereits vorhandenen.

Je feiner die Segmentierung, desto mehr wird "billig" im Vorhinein ausgeschlossen, desto mehr Overhead findet sich aber auch in der Optimierungsstruktur. Wo dort dann das Optimum liegt ist Ausprobierenssache.

Der fieseste Teil an dem ganzen ist eigentlich, dass es Rechtecke geben kann, die ein Segment belegen, aber keinen Eckpunkt darin haben - das ist der eigentlich teure und aufwendige Teil, der aber zum einen lohnenswert ist, und zum anderen nur ein einziges Mal zu Beginn gemacht werden muss, und eben für jedes neu eingefügte Rechteck einmalig.

[DeddyH]

Mir ist bei meinem Vorschlag im Nachhinein eingefallen, dass ich da einen kapitalen Denkfehler gemacht habe. Wenn die Rechtecke unterschiedlich groß sind, nützt einem die 4-fache Sortierung nämlich gar nichts.