Gruppierte Auswahl des nächsten Nachbarn in QGIS

14

Ich habe eine Liste mit über 100.000 Punkten im Lat / Long-Format, die ich in qgis importiert habe.

Ich versuche hier nun, alle diese Punkte in Box-Gruppen zu gruppieren. Damit meine ich im Wesentlichen, dass ich die Karte in Begrenzungsboxen aufteilen möchte.

Meine Anforderungen sind folgende:

  • Keine Box-Gruppe sollte weniger als 100 und nicht mehr als 200 Punkte haben
  • Kein Punkt sollte in mehr als einer Gruppe liegen
  • Alle Punkte sollten auf dem nächsten Nachbarn basieren

Wie könnte ich das durch qgis erreichen?

Ich gehe davon aus, dass man einen benutzerdefinierten Abfragecode übergeben und die Ergebnisse oder die als Shapefile erstellten Felder korrekt speichern kann? Könnte jemand bitte erklären, wie dies geschehen könnte und wie der Code aussehen würde?

Wie bereits erwähnt, ist es mein Ziel, eine Reihe quadratischer Kästchen als Shapefile-Ebene anzuzeigen, in der sich in jedem Kästchen nicht weniger als 100 und nicht mehr als 200 Eigenschaften befinden.

NetConstructor.com
quelle
6
An alle, die diese Frage als "Favorit" markiert haben: Warum nicht auch? Man würde denken, dass Ihre Lieblingsfrage eine gute Frage sein sollte.
Underdunkel
1
Warum brauchst du Boxen? Wenn Sie Kästchen auf der Grundlage der Anzahl erstellen, werden sie ohnehin unterschiedliche Größen haben, sodass Kacheln nicht in Frage kommen. Es ist wahrscheinlich einfacher, sich in Polygone (dh konvexe Hülle) zu gruppieren.
Dienstag,
@diciu danke für die Antwort. Ja, ich denke, ein konvexer Rumpf wäre in Ordnung, da ich diese anschließend in Kisten verwandeln könnte. Welchen Code müsste ich verwenden, um den konvexen Rumpfansatz zu verwenden?
NetConstructor.com
2
Wenn Sie konvexe Rümpfe verwenden, überlappen sich Ihre Begrenzungsrahmen (einschließlich der Rümpfe), und Ihre Anforderung, dass ein Punkt in einer einzelnen BBOX enthalten sein soll, ist nicht mehr erfüllt. Konvexe Rümpfe dienen nicht als Zwischenschritt zur BBOX, sondern als Ersatz. Und selbst dann wird das Erstellen einer generischen Lösung ziemlich aufwändig sein.
Dienstag,

Antworten:

13

Ich kann Sie ein Stück dahin bringen, indem ich annehme, Sie haben herausgefunden, wie Sie (a) die östlichste Hälfte eines Punktesatzes und (b) die nördlichste Hälfte eines Punktesatzes anfordern können. Von diesen können Sie natürlich leicht (c) die westlichste Hälfte oder (d) die südlichste Hälfte erhalten. (Ich kenne QGIS nicht, aber eine Möglichkeit, (a) im Allgemeinen zu tun, besteht darin, die mittlere x-Koordinate anzufordern und dann alle Punkte abzurufen, deren x-Koordinaten diese überschreiten. Die Lösungen für (b) - (d) sind ähnlich .)

Unter Verwendung dieser Fähigkeit wird die Lösung mit einer einfachen Rekursion erhalten. Um es zu beschreiben, nehmen wir an, dass es eine Prozedur gibt Half, die die vorhergehenden Operationen implementiert, die zwei Argumente akzeptiert: Die erste ist eine Menge von Punkten und die zweite ist ein Code, der gleich ist, truewenn eine Ost-West-Partitionierung gewünscht wird, und gleich ist falseansonsten. Es gibt zwei Teilmengen seiner Eingabe zurück, welche Partition es angefordert hat.

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

In diesem Pseudocode sind R- und S-Partition P; Box (R,! I, n) ist eine Partition von R in der orthogonalen Richtung , Box (S,! I, n) ist eine Partition von S in der orthogonalen Richtung, "+" bedeutet die satztheoretische Vereinigung und {} bezeichnet eine Menge. (Wenn Sie die Aufteilungsrichtung ändern, werden eher Kästchen als Streifen erstellt.) Der Parameter n gibt die Mindestgröße einer Gruppe in der Partition an. Die maximale Größe beträgt 2 n .

Beispiel

Hier ist zur Veranschaulichung eine Menge P von 12.891 zufälligen Punkten, die Box(P,true,100)in Gruppen zwischen 100 und 200 in der Größe unterteilt sind. Der Algorithmus erstellt 128 Felder, von denen 37 100 Punkte und 91 101 Punkte haben.

whuber
quelle
2
Der Algorithmus ist effizient. Es lief auf einem einzigen Kern und verarbeitete in 18 Sekunden zehnmal so viele Punkte (128.910). Es skaliert als O (n log (n) log (n)) für n Punkte. (Es könnte verbessert werden, einen dieser Faktoren von log (n) zu entfernen, aber es ist unwahrscheinlich, dass sich der Aufwand lohnt.)
whuber
1
@W Haben Sie eine lexikografische Sortierung verwendet, um die Aufteilung der Punktkoordinaten zu erleichtern?
2
@whuber das ist
super
1
@Dan Eine lexikalische Sortierung würde helfen, ist aber nicht notwendig. Es ist zu beachten, dass ein Median von n Werten in der O (n) -Zeit (nicht in der O (n log (n)) -Zeit) gefunden werden kann, sodass die Aufteilung von Punkten in Ost-West-Hälften oder Nord-Süd-Hälften asymptotisch ein O (n) ist ) Berechnung.
whuber