Flächenüberschneidung suchen

[blablab]

Das verstehe ich jetzt nicht...
Meinst du dass z.B. zuerst nach Left sortiert wird und wenn Left bei beiden gleich ist wird nach Right sortiert usw. ? Weil dann weiß ich nicht wie ich diese Liste beim Ausschlussverfahren benutzen kann.
Ich kann dann zwar die Sortierung nach Left benutzen um alle Rects auszuschließen, die sich rechts vom Punkt befinden, aber bei den restlichen Rects wird es dann schwer und bringt nicht mehr viel....

@Bummi
Das glaube ich langsam auch... :(
Wahrscheinlich läuft es darauf hinaus, dass der Code maximal 10% schneller und dafür 10x so kompliziert ist

[DeddyH]

Wenn Du alle Rects ausschließen kannst, welche sich rechts vom Punkt befinden, kannst Du aus den verbleibenden wiederum die ausschließen, deren rechte Seite sich links vom Punkt befindet usw. Ob sich dieser ganze Aufwand allerdings lohnt hängt m.E. von der Anzahl der zu vergleichenden Rechtecke ab.

[blablab]

Das geht doch aber nur, wenn man nach allen Eigenschaften einzeln sortiert...

[DeddyH]

Wieso? Du musst lediglich in der Reihenfolge der Kriterien vergleichen, in der die Liste auch sortiert wurde, sonst bringt das Ganze ja nichts.

[blablab]

Angenommen ich hab jetzt
Punkt (x,y):
(3,0)
Flächen (Left, Right, Top, Bottom):
1: (0,1,0,0)
2: (0,5,0,0)
3: (1,1,0,0)
4: (1,5,0,0)
5: (2,1,0,0)
6: (2,5,0,0)
7: (9,0,0,0)
...

Die sind ja sortiert.
Im ersten Schritt kann ich dann 7 und alles was folgt aussortieren.
Im zweiten Schritt muss ich dann 1, 3 und 5 aussortieren. Das wird dann schon etwas kompliziert und wahrscheinlich nicht sehr effizient.

[DeddyH]

Von wievielen Rects reden wir eigentlich? Ich vermute nämlich, dass sich dieser Aufwand erst ab ein paar Tausend wirklich lohnt, aber ich bin kein Mathematiker.

[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 :-D 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 :lol:

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