Poszukujesz algorytmu, aby umieścić maksymalną liczbę punktów w ograniczonym obszarze w minimalnym odstępie?

17

Mam warstwę wielokąta, która opisuje ograniczenie; Chcę dodać punkty w tym obszarze. Chcę dodać jak najwięcej punktów, ale muszą one mieć między nimi minimalny odstęp. Czy można to zrobić za pomocą GIS?

Aby to wyjaśnić, najlepiej byłoby wygenerować uporządkowaną siatkę, ponieważ gwarantowałoby to najwięcej punktów. Jednak ograniczenie rzadko na to pozwala i może być wskazane usunięcie punktów, aby umożliwić przesunięcie w celu lepszego dopasowania do ograniczenia.

algorithm point Matthew Snape
źródło
1. Tak 2. Czy chcesz losowy czy zamówiony (siatka)?
Brad Nesom
Wydaje się, że są dwa pytania. Czy chcesz, aby algorytm robił to poza oprogramowaniem? A może chcesz wiedzieć, jaki system GIS może to zrobić?
Brad Nesom
1
Czy punkty są tak ograniczone, że muszą być> = minimalna odległość od granicy wielokąta? Jeśli tak, pytanie może zostać bardziej jednoznacznie określone w następujący sposób: Jak spakować maksymalną liczbę okręgów do wielokąta?
Kirk Kuykendall
W jakiś sposób powiązane: gis.stackexchange.com/q/4927/162
julien
1
@qva Nie, nie ma, ponieważ dokładne rozwiązania, które można znaleźć, są asymetryczne i trudne do uzyskania nawet dla prostych kształtów, takich jak prostokąty. Najlepsze metody obliczeniowe, jakie znalazłem, oparte są na przestrzennym symulowanym wyżarzaniu (i działają bardzo dobrze, mimo że wymagają dużo obliczeń). Korzystając z nich, szukałem rozwiązań dla wielu wielokątów o różnych kształtach. Oczywiste jest, że granice wielokątów kontrolują rozwiązania blisko granic; głęboko w środku mają tendencję do zbliżania się do sześciokątnych wypełnień dysków.
whuber

Odpowiedzi:

5

Myślę, że można to uznać za problem „pakowania”.

Jeśli tak, możesz wypróbować Algorytm genetyczny, być może podobny do tego w „ Algorytmach genetycznych do pakowania wieloboków” .

Kirk Kuykendall
źródło
Ciekawe referencje, dzięki. Szybki rzut oka sugeruje, że algorytm papieru wymaga, aby wielokąty były prostokątami. Czy wiesz, czy można go uogólnić na dowolne wielokąty?
whuber
9

Nie znam na to żadnego narzędzia GIS, ale mam pomysł na algorytm.

Po pierwsze, można uzyskać przybliżenie maksymalnej liczby punktów za pomocą tego wzoru:

Nb = 4.A / Pi.d^2

(gdzie Ajest obszar wielokąta id minimalna odległość odstępu).

Następnie, aby spróbować zlokalizować te punkty w wielokącie, najlepszym wzorem nie jest kwadratowa siatka, ale sześciokątna siatka. Widzieć:

siatka kwadratowa vs sześciokątna

Wreszcie, niektóre techniki optymalizacji wykorzystujące modele siły mogą być wykorzystane do udoskonalenia względnego pozycjonowania punktów.

NB: Jest to dobrze znany problem w krystalografii .

Julien
źródło
gis narzędzie do tego ... geo-kreator ian-ko.com losowy punkt w wielokącie.
Brad Nesom
1
Dzięki! Ale pytanie nie dotyczy dokładnie losowych punktów w wielokącie, prawda?
Julien
Jako wstępne przybliżenie szybkie i brudne, sześciokątne pakowanie działa dobrze. Jednak prawie nigdy nie jest optymalna. Spodziewałbym się, że potencjalna poprawa będzie proporcjonalna do długości obwodu wielokąta, więc w przypadku wielokątów nieporęcznych z wieloma punktami nie jest to złe podejście.
whuber
6

Zobacz wątek na /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . W szczególności zwróć uwagę na odniesienie (w komentarzu) do „Proces dysku Poissona” i przeszukaj Internet. Związek z bieżącym pytaniem polega na tym, że jeśli możesz równomiernie rozdzielić określoną liczbę punktów, możesz systematycznie zwiększać tę liczbę, dopóki nie będzie można umieścić więcej punktów w wielokącie, co rozwiązuje problem maksymalizacji liczby punktów podlegających minimalna odległość wymagana. (Technicznie dwa problemy to problemy z podwójną optymalizacją, w których cele i ograniczenia są ze sobą zamienione).

Whuber
źródło
0

Rozwiązaniem muszą być trójkąty równoboczne, http://en.wikipedia.org/wiki/Equilateral_triangle . Jedyne pytanie dotyczy długości boków i „przesunięcia xy” w stosunku do twojego wielokąta.

(taki sam jak sześciokątna siatka wymieniona poniżej)

Uffe Kousgaard
źródło
1
Jest to prawdą tylko w nieskończonej płaszczyźnie. Granica skończonego wielokąta poważnie ogranicza konfigurację. Kiedy jest wiele punktów, w przybliżeniu tworzą trójkąty równoboczne.
whuber