Suche Algorithmus zu Kollisionsauflösung

Hallo,

ich suche einen Algorithmus zum Anordnen von Rechteckigen-Objekten. Konkret geht es um Elemente aus einem Diagramm.

Mein Problem kann man auch mit Spielkarten veranschaulichen, die durch Vermengen wilddurcheinander auf einem Tisch liegen.
Die Aufgabe ist nun diese so anzuordnen, dass keine Karte eine andere überschneidet. Jede Karte soll danach möglichst nah an dem Punkt liegen, an dem sie zuvor lag. Optimal wäre es, wenn auch möglichst wenig leerer Platz zwischen den Karten bleibt.

Das Problem bei dieser Sache ist weniger das finden von Kollisionen, sondern eben das Auflösen dieser.

Ich bin für jede Hilfe dankbar.

nabend.

das ganze dürfte recht leicht durchzuführen sein. du erstellst eine liste mit rectangles und die liste gehst du mit nem foreach durch und überprüfst ob das rechteck ein anderes rechteck schneidet

private List<Rectangle> FRectangle = new List<Rectangle>(); // hier speicherst du die rechtecke rein
foreach (Rectangle rec in FRectangle)
{
 foreach (Rectangle r2 in FRectangle)
 {
   Ifcheck:
   if ((rec.IntersectsWith(r2)) && (rec != r2))  // hoffe das geht so
   {
     //hier kannste dann r2 verschieben und die if nochma prüfen. nochmals überprüfen zb mit goto
     GoTo Ifcheck; // sollte klappen
   }
 }
} // ungetestet und nur schnell erstellt ohne großartig nachzudenken ^^!

das war nur als anregung gedacht.. falls dus doch nich hinkriegst, setz ich mich morgen früh evtl mal ran.. das ganze hört sich recht spannend an ;D

mfg

Hallo thejudge,

naja, um ein Uhr nacht kann man schon mal auf die merkwüdige Idee kommen, eine Schleife mit golo zu programmieren. Ich denke aber, dass diese innere Schleife ohnehin nicht nötig ist.

Hallo #coder,

das "möglichst nah" ist, was mir Sorgen macht. Insbesondere, wenn das wirklich als Optimierungsaufgabe zu verstehen ist, also z.B. das die Summe der Quadrate der Verschiebungen minimal werden muss.

Wenn es nicht optimal, sondern nur gut werden muss, könnte ich mir folgendes vorstellen: Man sucht die Karte, die am "mittigsten" liegt. Dann sucht man die Karte, die man nächsten an/auf dieser liegt. Diese Karte verschiebt man soweit entlang des Radius eines gedachten Kreises, bis es keine Überlappung mehr gibt (nicht mit Schleife, sondern des Abstand direkt ausrechnen). Dann sucht man wieder die nächstliegende Karte und verschiebt diese radial, wobei man jetzt natürlich zwei Karten als Hindernisse berücksichtigen muss und dann immer so weiter.

Vielleicht kann man sich auch ein Raster über dem Tisch denken und eine Karte immer auf den nächstliegenden freien Rasterplatz verschieben.

Vermutlich gibt es aber dafür aber auch fertige und damit ausgefeiltere Algorithmen.

herbivore

Vielen Dank für die Antworten.

das ganze dürfte recht leicht durchzuführen sein. du erstellst eine liste mit rectangles und die liste gehst du mit nem foreach durch und überprüfst ob das rechteck ein anderes rechteck schneidet Das finden der Kollisionen habe ich bisher so ähnlich gelöst mit zwei verschachtelten for Schleifen.

Die Idee von herbivore mit der mittigsten Karte zu beginnen finde ich gut und werde ich gleich mal versuchen zu implementieren.

Mit möglichst nah meinte ich, dass es schön wäre, wenn es ungefähre gelänge jede Karte nur minimal zu verschieben. Wenn dies nur annäherungsweise geschiet ist es nicht schlimm.

Jede Karte soll danach möglichst nah an dem Punkt liegen, an dem sie zuvor lag. Optimal wäre es, wenn auch möglichst wenig leerer Platz zwischen den Karten bleibt.

Diese beiden Punkte können sich - da die Karten ja zufällig verteilt wurden - sogar widersprechen.

Ein evolutionärer Algorithmus wäre auch denkbar.
Beispielsweise in der Form:1.halte keine Karte fest 1.reihe alle nicht festgehaltenen Karten zufällig aneinander 1.suche diejenige Karte, die am wenigsten bewegt wurde 1.gibt es noch Karten, die nicht festgehalten werden?
ja: gehe zu 5.
nein: fertig!

1.hältst du die gefundene Karte bereits fest?
ja: gehe zu 6.
nein: gehe zu 8.

1.suche die nach dieser Karte am wenigsten bewegte Karte 1.gehe zu 5. 1.halte diese Karte fest 1.lass alle Karten wieder los, deren Verschiebung größer ist als die der, bei 8. festgehaltenen, Karte 1.gehe zu 2.

Da es bei n Karten maximal n! (n Fakultät) verschiedene Anordnungen gibt, sollte obiger Algorithmus endlich sein.
Das Laufzeitverhalten musst du selbst ermitteln.
Sollen deine Karten nicht nur parallel ausgerichtet sein, müsstest du eine Drehung in obigen Algorithmus noch mit einbauen (beispielsweise summierte Verschiebung der oberen linken und der unteren rechten Ecke).