Saya mencoba membuat diagram voronoi dari kisi poin menggunakan kode yang dimodifikasi dari sini . Ini adalah permintaan SQL setelah modifikasi saya:
DROP TABLE IF EXISTS example.voronoi;
WITH
-- Sample set of points to work with
Sample AS (SELECT ST_SetSRID(ST_Union(geom), 0) geom FROM example."MeshPoints2d"),
-- Build edges and circumscribe points to generate a centroid
Edges AS (
SELECT id,
UNNEST(ARRAY['e1','e2','e3']) EdgeName,
UNNEST(ARRAY[
ST_MakeLine(p1,p2) ,
ST_MakeLine(p2,p3) ,
ST_MakeLine(p3,p1)]) Edge,
ST_Centroid(ST_ConvexHull(ST_Union(-- Done this way due to issues I had with LineToCurve
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p1,p2),ST_MakeLine(p2,p3)))),'LINE','CIRCULAR'),15),
ST_CurveToLine(REPLACE(ST_AsText(ST_LineMerge(ST_Union(ST_MakeLine(p2,p3),ST_MakeLine(p3,p1)))),'LINE','CIRCULAR'),15)
))) ct
FROM (
-- Decompose to points
SELECT id,
ST_PointN(g,1) p1,
ST_PointN(g,2) p2,
ST_PointN(g,3) p3
FROM (
SELECT (gd).Path id, ST_ExteriorRing((gd).geom) g -- ID andmake triangle a linestring
FROM (SELECT (ST_Dump(ST_DelaunayTriangles(geom))) gd FROM Sample) a -- Get Delaunay Triangles
)b
) c
)
SELECT ST_SetSRID((ST_Dump(ST_Polygonize(ST_Node(ST_LineMerge(ST_Union(v, ST_ExteriorRing(ST_ConvexHull(v)))))))).geom, 2180)
INTO example.voronoi
FROM (
SELECT -- Create voronoi edges and reduce to a multilinestring
ST_LineMerge(ST_Union(ST_MakeLine(
x.ct,
CASE
WHEN y.id IS NULL THEN
CASE WHEN ST_Within(
x.ct,
(SELECT ST_ConvexHull(geom) FROM sample)) THEN -- Don't draw lines back towards the original set
-- Project line out twice the distance from convex hull
ST_MakePoint(ST_X(x.ct) + ((ST_X(ST_Centroid(x.edge)) - ST_X(x.ct)) * 2),ST_Y(x.ct) + ((ST_Y(ST_Centroid(x.edge)) - ST_Y(x.ct)) * 2))
END
ELSE
y.ct
END
))) v
FROM Edges x
LEFT OUTER JOIN -- Self Join based on edges
Edges y ON x.id <> y.id AND ST_Equals(x.edge,y.edge)
) z
Di bawah - hasil permintaan saya.
Seperti yang Anda lihat, saya mendapatkan "hampir" diagram voronoi yang benar, kecuali titik-titik yang disorot yang tidak memiliki poligon unik. Di bawah ini adalah apa yang dihasilkan algoritma QGIS dan apa yang ingin saya peroleh dari kueri. Adakah saran di mana masalah dengan kode saya?
postgis
sql
voronoi-thiessen
DamnBack
sumber
sumber
Jawaban:
Meskipun ini memperbaiki masalah langsung dengan kueri untuk data yang dipermasalahkan, saya tidak senang dengan itu sebagai solusi untuk penggunaan umum dan saya akan meninjau kembali ini dan jawaban sebelumnya ketika saya bisa.
Masalahnya adalah bahwa permintaan asli menggunakan lambung cembung pada tepi voronoi untuk menentukan tepi eksterior untuk poligon voronoi. Ini berarti bahwa beberapa tepi voronoi tidak mencapai bagian luar ketika seharusnya. Saya melihat menggunakan fungsi lambung cekung, tetapi tidak benar-benar berfungsi seperti yang saya inginkan.
Sebagai perbaikan cepat saya telah mengubah lambung cembung yang akan dibangun di sekitar set tepi voronoi yang ditutup ditambah penyangga di sekitar tepi aslinya. Tepi voronoi yang tidak menutup diperpanjang keluar jarak yang besar untuk mencoba dan memastikan bahwa mereka memotong eksterior dan digunakan untuk membangun poligon. Anda mungkin ingin bermain-main dengan parameter buffer.
sumber
ST_Union(ST_Buffer(geom))
), tetapi saya akan melanjutkan pengujian dengan set poin lainnya. Sementara itu saya akan menunggu seperti yang Anda katakan - solusi yang lebih umum. :)Mengikuti saran dari @ LR1234567 untuk mencoba fungsi ST_Voronoi baru yang telah dikembangkan oleh @dbaston, jawaban luar biasa asli @MickyT (sebagaimana dinyatakan dalam pertanyaan OP) dan menggunakan data asli sekarang dapat disederhanakan menjadi:
yang menghasilkan output ini, identik dengan pertanyaan OP.
Namun, ini menderita dari masalah yang sama, sekarang diperbaiki dalam jawaban MickyT, bahwa poin pada lambung cekung tidak mendapatkan poligon terlampir (seperti yang diharapkan dari algoritma). Saya memperbaiki masalah ini dengan kueri dengan serangkaian langkah berikut.
Diagram 2 menunjukkan titik pada lambung cekung (kuning) dan titik terdekat ke buffer pada lambung (hijau).
Query jelas dapat disederhanakan / dikompresi, tapi saya meninggalkannya sebagai bentuk CTE, karena lebih mudah untuk mengikuti langkah-langkah berurutan seperti itu. Kueri ini berjalan pada data asli yang diatur dalam milidetik (rata-rata 11ms pada server dev) sedangkan jawaban MickyT menggunakan ST_Delauney berjalan pada 4800 ms pada server yang sama. DBaston mengklaim bahwa urutan peningkatan kecepatan magnitudo lainnya dapat diperoleh dari pembangunan terhadap batang GEOS saat ini, 3.6dev, karena peningkatan dalam rutinitas triangulasi.
Diagram 3 menunjukkan semua titik yang sekarang terlampir dalam poligon
Catatan: Saat ini ST_Voronoi melibatkan pembuatan Postgis dari sumber (versi 2.3, atau trunk) dan menghubungkannya dengan GEOS 3.5 atau lebih tinggi.
Sunting: Saya baru saja melihat Postgis 2.3 saat diinstal di Amazon Web Services, dan sepertinya nama fungsinya sekarang adalah ST_VoronoiPolygons.
Tidak diragukan lagi kueri / algoritme ini dapat ditingkatkan. Saran diterima.
sumber
Jika Anda memiliki akses ke PostGIS 2.3, cobalah fungsi ST_Voronoi baru, yang baru-baru ini dilakukan:
http://postgis.net/docs/manual-dev/ST_Voronoi.html
Ada build yang telah dikompilasi untuk windows - http://postgis.net/windows_downloads/
sumber