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

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.

— NetConstructor.com
źródło

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

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

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

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

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

@W Czy użyłeś sortowania leksykograficznego, aby ułatwić podział współrzędnych punktu?

@ whuber to jest niesamowite

— dassouki,

@ 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