Maximaler Kreis innerhalb eines unregelmäßigen Polygons von einem zufälligen Punkt

8

Ich versuche, einen Algorithmus zum Erstellen des Kreises mit maximalem Radius innerhalb eines unregelmäßigen Polygons (eines Zensus-Trakts) basierend auf einem bestimmten Mittelpunkt des Kreises zu erarbeiten.

Die Motivation dafür ist, den Standort einer Person zu verschleiern, die eine Umfrage beantwortet hat. Ihr tatsächlicher Standort ist bekannt, muss jedoch in der Analyse verdeckt werden, um die Daten für die weitere Analyse der Öffentlichkeit zugänglich zu machen.

Wir möchten für jeden Befragten ein donutförmiges Polygon mit einem Innenradius (einfach) haben, der durch einen Außenradius begrenzt ist, der durch den Zensus-Trakt, in dem sich die Person befindet, begrenzt wird. Ihre endgültige Position wird zufällig innerhalb des Donut-Polygons platziert .

Ich habe hier viele Antworten auf ähnliche Fragen gesehen, aber nicht diese spezifische, die in diesem Fall mit einem SPEZIFISCHEN Ort beginnt.

Sobald wir den Donut festgelegt haben, können wir die Position der einzelnen Antwort innerhalb des Polygons zufällig bestimmen. Das ist relativ einfach ...

Vielen Dank für Ihre Ideen, meine schienen bisher ziemlich brutal und rechnerisch "teuer" oder ineffizient zu sein ...

Percy
quelle
1
Ist es nicht nur der kürzeste Abstand zwischen dem bestimmten Ort und der Grenze des gewünschten Polygons?
Nicklas Avén
Welche Software oder Programmiersprache verwenden Sie?
Pablo
Warum nicht einfach den gewünschten Ring mit dem Trakt schneiden? Besser noch, es gibt keinen Grund, kreisförmige Formen zu verwenden - Sie könnten genauso gut einen quadratischen Ring verwenden, was zu einer schnelleren Ausführung führen würde.
whuber
3
Es scheint wenig oder keinen Konsens zu geben . Eine Übersicht über einige Methoden finden Sie hier ab S. 34 . Auf unserer Website wurde eine ausgefeilte Methode vorgeschlagen . Eine kürzlich durchgeführte internationale Arbeitsgruppe befasste sich mit vielen verwandten Themen. Eine aktuelle Überprüfung von Mathews & Harel kann nützlich sein.
whuber
3
@whuber, vielen Dank! Ich gehe davon aus, dass Sie derselbe Bill Huber sind, der seit meinem ersten Einsatz von GIS im Jahr 1998 Hilfe und Quellcode veröffentlicht hat. Ich habe alle Ihre Avenue-Skripte geliebt und viel von ihnen gelernt (und ich gehe davon aus, dass das unten genannte Programm ArcView ist erstaunlich, wie schnell es heutzutage läuft !!!). Ich wollte Sie nur wissen lassen, wie sehr Sie in der Gemeinschaft der GIS-Praktiker geschätzt werden! Vielen Dank für all Ihre jahrelangen tollen Ratschläge!
Percy

Antworten:

3

Eine einfache Methode zum Verschieben von Orten innerhalb solcher Ringe nutzt eine gerasterte Darstellung des Abstands zur Traktgrenze. Beginnend mit einer polygonalen Darstellung der Zensus-Traktate (was üblich ist),

  1. Konvertieren Sie dies in die Polygongrenzen (eine Polylinienebene).

  2. Berechnen Sie das euklidische Distanzgitter zu den Grenzen.

  3. Extrahieren Sie die euklidischen Abstände an den angegebenen Stellen.

  4. Verschieben Sie jeden Ort innerhalb des durch die Entfernung angegebenen Bereichs, der per Definition das Maximum zur Grenze darstellt.

Für jeden Befehl ist normalerweise nur ein einziger Befehl mit einem GIS erforderlich, sodass die gesamte Sequenz einfach automatisiert und manuell ausgeführt werden kann. Dies sind effiziente Befehle, da nicht für jeden Punkt ein Puffer erstellt werden muss (wodurch normalerweise mehrere Dutzend bis fast tausend Punkte erstellt werden, um einen Ring oder Ringraum zu beschreiben ). Es sind auch keine Such- oder Zufallsversuche erforderlich: Die Punkte werden direkt um Beträge verschoben, die sie garantiert in ihren ursprünglichen Zensusdaten belassen.


Zum Beispiel habe ich 172.902 Stellen innerhalb von 47 Flächen in zufällige Richtungen durch Verschiebungen verschoben, die gleichmäßig zwischen der halben Entfernung und der vollen Entfernung zur Grenze verteilt sind. Hier ist ein Teil eines Traktats vor dem Umzug:

Abbildung 1

(gelbe Quadrate markieren die Orte) und nach dem Umzug:

Figur 2

(Jetzt markieren graue Quadrate die neuen Standorte). Der gesamte Vorgang dauerte nur ein oder zwei Minuten (mit einem alten veralteten GIS :-).

Wenn Sie diese Zahlen genau vergleichen, können Sie das sehen

  • Punkte, die sich jetzt nahe der Grenze befinden (z. B. in der Nähe der beiden in diesen Figuren als weiße "Löcher" dargestellten Seen), bleiben notwendigerweise nahe der Grenze.

  • Punkte, die weit von der Grenze entfernt sind, neigen dazu, sich weit zu bewegen.

Folglich entstand ein Punkt nahe der Grenze wahrscheinlich (aber nicht sicher) ganz in der Nähe, wohingegen jeder Punkt weit entfernt von der Grenze wahrscheinlich von einem anderen Ort weit entfernt von der Grenze stammte. Diese beiden Tendenzen sind alles andere als zufällig: Sie könnten (ziemlich leicht) von jemandem ausgenutzt werden, der in die Privatsphäre eindringen möchte, die sich diese Bewegungen leisten sollten.

Bessere Methoden würden die Verbindungen zwischen dem endgültigen und dem ursprünglichen Ort schwächer und zufälliger machen. Zumindest sollten Punkte in relativ großen Stadtteilen und nicht in Stadtteilen unterschiedlicher (und möglicherweise willkürlich kleiner) Größe verschoben werden. Solche Bewegungen lassen sich mit Gittern nicht ohne weiteres ausführen, da sie normalerweise einige Versuche und Irrtümer erfordern: Sie generieren eine Reihe von zufälligen Punkten in der Nähe jedes ursprünglichen Punkts und wählen den ersten aus, der im selben Zensus-Trakt liegt. Dies ist eine Schleife, die (1) eine zufällige Bewegung und (2) eine Punkt-in-Polygon-Untersuchung umfasst. Beide Operationen sind schnell, dies erfordert jedoch ein wenig Programmierung, um die Schleife zu implementieren.

(In einem Kommentar zu der Frage verweise ich auf einige Studien zu Methoden, mit denen Standortdaten aus Datenschutzgründen verschleiert werden.)

whuber
quelle
2

Ich wollte nur Ihre Donuts in PostGIS testen

Ich habe es auf PostGISonline versucht.

Um denselben Test durchzuführen, gehen Sie zu: http://postgisonline.org/map.php

Es gibt einige Polygone, die als "Eigenschafts" -Druck bezeichnet werden:

SELECT * FROM property;

und drücken Sie "Map1"

Dann können Sie den Donut-Code testen, indem Sie das Folgende in den Textbereich kopieren und "map2" drücken (dann bleibt die Eigenschaftskarte erhalten):

SELECT ST_Difference(ST_Buffer(the_geom,dist),ST_Buffer(the_geom,dist/3)) the_geom,dist FROM
(
    SELECT ST_Distance(poly.boundary,points.the_geom) dist, points.the_geom FROM
    (
        SELECT ST_Boundary(the_geom) boundary,the_geom FROM property
    ) poly
    INNER JOIN
    (
        SELECT ST_SetSrid('POINT(137816 267009)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(139816 268542)'::geometry,3021) the_geom
        UNION ALL
        SELECT ST_SetSrid('POINT(135016 268102)'::geometry,3021) the_geom
    ) points
    ON ST_Contains(poly.the_geom,points.the_geom)
) a

Das sollte Ihnen ein Ergebnis geben wie: Geben Sie hier die Bildbeschreibung ein

Nicklas Avén
quelle
PostGIS rockt einfach total! Danke, das ist großartige, gute Arbeit!
Percy
1

Hoffentlich hilft Ihnen diese Python-Lösung weiter. Der allgemeine Workflow lautet wie folgt:

  1. Konvertieren Sie Polygone in Polylinien, damit Sie einen Nahabstand berechnen können
  2. Puffern Sie die Punkte basierend auf der Nahentfernung

Geben Sie hier die Bildbeschreibung ein

# Import arcpy module
import arcpy, os
from arcpy import env

env.overwriteOutput = 1

env.workspace = r'C:\sample.gdb\temp'
Dir = env.workspace

# Local variables:
points = "points"
polygon = "polygon"
points_2 = "points"
buffers = "buffers"
polyline = "polyline"

# Polygon To Line
arcpy.PolygonToLine_management(polygon, polyline, "IDENTIFY_NEIGHBORS")

# Near
arcpy.Near_analysis(points, polyline)

# Buffer
arcpy.Buffer_analysis(points_2, buffers, "NEAR_DIST")
Aaron
quelle
Vielen Dank! das sieht so aus, als würde es einfach funktionieren! :-) Wir werden es versuchen!
Percy