Biorąc pod uwagę wiele wielokątów, które nakładają się na wiele sposobów, chciałbym wyeksportować z tych funkcji wszystkie wielokąty, które nie pokrywają się iteracyjnie.
Produkt miałby szereg funkcji bez nakładania się, które po zsumowaniu składają się na oryginał.
Produkty mogłyby następnie zostać wykorzystane jako dane wejściowe do statystyki strefowej, a byłoby to znacznie szybsze niż iteracja statystyki strefowej dla każdego wielokąta.
Próbowałem to zakodować w ArcPy bez powodzenia.
Czy kod do tego celu już istnieje?
arcpy
algorithm
overlapping-features
ndimhypervol
źródło
źródło
Odpowiedzi:
Jest to problem z kolorowaniem wykresów .
Przypomnij sobie, że kolorowanie wykresu to przypisanie koloru do wierzchołków wykresu w taki sposób, że żadne dwa wierzchołki, które dzielą krawędź, również nie będą miały tego samego koloru. W szczególności (abstrakcyjne) wierzchołki wykresu to wielokąty. Dwa wierzchołki są połączone (niekierowaną) krawędzią, gdy przecinają się (jako wielokąty). Jeśli weźmiemy jakieś rozwiązanie problemu - który jest sekwencją (powiedzmy k ) rozłącznych kolekcji wielokątów - i przypiszemy unikalny kolor do każdej kolekcji w sekwencji, uzyskamy k -kolorowanie wykresu . Pożądane jest znalezienie małego k .
Ten problem jest dość trudny i pozostaje nierozwiązany w przypadku dowolnych grafów. Rozważ przybliżone rozwiązanie, które można łatwo kodować. Algorytm sekwencyjny powinien zrobić. Algorytm Welsha-Powella jest chciwym rozwiązaniem opartym na malejącej kolejności wierzchołków według stopnia. Przetłumaczone na język oryginalnych wielokątów, najpierw posortuj wielokąty w porządku malejącym względem liczby innych wielokątów, które się na siebie nakładają. Pracując w porządku, nadaj pierwszemu wielokątowi początkowy kolor. Na każdym kolejnym kroku spróbuj pokolorować następny wielokąt istniejącym kolorem: wybierz kolor, który nie jestużywany już przez któregokolwiek z sąsiadów tego wielokąta. (Istnieje wiele sposobów wyboru spośród dostępnych kolorów; wypróbuj ten, który był najmniej używany, lub wybierz jeden losowo.) Jeśli następnego wielokąta nie można pokolorować istniejącym kolorem, utwórz nowy kolor i pokoloruj go tym.
Po uzyskaniu kolorowania za pomocą niewielkiej liczby kolorów wykonaj statystyki strefowe kolor po kolorze: z uwagi na konstrukcję masz pewność, że żadne dwa wielokąty danego koloru nie zachodzą na siebie.
Oto przykładowy kod w
R
. (Kod w Pythonie nie różni się zbytnio.) Po pierwsze, opisujemy nakładanie się siedmiu pokazanych wielokątów.Oznacza to, że wielokąty 1 i 2 nakładają się, podobnie jak wielokąty 2 i 3, 3 i 4, ..., 1 i 7.
Sortuj wierzchołki według malejącego stopnia:
(Surowy) algorytm sekwencyjnego kolorowania używa najwcześniejszego dostępnego koloru, który nie jest jeszcze używany przez nakładający się wielokąt:
Zainicjuj struktury danych (
colors
icolor.next
) i zastosuj algorytm:Podziel wielokąty na grupy według kolorów:
Dane wyjściowe w tym przykładzie wykorzystują cztery kolory:
Podzielił wielokąty na cztery niezachodzące na siebie grupy. W tym przypadku rozwiązanie nie jest optymalne ({{3,6,5}, {2,4}, {1,7}} to trójkolorowy wykres). Ogólnie rzecz biorąc, rozwiązanie, które dostaje, nie powinno być jednak takie złe.
źródło
Metodologia zalecana przez #whuber zainspirowała mnie do obrania nowego kierunku, a oto moje arkadowe rozwiązanie w dwóch funkcjach. Pierwsze, zwane countOverlaps, tworzy dwa pola: „overlaps” i „ovlpCount”, aby zapisać dla każdego poli, które pokrywały się z nim, i ile wystąpiło. Druga funkcja, explodeOverlaps, tworzy trzecie pole, „expl”, które daje unikalną liczbę całkowitą dla każdej grupy nie nakładających się polis. Użytkownik może następnie wyeksportować nowe fc na podstawie tego pola. Proces jest podzielony na dwie funkcje, ponieważ myślę, że narzędzie countOverlaps może się przydać. Proszę wybaczyć niechlujność kodu (i nieostrożną konwencję nazewnictwa), ponieważ jest to dość wstępne, ale działa. Upewnij się także, że „idName” pole reprezentuje pole z unikalnymi identyfikatorami (testowane tylko z identyfikatorami liczb całkowitych). Dziękuję fanom za udostępnienie mi ram niezbędnych do rozwiązania tego problemu!
źródło
countOverlaps
odpowiada dwóm wierszomnbrhoods <- sapply(vertices, neighbors); degrees <- sapply(nbrhoods, length)
w moim kodzie:degrees
jest liczbą nakładania się. Oczywiście twój kod jest dłuższy, ponieważ odzwierciedla większość analiz GIS, które są brane za pewnik w moim rozwiązaniu: mianowicie, że najpierw identyfikujesz, które wielokąty zachodzą na siebie, i że na końcu używasz rozwiązania do generowania zestawów danych wieloboków. Dobrym pomysłem byłoby zamknięcie obliczeń teoretycznych na wykresach, więc jeśli kiedykolwiek znajdziesz lepszy algorytm kolorowania, łatwo byłoby go podłączyć.Minęło trochę czasu, ale użyłem tego kodu do własnej aplikacji i działa świetnie - dziękuję. Ponownie napisałem część, aby ją zaktualizować, zastosować do linii (z tolerancją) i znacznie przyspieszyć (poniżej - korzystam z 50 milionów przecinających się buforów i zajmuje to tylko kilka godzin).
źródło
W takich przypadkach zazwyczaj używam następującej metody:
Wierzę, że wynik będzie taki, jaki chciałeś, i możesz nawet policzyć liczbę nakładek. Nie wiem, czy pod względem wydajności będzie to dla Ciebie lepsze, czy nie.
źródło