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.

qgis polygon

— ksatzu
źródło

Niezły problem ....

— WKT

Nie wiem, jak bym zaczął. Brzmi jak problem / algorytm Maters stopni.

— HeikkiVesanto

Jeśli możesz uzyskać dostęp do bezpłatnej wersji próbnej ArcGIS (lub pobrać bezpłatną wersję R), oprogramowanie Geospatial Modeling Environment ma gencirclesinpolys (Generate Circles In Polygons)narzędzie, które może być przydatne.

— Joseph

Szukasz narzędzia do rozwiązania problemów z pakowaniem, ale nie znam go dla QGIS

— podmrok

@Joseph Użyłem narzędzia Geospatial Modeling Environment, działa. Niestety narzędzie generuje regularny układ kół (lub sześciokąta) w granicach wielokątów, co oznacza, że kształt wyjściowy nie pokazuje (koniecznie) najlepszego rozmieszczenia cech, mam na myśli maksymalną możliwą liczbę.

— ksatzu

Odpowiedzi:

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

— pigreco
źródło

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.

— Steven Kay
źródło