Rechtecke auslegen, Kollisionen vermeiden (Algorithmushilfe)
Ich habe eine (große) horizontal scrollende Ansicht und eine Reihe von Rechtecken, die ich darauf positionieren möchte. Jedes Rechteck hat eine gewünschte horizontale Position, kann jedoch bei Bedarf von dieser Position um bis zu einem bestimmten Betrag (eine Konstante, K) abweichen. Die Rechtecke dürfen nicht überlappen. Die vertikale Position der Rechtecke ist beliebig (natürlich auf die Höhe der Ansicht beschränkt).
Idealerweise möchte ich, dass die Größe der Rechtecke variabel ist ... Ich denke, wenn das nicht möglich ist, kann ich die Größe in nur einer Dimension variieren lassen.
Nun wird es Unmöglichkeiten in diesem Layout geben: Da es nur einen gewissen vertikalen Platz gibt und sie nur K Pixel von ihrem Ideal horizontal wegbewegen können, können wahrscheinlich nicht alle Rechtecke gezeichnet werden. Um damit umzugehen, hat jedes Rechteck eine Priorität (P), und die niedrigerwertigen Prioritäten sollten zuerst weggelassen werden. (Sie können davon ausgehen, dass dies nicht eindeutig ist und Sie immer wissen können, welches der beiden Rechtecke die höhere Priorität hat.)
Ich bin nach konzeptionellem Algorithmus-Zeug, aber wenn Sie Besonderheiten benötigen, wird dies auf einem iPad ausgeführt, und es wird ein paar tausend (& gt; 1000, aber & lt; 10.000) Rechtecke zu berücksichtigen geben. Idealerweise möchte ich etwas, das schnell genug ist, um jedes Mal neu zu starten, wenn der Benutzer die Zoomstufe ändert, aber wenn das nicht einfach ist, kann ich die Positionen zwischenspeichern. Die Objekte sind Fotos auf einer Zeitachse und ich möchte sie ungefähr in die Nähe bringen, wenn das Ereignis passiert ist - ich gehe näher, um mehr davon zu bekommen.
Ich habe Algorithmen wie dies gesehen, die das tun nicht überschneidender Trick, aber haben nicht die gleiche Idee, dass jeder Gegenstand nur bis zu einem bestimmten Betrag bewegt werden darf. Offensichtlich können Sie ohne die letzte Einschränkung alle Elemente anzeigen, also muss ich auch wissen, an welchem Punkt keine Rechtecke mehr angezeigt werden können.
Wenn die Lösung des beschriebenen Problems zu schwierig ist, würde ich einen Vorschlag für eine pragmatischere Idee begrüßen. Wenn alles andere fehlschlägt, könnte ich immer etwas tun, wo es in der Prioritätsreihenfolge durchläuft, jedes Element an seinem gewünschten Ort rendert, wenn es möglich ist, wenn nicht, dann versuche, es vertikal zu verschieben, wenn noch nicht, dann horizontal bis zum erlaubten Limit verschieben. bevor wir zum nächsten weitergehen. Die Prioritätsreihenfolge würde bedeuten, dass wahrscheinlich eine suboptimale Lösung gefunden würde, die jedoch auf die wichtigsten Punkte gewichtet würde.
1 Antwort
Dies ist eine Möglichkeit, wie ich denke, dass dies getan werden könnte.
In Schritt 1 werden alle Positionen ermittelt, an denen das neue gelbe Rechteck platziert werden kann. Ohne Beschränkung der Allgemeinheit können wir dies als eine Liste aller möglichen X-Y-Positionen der oberen linken Ecke des Rechtecks speichern. Natürlich wird diese Liste für einen so großen Startbereich Millionen von Einträgen enthalten. Um Platz zu sparen, speichern wir diese Liste in Form von rechteckigen Bereichen.
Beispiel: Wenn unser Bildschirm Pixel von X = 0 bis X = 2999 einschließlich und von Y = 0 bis Y = 999 einschließlich hat und unser neues Rechteck eine Breite von 300 Pixel und eine Höhe von 150 Pixel hat, wird die obere linke Ecke von unser neues Rechteck kann an jeder Position von (X, Y) = (0, 0) bis (2699, 849) einschließlich erscheinen. Speichern wir das als Quadrupel, [0, 0, 2699, 849].
Wenn wir nun jedes vorhandene (rote) Rechteck auf den Bildschirm legen, werden einige dieser Möglichkeiten ausgeschlossen, da sie dazu führen würden, dass das neue (gelbe) Rechteck diese überlappt. Wenn beispielsweise ein rotes Rechteck [1100, 200, 1199, 299] vorhanden ist, kann unser gelbes Rechteck seine obere linke Ecke an keiner Position von (X, Y) = (801, 51) bis (1199, 299) haben. inklusive.
Ersetzen Sie also [0, 0, 2699, 849] durch vier rechteckige Zonen, die denselben Bereich abdecken, aber die Lücke verlassen. Es gibt viele Möglichkeiten, dies zu tun, aber hier ist eines: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849 ].
Fügen Sie weitere rote Rechtecke zum Bildschirm hinzu. Jedes Mal, wenn eine hinzugefügt wird, subtrahieren Sie mehr Möglichkeiten von der Liste (dies führt normalerweise dazu, dass die Liste mehr, kleinere "sichere Zonen" enthält). (Dies könnte sehr zeitaufwendig sein für den Vollbildschirm mit mehr als 1000 Rechtecken; wenn Sie stattdessen nur mit dem von Ihnen erwähnten [XK, 0, X + K, H] -Raum beginnen, dann relativ wenige der 1000 + wird dies überlappen und die Berechnung wird viel schneller gehen.) Dieser Code sollte mit großer Sorgfalt und einem Stapel von Unit Tests geschrieben werden, da Fencepost Fehler reichlich vorhanden sind.
Das Endergebnis ist eine vollständige Liste der möglichen Positionen auf dem Bildschirm, an denen die obere linke Ecke Ihres neuen gelben Rechtecks platziert werden kann, ausgedrückt in Form einer Liste von rechteckigen Zonen.
Schritt 2: Sehen Sie sich diese Liste an und wählen Sie den gewünschten Ort aus. Jede rechteckige Zone, die Ihre ideale vertikale Linie schneidet, hat Priorität. Aber es ist möglich, dass es keine gibt. In diesem Fall liegt es an Ihnen, die am meisten bevorzugte Option aus den Zonen auszuwählen, die auf der linken Seite liegen und den Zonen, die auf der rechten Seite der idealen Linie liegen. Als Hinweis: nur eine Ecke jeder Zone muss in jedem Fall berücksichtigt werden (die obere linke Ecke der Zonen auf der rechten Seite, die obere rechte Ecke der Zonen auf der linken Seite).