Programowo rozmieszczaj prostokątne obiekty UI w abstrakcyjny sposób, bez przerw.

Question

Biorąc pod uwagę zbiór 50, obrazów o różnych szerokościach i wysokościach, w jaki sposób można je programowo uporządkować w ciekawy * abstrakcyjny sposób? (Patrz zdjęcie poniżej)

• Przez interesujący To znaczy, nie ma dużych różnic, a nie łatwo odróżnić wiersze lub kolumny (ujemna przestrzeń tworzy wiele T-podobnych skrzyżowaniach).

Dla mojego konkretnego przypadku wszystkie obrazy mają ustawiony maksymalny wymiar 150 pikseli, co może oznaczać, że wysokość LUB szerokość wynosi maks. 150 pikseli (może być 150 pikseli na 450 pikseli lub 378 na 150 pikseli).

Wydaje się to może to być klasyczne wyzwanie programowania, ale jestem znalezienie tematu trudno Google ...

EDIT: Zmieniono obraz, aby pokazać, że nie ma żadnych ograniczeń, w jaki sposób ogólny układ musi być (nie musi zmieścić się w ustawionym obszarze)

Answer 1

Twój problem to NP-Hard.

This thread pokazuje, że nawet z jednym typem prostokąta nXm trudno jest znaleźć NP, jeśli istnieje rozwiązanie, więc waszym bardziej ogólnym problemem jest oczywiście NP-Hard [tylko jeden typ prostokąta to prywatna sprawa tego problemu]

można spróbować rozwiązania backtracking jeśli po zoptymalizowane rozwiązanie, lub heurystycznego podejścia w genetic algorithms lub hill climbing, który będzie szybciej - ale zazwyczaj znaleźć non optymalny rezultat.

Answer 2

Jeżeli nie sprzeciwiają się jQuery plugin, można to sprawdzić - http://masonry.desandro.com/

Answer 3

zbudowałem coś podobnego do tego (choć nie jest to prawdopodobnie najbardziej wyrafinowane rozwiązanie). Moim podejściem było użycie quadtree do uporządkowania prostokątów, które umieściłem na płótnie. Następnie po prostu chodziłem po spiralnym punkcie środkowym, próbując umieścić nowe prostokąty i używając kwadratu do wykrywania kolizji. W przypadku wykrycia kolizji przesuwałbym prostokąt, który próbowałem umieścić na krawędzi prostokąta, który zderzył się z tym, który znajdował się najdalej od środka i powtórzył proces sprawdzania kolizji.

Znowu, prawdopodobnie nie jest to najbardziej wyrafinowana metoda, która powoduje pozostawienie większych odstępów między prostokątami (granice między nimi nie są jednolite), ale według mojego gustu daje to dobre wyniki.