Flächenüberschneidung suchen

[blablab]

Hallo!

Ich habe eine Menge von verschiedenen Flächen (TRects) die sich nicht überschneiden und möchte nun alle dieser Flächen ermitteln, die sich mit einem Punkt bzw. einer anderen gegebene Fläche (TRect) überschneiden. Das sind also 2 verschiedene (ziemlich ähnliche) Probleme.

Eine Lösung wäre wohl alle Flächen durchzugehen und jeweils zu überprüfen ob sich der Punkt darin befindet bzw. ob die gegebene Fläche geschnitten wird.

Aber ich bin die ganze Zeit am Überlegen ob es da nicht einen geschickteren Algorithmus gibt. Als erstes habe ich an Sortieren gedacht, allerdings haben die Flächen 4 Eigenschaften (left, top, right und bottom) und ich kann ja nur nach einer Eigenschaft sortieren... Und wenn ich nach allen 4 Eigenschaften einzeln sortiere, dann fallen zwar jedes Mal ein paar Flächen die nicht mehr in Frage kommen weg, allerdings muss ich am Schluss diese 4 Ergebnislisten wieder zu einer zusammenfügen, was auch wieder Zeit beansprucht...

Hat vielleicht jemand eine Idee???
Oder ist es doch am besten einfach alle Flächen durchzugehen???

Das ist wahrscheinlich etwas anspruchsvoll so früh am Morgen, aber ich weiß doch dass es hier schlaue Köpfe gibt! :-D

Grüße
blablab

[DeddyH]

Ich hoffe, dass ich keinen Denkfehler mache, aber es müsste doch so gehen: wenn Du alle Rects in einer Liste hast, nimmst Du das erste Element und vergleichst es mit allen folgenden auf Überschneidung. Anschließend das nächste Element wieder mit allen folgenden vergleichen. Ziehst Du das bis zum Ende der Liste durch, hast Du alle Rects miteinander verglichen.

[Memnarch]

@DeddyH: Und genau DAS wollte er vermeiden ;). Er wollte es möglichst so geschickt anstellen, das es möglichst wenig redundanz gibt.

@Blablab: Vllt könntest du kurz sagen wieviele flächen du hast(haben könntest. Dann lässt sich der aufwand u8nd der gewinn einer optimierung einschätzen ;)

MFG
Memnarch

[blablab]

Vielleicht hab ich das etwas blöd formuliert. Ich will nicht alle Flächen mit allen vergleichen.
Ich habe eine Menge von Rects, das nenn ich jetzt mal die Flächenliste. Ich bin mir nicht sicher ob das einen Unterschied macht, aber diese Flächenliste hat als besondere Eigenschaft, dass sich die einzelnen Flächen darin nicht überschneiden.

Und jetzt hab ich 2 Probleme:
1) Ich bekomme als Eingabe einen Punkt P.
Hier würde ich gerne ausrechnen ob dieser Punkt P eine Fläche der Flächenliste schneidet und wenn ja welche.

2) Ich bekomme als Eingabe eine Fläche F.
Hier möchte ich herausfinden welche und wie viele Flächen der Flächenliste die Fläche F schneiden.
Fläche Fläche Fläche :-D

[DeddyH]

Achso, Du suchst ein geeignetes Ausschlussverfahren. Da muss ich mal drüber nachdenken.

[edit] Wenn man nach mit CustomSort nach den Kriterien Left, Width, Top und Height sortiert, müsste sich doch eine binäre Suche realisieren lassen, oder täusche ich mich? [/edit]

[Bummi]

Iterierien mit PtInRect bzw. InsersectRect ?

[DeddyH]

Bummi, darum geht es ja nicht, das hatte ich auch erst falsch verstanden. Er sucht ein geeignetes Ausschlussverfahren, damit er nicht jedes Rect einzeln prüfen muss.

[blablab]

Kann es sein dass das mit dem sortieren sogar noch aufwändiger ist?
Ich muss ja dann in jeder Liste die binäre Suche anwenden (das ist noch nicht aufwändig). Als Ergebnis hab ich dann jeweils eine Position wo dann zum Beispiel oberhalb alle Rects in Frage kommen und unterhalb nicht. Um diese 4 Listen zusammenzufügen würde ich dann einen Boolean-Array mit der Länge n machen und dann alle Listen durchgehen und die Rects die nicht in Frage kommen im Boolean-Array markieren. Und dann müsste ich nochmal den Boolean-Array durchegehen und mir die die übriggebliebenen Rects rausschreiben.

Das wäre dann:
4*Binäre Suche = 4* log(n)
Boolean-Array initialisieren = n
Falsche Rects rausstreichen ~ 4* 1/2n
Übriggebliebenen Rects rausschreiben = n

Insgesamt sind das dann ganz grob >4n Operationen.
Das ist ja eigentlich nicht viel, aber wenn ich die n Rects einfach alle durchgehe, dann muss ich ja auch nur jeweils 4 Vergleiche pro Rect machen. Und wenn einer der 4 Vergleiche false ergibt, dann müssen die restlichen nicht verglichen werden. Das bedeutet es sind sogar eher weniger als 4n Operationen...

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

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