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!

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

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