Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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:
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
Wieso? Du musst lediglich in der Reihenfolge der Kriterien vergleichen, in der die Liste auch sortiert wurde, sonst bringt das Ganze ja nichts.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
Achso, Du suchst ein geeignetes Ausschlussverfahren. Da muss ich mal drüber nachdenken.
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?
Forum: Algorithmen, Datenstrukturen und Klassendesign
by DeddyH,
28. Jan 2011
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.