Mempertimbangkan lubang / kendala dalam pembuatan poligon Voronoi di QGIS?

12

Saya mencoba membuat voronoi poligon di QGIS yang akan mempertimbangkan "lubang" di domain umum. Contohnya adalah:

masukkan deskripsi gambar di sini

Saya benar-benar membuat Vorono pada gambar ini menggunakan QGIS melalui perintah GRASS, kemudian menggunakan alat "Perbedaan" untuk membuat lubang. Shapefile poligon terpisah, yang berisi luasan lubang, digunakan sebagai lapisan "Perbedaan". Contoh aplikasi akan membuat poligon di sekitar titik pengambilan sampel yang dikumpulkan antara struktur yang harus dikeluarkan dari analisis.

Dua masalah muncul di sini:

  1. Fungsi "perbedaan" tampaknya tidak berfungsi 100% dengan benar, dengan beberapa batas poligon memanjang ke "lubang". Ini dapat diperbaiki dengan menemukan baris di Tabel Atribut yang tidak memiliki nomor ID poligon (atau ID "0").

  2. Jenis "hole-punch" setelah-fakta ini dapat menghasilkan poligon diskontinyu, seperti yang ditunjukkan oleh panah merah pada gambar.

Pertanyaan saya adalah: apakah ada alat atau plugin Voronoi yang dapat mempertimbangkan keberadaan "lubang" di tengah domain, sebagai proses satu langkah, dan juga menghilangkan generasi poligon terputus-putus? Saya membayangkan bahwa alat seperti itu akan memperluas batas poligon ke persimpangan terdekat dengan batas lain, kecuali jika batas itu membanting terhadap batas "lubang" terlebih dahulu.

LeaningCactus
sumber
Ini akan mirip dengan tetapi kebalikan dari (saya pikir) menggunakan masker lingkungan di ArcGIS . Itu akan membiarkan Anda membatasi poligon yang dibuat dalam batas tertentu. Namun saya tidak mengetahui adanya alat yang akan menggunakan batas / lubang yang kompleks (meskipun mungkin di ArcGIS topeng bisa menjadi kompleks - saya belum mengujinya dan saya akan mencobanya nanti jika saya punya waktu).
Chris W
Saya telah menguji teori ArcGIS, dan itu tidak akan berhasil. Per pertanyaan yang ditautkan, Anda dapat membatasi hasil ke bentuk luar. Namun, lubang yang dipotong dalam bentuk diabaikan oleh polis yang dihasilkan. Lebih lanjut, jika lubang itu juga memiliki beberapa titik di dalamnya, alat kesalahan keluar dan gagal dijalankan. Saya tidak bisa menjelaskan masalah pertama Anda dengan perbedaan, tetapi yang kedua menghasilkan sliver tidak sepenuhnya tidak terduga - setelah semua, area itu masih akan dialokasikan ke titik yang sama bahkan jika lubang ada. Anda bisa menggunakan metode itu dan kemudian memasukkan sliver ke tetangga mereka dengan metode pembersihan.
Chris W
2
Anda berpotensi memecahkan ini dengan pergi ke raster. Dengan topeng raster, jarak Euclidean akan keluar dari titik Anda hingga menyentuh sel mana pun yang keluar dari titik lain atau raster topeng Anda (deskripsi slam batas Anda). Kemudian Anda melakukan pembersihan zona dan membuat vektor hasilnya untuk mendapatkan poligon.
Chris W
1
Saya akan memastikan Geometri voronoi valid dengan menjalankan v.clean kemudian memeriksa geometri. Akhirnya, jalankan Perbedaan untuk membuat lubang.
klewis
Apa Voronoi tentang lubang ini? Apakah Anda tidak ingin membuat lubang dengan bersih? Mengapa tidak ada lapisan poligon?
mdsumner

Jawaban:

3

Ini dimungkinkan menggunakan raster. Konversi poin dan poligon batas Anda terlebih dahulu menjadi raster resolusi tinggi. Tetapkan topeng untuk batas Anda menggunakan r.mask. Kemudian, jalankan r.grow.distancedalam GRASS dan gunakan Value= output. Ini akan memberi Anda untuk setiap piksel, yang merupakan titik terdekat. Ubah ini kembali menjadi poligon vektor. Mungkin ada langkah-langkah tambahan yang dibutuhkan untuk menyingkirkan sliver poligon.

Guillaume
sumber
2

Ini tentu saja mungkin dengan raster.

Tangkapan layar ini mudah-mudahan menunjukkan masalahnya dengan lebih jelas. Bagian B dari voronoi lebih dekat 'saat gagak terbang' ke pusat voronoi yang asli, tetapi ini tidak memperhitungkan fakta bahwa akan memakan waktu lebih lama untuk berjalan di sekitar gedung. Pemahaman saya tentang pertanyaan OP adalah bahwa voronoi perlu memperhitungkan jarak ekstra ini untuk berjalan di sekitar gedung.

masukkan deskripsi gambar di sini

Saya suka saran dari @Guillaume. Namun, ketika saya mencobanya saya punya masalah r.grow.distanceuntuk menghormati topeng (lihat di bawah. Riak-riak seharusnya tidak melewati bangunan).

Pengetahuan Rumput saya tidak sekuat yang seharusnya, jadi mungkin saya melakukan sesuatu yang bodoh. Tentunya, periksa saran itu terlebih dahulu karena akan jauh lebih sedikit pekerjaan daripada milik saya ;-)

masukkan deskripsi gambar di sini

Langkah 1 - Buat permukaan biaya

Langkah pertama adalah membuat permukaan biaya. Ini hanya perlu dilakukan sekali.

  • buat layer yang bisa diedit, lubang dan semua.
  • tambahkan bidang yang disebut 'unit', setel ke 1.
  • menggunakan polygon-to-raster pada layer vektor "punched" (yang berlubang), menggunakan field 'unit'. Anda sekarang memiliki layer "mask", di mana 1 adalah ruang kosong dan 0 sedang membangun.
  • gunakan kalkulator raster untuk mengubahnya menjadi permukaan biaya. Saya akan mengatur 'di luar ruangan' menjadi 1 dan 'di dalam ruangan' ke 9999. Ini akan membuat sulit untuk melewati bangunan.

    (("mask @ 1" = 1) * 1) + (("mask @ 1" = 0) * 9999)

Anda bisa mendapatkan lebih banyak hasil 'organik' dengan menambahkan sedikit noise ke permukaan biaya (mis. Gunakan angka acak dari 1 hingga 3, daripada hanya 1 untuk pxiels outdoor.)

Langkah 2. Buat raster biaya kumulatif untuk setiap pusat voronoi

Sekarang kita dapat menjalankan (untuk satu sel voronoi sekaligus) algoritma GRASS r.cost.coordinatesterhadap lapisan permukaan biaya kami.

Untuk mulai berkoordinasi, gunakan pusat vornoi. Untuk koordinat akhir, pilih salah satu sudut area Anda. Saya sarankan menggunakan 'Knights Tour' karena ini memberikan hasil yang lebih halus.

Hasilnya menunjukkan garis waktu perjalanan yang sama dari satu pusat voronoi. Perhatikan bagaimana pita membungkus bangunan.

masukkan deskripsi gambar di sini

Tidak yakin cara terbaik untuk mengotomatisasi ini. Mungkin memproses mode batch, atau dilakukan dalam pyqgis.

Langkah 3. Gabungkan raster

Ini mungkin membutuhkan kode. Algoritma akan menjadi

create a raster 'A' to match the size of your cumulative cost images
fill raster 'A' with a suitably high number e.g. 9999
create an array of the same size as the raster.
for each cumulative cost raster number 1..N
    for each cell in image
        if cell < value in raster 'A'
            set value in raster 'A' to cell value
            set corresponding cell in array to cum. cost image number
write out array as a raster

Pendekatan itu harus menghasilkan raster di mana setiap sel dikategorikan oleh pusat voronoi terdekat, dengan mempertimbangkan hambatan.

Anda kemudian dapat menggunakan raster-ke-poligon. Anda kemudian dapat menggunakan plugin Generalize untuk menghapus artefak efek "langkah" dari raster.

Permintaan maaf atas ketidakjelasan pada langkah 2 dan 3 ... Saya berharap seseorang berpadu dengan solusi yang lebih elegan :)

Steven Kay
sumber
1
Terima kasih Steven, saya memiliki pekerjaan raster GRASS yang berhasil, tetapi saya berharap untuk solusi yang lebih elegan seperti yang disebutkan dalam deskripsi karunia.
underdark
0

Catatan # 1 : Saya tidak dapat mereproduksi masalah yang diusulkan karena alat Perbedaan bekerja dengan baik untuk saya dalam beberapa tes yang saya lakukan (mungkin itu karena geometri masalah yang sederhana atau karena alat tersebut telah diperbaiki karena pertanyaannya adalah tanya 1 tahun yang lalu).

Namun, saya mengusulkan solusi di PyQGIS untuk menghindari penggunaan alat Perbedaan . Semuanya didasarkan pada persimpangan lokal antara dua lapisan input (lihat gambar di bawah):

  1. lapisan vektor poligon yang mewakili poligon Voronoi;
  2. lapisan vektor poligon yang mewakili lubang / kendala yang perlu dikeluarkan dari analisis.

masukkan deskripsi gambar di sini

Catatan # 2 : Karena saya tidak ingin menggunakan alat Perbedaan , saya tidak dapat menghindari pembuatan "sliver" (lihat kemudian), jadi saya perlu menjalankan v.cleanalat untuk menghilangkannya. Selanjutnya, seperti yang dikatakan @Chris W,

[...] tetapi yang kedua menghasilkan sliver tidak sepenuhnya tidak terduga - setelah semua, area itu masih akan dialokasikan ke titik yang sama bahkan jika lubangnya ada. Anda bisa menggunakan metode itu dan kemudian memasukkan sliver ke tetangga mereka dengan metode pembersihan .

Setelah tempat yang diperlukan ini, saya memposting kode saya:

##Voronoi_Polygons=vector polygon
##Constraints=vector polygon
##Voronoi_Cleaned=output vector

from qgis.core import *

voronoi = processing.getObject(Voronoi_Polygons)
crs = voronoi.crs().toWkt()
ex = voronoi.extent()
extent = '%f,%f,%f,%f' % (ex.xMinimum(), ex.xMaximum(), ex.yMinimum(), ex.yMaximum())

constraints = processing.getObject(Constraints)

# Create the output layer
voronoi_mod = QgsVectorLayer('Polygon?crs='+ crs, 'voronoi' , 'memory')
prov = voronoi_mod.dataProvider()
fields = voronoi.pendingFields() # Fields from the input layer
prov.addAttributes(fields) # Add input layer fields to the outLayer
voronoi_mod.updateFields()

# Spatial index containing all the 'constraints'
index_builds = QgsSpatialIndex()
for feat in constraints.getFeatures():
    index_builds.insertFeature(feat)

final_geoms = {}
final_attrs = {}

for feat in voronoi.getFeatures():
    input_geom = feat.geometry()
    input_attrs = feat.attributes()
    final_geom = []
    multi_geom = input_geom.asPolygon()
    input_geoms = [] # edges of the input geometry
    for k in multi_geom:
        input_geoms.extend(k)
    final_geom.append(input_geoms)
    idsList = index_builds.intersects(input_geom.boundingBox())
    mid_geom = [] # edges of the holes/constraints
    if len(idsList) > 0:
        req = QgsFeatureRequest().setFilterFids(idsList)
        for ft in constraints.getFeatures(req):
            geom = ft.geometry()
            hole = []
            res = geom.intersection(input_geom)
            res_geom = res.asPolygon()
            for i in res_geom:
                hole.extend(i)
                mid_geom.append(hole)
        final_geom.extend(mid_geom)
    final_geoms[feat.id()] = final_geom
    final_attrs[feat.id()] = input_attrs

# Add the features to the output layer
outGeom = QgsFeature()
for key, value in final_geoms.iteritems():
    outGeom.setGeometry(QgsGeometry.fromPolygon(value))
    outGeom.setAttributes(final_attrs[key])
    prov.addFeatures([outGeom])

# Add 'voronoi_mod' to the Layers panel
QgsMapLayerRegistry.instance().addMapLayer(voronoi_mod)

# Run 'v.clean'
processing.runalg("grass7:v.clean",voronoi_mod, 2, 0.1, extent, -1, 0.0001, Voronoi_Cleaned, None)

# Remove 'voronoi_mod' to the Layers panel
QgsMapLayerRegistry.instance().removeMapLayer(voronoi_mod)

yang mengarah ke hasil ini:

masukkan deskripsi gambar di sini

Hanya untuk kejelasan, ini akan menjadi hasil tanpa menggunakan v.cleanalat ini:

masukkan deskripsi gambar di sini

Perbedaan dengan hasil oleh @LeaningCactus adalah bahwa, sekarang, geometri tidak rusak dan mereka bisa "dibersihkan" tanpa kesalahan .

mgri
sumber
Buat lubang lebih lama, misalnya memotong seluruh peta, seperti sungai, dan Anda akan melihat masalahnya. Menambahkan sliver ke tetangga menciptakan poligon yang terlihat sangat berbeda dari diagram Voronoi yang dibatasi dengan tepat. Saya mencobanya.
underdark
Maaf, saya tidak mengerti: apakah Anda menemukan kesalahan dalam hasil? Saya hanya menguji kode untuk kasus-kasus di mana poligon mirip dengan yang diusulkan dalam pertanyaan.
mgri
Sayangnya, tidak dapat menguji kode sekarang, tetapi dapatkah Anda menunjukkan hasil yang diperoleh dengan perubahan lubang yang dibuat di i.stack.imgur.com/Jpfra.png ?
underdark
Jika saya memperluas batasan hingga fitur di sebelah kanan, saya memperoleh ini . Sebaliknya, jika saya langsung memindahkan kendala, saya mendapatkan ini .
mgri
Segitiga kecil yang ditunjukkan panah merah di gambar saya adalah masalahnya. Seharusnya tidak ada di sana tetapi juga di hasil Anda. Sepertinya pendekatan ini menyelesaikan masalah # 1 dari pertanyaan tetapi membiarkan # 2 tidak terpecahkan.
underdark