lingkaran maksimum di dalam poligon tidak beraturan dari titik acak

8

Saya mencoba membuat algoritma untuk membuat lingkaran jari-jari maksimum dalam poligon tidak beraturan (saluran sensus) berdasarkan pusat lingkaran yang diberikan.

Motivasi untuk ini adalah untuk mengaburkan lokasi seseorang yang telah menjawab survei. Lokasi aktual mereka diketahui, namun perlu dikaburkan dalam analisis, untuk merilis data kepada publik, untuk analisis lebih lanjut.

Kami ingin memiliki poligon berbentuk donat untuk setiap responden survei yang memiliki beberapa jari-jari dalam (mudah), dibatasi oleh jari-jari luar yang dibatasi oleh saluran sensus tempat individu tersebut berada. Lokasi akhir mereka akan ditempatkan secara acak di dalam poligon donat. .

Saya telah melihat banyak jawaban untuk pertanyaan serupa di sini, tetapi bukan yang spesifik ini, yang dalam hal ini dimulai dengan lokasi SPESIFIK.

Setelah donat didirikan, kami dapat mengacak lokasi respons individu dalam poligon. Itu relatif mudah ...

Terima kasih atas ide-ide Anda, milik saya sejauh ini tampaknya cukup kasar, dan secara komputasi "mahal" atau tidak efisien ...

Percy
sumber
1
Bukankah itu jarak terdekat dari lokasi spesifik ke batas poligon yang Anda inginkan?
Nicklas Avén
Perangkat lunak atau bahasa pemrograman apa yang Anda gunakan?
Pablo
Mengapa tidak memotong anulus yang diinginkan dengan risalah? Lebih baik lagi, tidak ada alasan untuk menggunakan bentuk lingkaran - Anda juga bisa menggunakan annulus persegi, yang akan menyebabkan eksekusi lebih cepat.
whuber
3
Tampaknya ada sedikit atau tidak ada konsensus . Gambaran umum beberapa metode muncul di sini, mulai hal. 34 . Metode canggih diusulkan di situs kami . Kelompok kerja internasional baru - baru ini mengeksplorasi banyak masalah terkait. Ulasan terbaru oleh Mathews & Harel mungkin berguna.
whuber
3
@whuber, terima kasih banyak! Saya berasumsi Anda adalah Bill Huber yang sama yang telah memposting bantuan dan kode sumber sejak saya mulai menggunakan GIS pada tahun 1998. Saya menyukai semua skrip Avenue Anda, belajar banyak dari mereka (dan saya menganggap program yang direferensikan di bawah ini adalah ArcView, itu luar biasa seberapa cepat ia berjalan hari ini !!!). Hanya ingin memberi tahu Anda betapa Anda dihargai di komunitas praktisi GIS! Terima kasih atas semua tahun nasihat Anda yang luar biasa!
Percy

Jawaban:

3

Metode sederhana untuk memindahkan lokasi dalam annuli seperti itu mengeksploitasi representasi grid dari jarak ke batas traktat. Dimulai dengan representasi poligonal dari traktus Sensus (yang biasa),

  1. Konversikan itu menjadi batas poligon (lapisan polyline).

  2. Hitung grid jarak Euclidean dengan batas.

  3. Ekstrak jarak Euclidean di lokasi yang diberikan.

  4. Pindahkan setiap lokasi dalam rentang yang diberikan oleh jarak - yang, menurut definisi, adalah maksimum ke batas.

Masing-masing biasanya hanya memerlukan satu perintah dengan GIS, membuat seluruh urutan mudah otomatis dan mudah dilakukan secara manual. Ini adalah perintah yang efisien , karena mereka tidak memerlukan membangun buffer untuk setiap titik (yang biasanya membuat beberapa lusin hingga hampir seribu poin untuk menggambarkan cincin, atau annulus ). Tidak ada uji coba pencarian atau acak yang diperlukan, baik: titik-titik secara langsung dipindahkan dengan jumlah yang dijamin untuk meninggalkan mereka dalam traktus Sensus asli mereka.


Sebagai contoh, saya memindahkan 172.902 lokasi dalam 47 traktat ke arah acak dengan perpindahan yang terdistribusi secara merata antara setengah jarak dan jarak penuh ke batas. Berikut adalah bagian dari satu risalah sebelum pindah:

Gambar 1

(kotak kuning tandai lokasi) dan setelah pindah:

Gambar 2

(sekarang kotak abu-abu menandai lokasi baru). Operasi total hanya membutuhkan satu atau dua menit (menggunakan GIS yang sudah usang :-).

Dengan membandingkan angka-angka ini dengan seksama, Anda dapat melihatnya

  • Poin yang sekarang dekat dengan batas (seperti dekat dua danau yang ditampilkan sebagai "lubang" putih pada gambar-gambar ini) harus selalu dekat dengan batas.

  • Poin yang jauh dari batas cenderung bergerak jauh.

Akibatnya, suatu titik yang dekat dengan batas kemungkinan berasal (tetapi tidak tentu) berasal sangat dekat, sedangkan titik yang jauh dari batas kemungkinan berasal dari tempat lain yang jauh dari batas. Kedua kecenderungan ini jauh dari acak: mereka dapat (cukup mudah) dieksploitasi oleh seseorang yang ingin menembus privasi yang ingin dicapai oleh gerakan ini.

Metode yang lebih baik akan membuat koneksi antara lokasi akhir dan awal lebih renggang dan lebih acak. Paling tidak, poin harus dipindahkan dalam lingkungan yang cukup besar daripada dalam lingkungan dengan ukuran yang bervariasi (dan mungkin kecil secara sewenang-wenang). Gerakan seperti itu tidak mudah dilakukan dengan kisi-kisi, karena biasanya mereka memerlukan beberapa percobaan dan kesalahan: Anda menghasilkan banyak titik acak dalam lingkungan dari setiap titik asli dan memilih yang pertama yang terletak di dalam saluran Sensus yang sama. Itu adalah loop yang melibatkan (1) gerakan acak dan (2) penyelidikan point-in-polygon. Kedua operasi cepat, tetapi ini membutuhkan sedikit pemrograman untuk mengimplementasikan loop.

(Dalam komentar pada pertanyaan, saya memberikan tautan ke beberapa studi tentang metode yang digunakan untuk menyamarkan data lokasi untuk tujuan privasi.)

whuber
sumber
2

Saya hanya ingin menguji donat Anda di PostGIS

Saya mencobanya di PostGISonline.

Untuk melakukan tes yang sama Anda pergi ke: http://postgisonline.org/map.php

Ada beberapa poligon yang disebut "properti" cetak:

SELECT * FROM property;

dan tekan "Map1"

Kemudian Anda dapat menguji kode donat dengan menyalin di bawah ini ke textarea dan tekan "map2" (maka properti-peta akan tetap):

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

Itu akan memberi Anda hasil sesuatu seperti: masukkan deskripsi gambar di sini

Nicklas Avén
sumber
PostGIS benar-benar hanya batu! Terima kasih, itu luar biasa, kerja bagus!
Percy
1

Semoga solusi Python ini akan membantu Anda. Alur kerja umum adalah sebagai berikut:

  1. Ubah poligon menjadi polyline sehingga Anda dapat menghitung jarak Dekat
  2. Buffer poin berdasarkan jarak yang dekat

masukkan deskripsi gambar di sini

# 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")
Harun
sumber
Terima kasih! yang sepertinya hanya bekerja! :-) kami akan mencobanya!
Percy