Wie verteilt man Rechtecke in verschiedenen Größen horizontal?

Question

Ich habe eine Reihe von Rechtecken mit verschiedenen Größen:

Alle Rechtecken in der Y-Richtung beschränkt sind, das heißt Y-Koordinaten festgelegt sind, können sie nur entlang der X-Achse bewegt werden. Nun möchte ich horizontal alle diese Rechtecke mit einem gleichen verteilten Abstand anordnen, aber einige von ihnen (die grauen Rechtecke im Bild) sind durch die linken und rechten Nachbarn (die roten Rechtecke), aber auch durch die Rechtecke darunter eingeschränkt und darüber hinaus.

EDIT: Die Anfangsposition der Rechtecke wird sequenziell nach Zeilen definiert. Außerdem ist in meiner ersten Implementierung Versuch, ich bin Speichern in jeder Reihe auch die Anwesenheit der vertikalen Rechtecke, die zwei oder mehr Reihen überlappt, wie wie folgt:

Row 1: {id:1,w:15,h:10},{id:2,w:10,h:40},{id:3,w:10,h:40},{id:4,w:20,h:10} 
Row 2: {id:2,w:10,h:40},{id:5,w:10,h:40},{id:3,w:10,h:40},{id:6,w:10,h:10},{id:7,w:10,h:10} 
Row 3: {id:8,w:10,h:10},{id:9,w:18,h:10},{id:5,w:10,h:40},{id:10,w:10,h:10} 

I horizontal einen Algorithmus bin auf der Suche verteile alle diese Rechtecke so, dass der linke und rechte Abstand von jedem zum nächsten der gleiche ist, wie auf dem Bild.

EDIT 2: Jeder Hinweis, wie höhere Komplexität zu handhaben, würde auch geschätzt:

Answer 1

Sortieren Sie die Rechtecken von links nach rechts, ihre äußersten linken Koordinate verwendet wird, wie im Bild unten:

Dann iterieren nach rechts jedes Rechteck von links vorbei, und sehen, welche links von ihnen recht~~POS=TRUNC ecke~~POS=HEADCOMP überlappen sie vertikal wi th (d.h. Wenn Sie sie nach links verschoben haben, auf welche Rechtecke würden sie stoßen?

A und B erreichen die linke Fensterkante, ohne in andere Rechtecke zu stoßen.
C Bumps in A.
D Bumps in B.
E Bumps in A, C und D.
F Bumps in B, D und E.
G-Bumps in D, E und F.
H Unebenheiten in A, C und E.
I-Bumps in B, D und F.
J-Bumps in D, E, F und G.

verwenden diese Informationen, um eine Grafik zu bauen, wie unten gezeigt. Wenn ein Rechteck in mehrere andere Rechtecke übergeht, z. E springt in A, C und D, und diese Rechtecke sind selbst Teil derselben Verzweigung, z. A und C, dann eine Verbindung nur zu dem am weitesten rechts liegenden Rechteck, d.h. Rechteck C.

Dann Speicher jedes Breite des Rechtecks ​​in Bildpunkten in dem Graphen. Wir werden dann versuchen, das Gewicht X der Kanten zu finden, das die Breite des Raums zwischen den Rechtecken darstellt.

Um dies zu tun, müssen wir eine Anzahl von Pfaden durch das Diagramm finden. Zuerst suchen wir den längsten Weg, d.h.der Weg mit den meisten Rechtecken, ohne ihre Breite zu berücksichtigen; die in dem Beispiel ist:

linke Fensterkante → A → C → E → F → G → J
linke Fensterkante → B → D → E → F → G → J

Wir prüfen dann, welcher dieser Wege die größte kombinierte Breite hat:

linke Fensterkante → A → C → E → F → G → J = 240

Danach betrachten wir kürzeren Pfade, und sehen, ob sie eine größere Breite haben:

linke Fensterkante → A → C → E → F → I = 230
linke Fensterkante → B → D → E → F → I = 220
linke Fensterkante → A → C → E → H = 168
linke Fensterkante → B → D → E → H = 158

Im Beispiel keiner der kürzeren Pfade hat eine größere Breite. Wenn einige von ihnen dies tun würden, müssten wir auch den breitesten Weg für jede Länge in Betracht ziehen. Wie es ist, müssen wir nur auf dem Weg aussehen:

linken Fensterrand → A → C → E → F → G → J = 240

Schließen Sie diesen Pfad zum rechten Fensterrand , so dass es eine Extrakante hat; Es gibt jetzt 7 Kanten der Breite X. Die kombinierte Breite der Rechtecke beträgt 240 Pixel, wenn also das Fenster z. 450 Pixel breit, dann X = (450 - 240)/7 = 30 Pixel. Wenn es mehr Pfade zu berücksichtigen sind, würden Sie das Mindestergebnis für X. nehmen

Die Rechtecken auf dem Weg mit dem Minimalergebnis für X wird zwischen ihnen genau X Pixel Platz ; die anderen Rechtecke haben etwas Spielraum. Sie können X als Gewichtung der Kanten im längsten Pfad des Diagramms eingeben und dann mit dem Diagramm den gleichen Abstand der anderen Rechtecke berechnen. Oder Sie könnten sie einfach in die Entfernung X von ihrem linken oder rechten Nachbarn bringen. Für einen komplizierteren Fall stellen Sie sich vor, dass im Beispiel das Rechteck I 90 Pixel breit ist und das Rechteck H 120 Pixel breit ist.Diese würden sich die Wege:

6 Rechtecke:
linken Fensterkante → A → C → E → F → G → J = 240
linken Fensterkante → B → D → E → F → G → J = 230

5 Rechtecke:
linke Fensterkante → A → C → E → F → I = 254
linke Fensterkante → B → D → E → F → I = 244

4 Rechtecken:
linke Fensterkante → A → C → E → H = 250
linke Fensterkante → B → D → E → H = 240

Dann

die Pfade zu berücksichtigen wären:

linke Fensterkante → A → C → E → F → G → J = 240

, weil es das breiteste der Pfade mit den meisten (6) Rechtecken und:

linke Fensterkante → A → C → E → F → I = 254

weil es das breiteste der Pfade mit 5 Rechtecken und ist breiter als der 6-Rechteck-Pfad.

(Der breiteste 4-Rechteck-Pfad ist breiter als der 6-Rechteck-Pfad, aber nicht breiter als der 5-Rechteck-Pfad, sodass er ignoriert werden kann.)

Diese Bedingungen ergibt:

240 + 7 × X = W
254 + 6 × X = W

290 Also für Fensterbreite, würde diese geben:

240 + 7 × X = 290 → X = 7
254 + 6 = 290 X × → X = 6

So Pfad A → C → E → F → I die Breite der Räume bestimmt, bei 6 Pixeln.

Aber für Fensterbreite 390, dass würde:

240 + 7 × X = 390 → X = 21
254 + 6 × X = 390 → X = 22

also jetzt Pfad A → C → E → F → G → J bestimmt die Breite der Leerzeichen bei 21 Pixel.