Najbliższy zgrupowany wybór sąsiadów w QGIS

14

Mam listę zawierającą ponad 100 000 punktów w formacie lat / long, które zaimportowałem do qgis.

Teraz staram się pogrupować wszystkie te punkty w grupy ramek i przez to zasadniczo mam na myśli, że chcę podzielić mapę na ramki ograniczające.

Moje wymagania są następujące:

  • żadna grupa w pudełku nie powinna mieć MNIEJ NIŻ 100 i NIE PONAD 200 PUNKTÓW
  • żaden punkt nie powinien znajdować się w więcej niż jednej grupie
  • wszystkie punkty powinny opierać się na najbliższym sąsiadu

Jak mogłem to osiągnąć za pomocą qgis?

Zakładam, że można przekazać niestandardowy kod zapytania i zapisać wyniki lub pola utworzone jako plik shapefile, prawda? Czy ktoś mógłby wyjaśnić, jak można to zrobić i jak wyglądałby kod?

Jak wspomniano, moim celem jest wyświetlenie szeregu kwadratowych pól wyświetlanych jako warstwa pliku kształtów, gdzie w każdym polu jest nie mniej niż 100 właściwości i nie więcej niż 200.

qgis postgis postgresql sql proximity NetConstructor.com
źródło
6
Wszystkim, którzy oznaczyli to pytanie jako „ulubione”: dlaczego też go nie głosować? Można by pomyśleć, że twoje ulubione pytanie powinno być dobrym pytaniem.
podmroku
1
Dlaczego potrzebujesz boksu? Jeśli utworzysz pola na podstawie liczby, i tak będą miały różne rozmiary, więc nie ma mowy o kafelkowaniu. Prawdopodobnie łatwiej jest pogrupować je w wielokąty (np. Wypukły kadłub).
diciu
@diciu dzięki za odpowiedź. Tak, wydaje mi się, że wypukły kadłub byłby w porządku, ponieważ mógłbym później przekształcić je w pudła. Jakiego kodu musiałbym użyć, aby to zrobić przy użyciu wypukłego kadłuba?
NetConstructor.com
2
Jeśli używasz wypukłych kadłubów, ramki ograniczające (otaczające kadłuby) będą się nakładać, a twoje wymaganie, aby punkt był w jednym BBOX, nie będzie już spełnione. Wypukłe kadłuby nie działają jako pośredni krok w kierunku BBOX, ale raczej jako zamiennik. I nawet wtedy stworzenie ogólnego rozwiązania będzie raczej zaangażowane.
diciu

Odpowiedzi:

13

Mogę zapewnić ci część drogi, zakładając, że wymyśliłeś, jak poprosić o (a) najbardziej wysuniętą na wschód połowę zestawu punktów i (b) najbardziej wysuniętą na północ połowę zestawu punktów. Z tych można oczywiście łatwo uzyskać (c) najbardziej wysuniętą na zachód połowę lub (d) najbardziej wysuniętą na południe połowę. (Nie znam QGIS, ale jednym ze sposobów na zrobienie (a) jest w ogóle zapytanie o środkową współrzędną x, a następnie pobranie wszystkich punktów, których współrzędne x przekraczają tę wartość. Rozwiązania dla (b) - (d) są podobne .)

Korzystając z tej możliwości, rozwiązanie uzyskuje się z łatwą rekurencją. Aby to opisać, załóżmy, że istnieje procedura Halfimplementująca poprzednie operacje, która wymaga dwóch argumentów: pierwszy to zbiór punktów, a drugi to kod równy, truegdy pożądane jest dzielenie wschód-zachód, i równy jest falseinny. Zwraca dwa podzbiory danych wejściowych, które dzielą go zgodnie z żądaniem.

Procedure Box(P: set of points, i: boolean, n: integer)
Begin
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
    Else
        Q = {P}
    Endif
    Return Q
End

W tym pseudokodzie R i S partycja P; Pole (R,! I, n) jest podziałem R w kierunku ortogonalnym , Pole (S,! I, n) jest podziałem S w kierunku ortogonalnym, „+” oznacza uformowanie połączenia teoretycznego i {} oznacza zestaw. (Naprzemienny kierunek podziału tworzy ramki zamiast pasków.) Parametr n określa minimalny rozmiar grupy w partycji; maksymalny rozmiar to 2 n .

Przykład

Tutaj, jako ilustracja, jest zestaw P z 12 891 losowych punktów podzielonych Box(P,true,100)na grupy o wielkości od 100 do 200. Algorytm tworzy 128 pól, z których 37 ma 100 punktów, a 91 ma 101 punktów.

Whuber
źródło
2
Algorytm jest wydajny. Działając na jednym rdzeniu, przetworzył dziesięć razy więcej punktów (128 910) w 18 sekund. Skaluje się jako O (n log (n) log (n)) dla n punktów. (Można by poprawić jeden z tych czynników log (n), ale wysiłek raczej nie będzie opłacalny.)
whuber
1
@W Czy użyłeś sortowania leksykograficznego, aby ułatwić podział współrzędnych punktu?
2
@ whuber to jest niesamowite
dassouki,
1
@ Dan Sortowanie leksykalne pomogłoby, ale nie jest konieczne. Zauważ, że medianę n wartości można znaleźć w czasie O (n) (nie O (n log (n))), więc podział punktów na połówki wschód-zachód lub połówki północ-południe jest asymptotycznie równy O (n ) obliczenia.
whuber