Jak obliczyć, ile wielokątów mogę umieścić w wielokącie?

Zwykle używam qgis. Mój problem wyjaśniam na przykładzie: jest las (nieregularna geometria1) i jedno drzewo (geomery2). Chcę poznać maksymalną liczbę drzew, które może zawierać las. Co więcej, chcę uzyskać plik kształtów o najlepszym rozmieszczeniu tych drzew w lesie.

Wypróbuj aplikację online svgnest.com/

kroki: 1. svg tworzy plik (jak na rysunku 1); 2. Przejdź do linku i prześlij svg; 3. Wybierz myszą wielokąt pojemnika; 4. start

po kilku iteracjach możesz zablokować i pobrać plik svg (patrz rysunek 2)

Uwaga: wielokąt i okręgi muszą znajdować się w tym samym pliku svg

Ciekawy problem!

Zrobiłem podobnie z nieregularnymi wielokątami (w tym przypadku budynki były zapakowane, aby się nie nakładały)

Używane postgresql i postgis oraz python. Trudny algorytm był

• Znajdź losowy punkt w obwiedni wielokąta (ST_Envelope)
• Jeśli wskazuje poza wielokąt, cofnij się o jeden krok
• Utwórz geometrię drzewa wyśrodkowanego na tym losowym punkcie
• Jeśli pokrywa się to z istniejącym umieszczonym drzewem (ST_Overlaps), wróć, aby rozpocząć
• Dodaj drzewo w punkcie
• Wróć, aby rozpocząć

Nie mogę zagwarantować, że da to globalny optymalny, do tego potrzebny byłby algorytm „upakowania kół” (jak wspomnieli inni).

Będzie trwać wiecznie, więc będziesz musiał wstawić trochę kodu, aby zdecydować, kiedy wyjść, np

• gdy łączna powierzchnia umieszczonych drzew stanowi pewien procent powierzchni wielokąta
• gdy potrzeba więcej niż N iteracji, aby znaleźć nie nakładające się drzewo.

Według Circle Packing na Wikipedii najlepszą gęstość upakowania uzyskuje się za pomocą sześciokątnej siatki. Możliwe jest utworzenie takiej siatki za pomocą MMQGIS, którego odstępy są oparte na wielkości drzew, które, jak zakładam, są identyczne. Następnie umieszczając drzewo na każdym wierzchołku. Ale wtedy masz problem z wiedzą, gdzie umieścić siatkę, aby zmaksymalizować liczbę drzew.