Określ minimalną liczbę wielokątów z pliku kształtu, aby pokryć obszar zainteresowania

10

Mam dużą liczbę plików kształtów reprezentujących obszary zainteresowania do analizy, która zostanie przeprowadzona przy użyciu różnych źródeł zdjęć satelitarnych (IKONOS, RapidEye itp.). Niestety, obrazy nie używają na przykład systemu ścieżek takiego jak Landsat, więc zakres jest bardzo różny.

Do każdego AOI przypiąłem pliki kształtów reprezentujące zakres różnych zakupów obrazów, z których wszystkie zostały już uznane za dopuszczalne. Niektóre z tych plików kształtów mają 500 lub więcej wielokątów.

Muszę znaleźć podejście, najlepiej takie, które można zautomatyzować (najlepiej Python i ArcInfo 10, najlepiej FOSS również będzie akceptowalne), aby określić najmniejszą liczbę wielokątów dla każdego z moich obszarów zainteresowania.

— Chad Hawkins
źródło

3

Ogólnie rzecz biorąc, jest to trudny problem NP, więc prawdopodobnie wymaga potężnego oprogramowania. Jednym z podejść jest ułożenie go w postaci liniowego programu liczb całkowitych: wielokąty dzielą AOI na wielokąty „atomowe”, a każdy oryginalny wielokąt całkowicie pokrywa lub nie obejmuje każdego wielokąta atomowego. Informacje te można zakodować w wektorach binarnych. Próbujesz zminimalizować liczbę takich wektorów, których suma wynosi 1 lub więcej w każdym komponencie. Przykłady przykładów rozwiązania podobnych problemów można znaleźć na mathematica.stackexchange.com/a/6888 i gis.stackexchange.com/a/27678 .

— whuber

3

Jak zauważył whuber, uogólnienie tego rodzaju problemu w celu znalezienia rozwiązania wysokiej jakości byłoby trudne, ale takie podejście może doprowadzić cię wystarczająco blisko bez większego wysiłku. Oto pseudo kod oparty na następujących założeniach:

Obszar zainteresowania A

Zestaw wielokątów Y, które całkowicie pokrywają A

Start loop
 Iterate through Y
   Select the polygon x from Y that has greatest area of intersection with A

 Clip A with polygon x
 Remove x from Y 
 If A is null then end program

Chodzi o to, że iteracyjnie redukujesz obszar zainteresowania za pomocą zasięgu satelity, który ma największe nakładanie się z pozostałym obszarem zainteresowania. AOI zmniejsza się z każdą iteracją, dopóki nic nie zostanie. Prawdopodobnie nie będzie to optymalne rozwiązanie, ale powinno być rozsądne i działać dość szybko.

— dblanchett
źródło

0

Ok, więc masz obszar A, który reprezentuje pewien obszar i kilka zakresów zdjęć, które można zdefiniować jako zbiór Y.

Jeśli mam to poprawnie, możesz wykonać kilka różnych funkcji:

przycinanie zakresu obrazów przez obszar A
Wykonaj zaznaczenie według lokalizacji przy użyciu wielokątów Extent, a opcja całkowicie zawiera

Następnie możesz zbadać obszary każdego z nich i ustalić, czy masz samobierające się wielokąty, wykonując sortowanie geometrii przestrzennej za pomocą ArcPy i kursorów.

Mam nadzieję, że to pomoże.

— podstawa kodu 5000
źródło

1

Czy możesz bardziej szczegółowo omówić sposób używania kursorów? Wchodząc do środka, zakładałem, że jakoś do tego dojdzie, ale nie byłem w stanie opracować metodologii. Rozważałem rozpoczęcie od n górnych wielokątów w obszarze, wyeliminowanie z pozostałych wielokątów całkowicie zamkniętych i kontynuowanie iteracji w ten sposób. To może być początek, ale oczywiście te wielokąty o największych obszarach mogą nie mieć bardzo różnych rozmiarów.

— Chad Hawkins