Flächenüberschneidung suchen

[DeddyH]

Wie kommst Du auf 4 Listen? Ich meinte eine einzige, aber nach 4 Kriterien sortiert. Solange sich die Rects nicht ändern, muss diese Sortierung ja nur einmalig vorgenommen werden.

[Bummi]

mein Bauch meint iterieren wird die schnellst Methode bleiben....

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