Flächenüberschneidung suchen

[blablab]

Ich denke im ungünstigen Fall sind es vielleicht maximal 1000 oder 10000 oder so. Aber es wären dann auch viele Punkte die abgefragt werden...

Aber so wies aussieht kann man da ja nicht viel machen. Wenn man das ganze in log(n) hinbekommen würde wär das natürlich genial gewesen Aber so wie es aussieht wird der Aufwand ja teilweise sogar größer statt kleiner und wenn das so ist, dann ist damit meine Frage ja auch beantwortet: Ich sollte einfach alle Rects durchgehen.
Mir geht es eigentlich darum, dass ich gerne eine der schnellsten Lösungen hätte. Und wenn es nicht schneller geht, dann bin ich damit auch zufrieden.
Also vielen Dank für die Mühe!!!

[DeddyH]

Da mich das jetzt selbst interessiert, ob mein Gedankengang richtig ist, werde ich mich selbst mal daran setzen. Allerdings bin ich noch bis 17:00 Uhr auf der Arbeit, komme also frühestens heute Abend dazu. Auf das Ergebnis bin ich selbst gespannt

[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.