Apa perbedaan antara alat Create Thiessen Polygons (ArcGIS) dan Voronoi Polygons (QGIS)?

12

Apakah poligon Thiessen sama dengan poligon Voronoi? Saya menggunakan ArcMap 10 dan juga QGIS 2.4 dan saya ingin mengetahui perbedaan yang tepat (jika ada) antara kedua metode.

qgis arcgis-desktop voronoi-thiessen Maria Karypidou
sumber
Bisakah Anda jelaskan riset apa pun yang telah Anda lakukan tentang masalah ini dan khususnya apa yang perlu Anda klarifikasi?
Aaron
1
Kami sebenarnya sedang berdiskusi tentang apakah akan menggabungkan dua tag pada meta: meta.gis.stackexchange.com/questions/3677/…
Chris W

Jawaban:

20

Ya, mereka adalah hal yang sama. Di bidang SIG kita cenderung menyebutnya sebagai poligon Thiessen, setelah ahli meteorologi Amerika yang sering menggunakannya. Di bidang lain, terutama matematika dan ilmu komputer, mereka umumnya disebut sebagai diagram Voronoi, untuk menghormati ahli matematika Georgy Voronyi. Kedua penggunaan tersebut dapat diterima.

WhiteboxDev
sumber
Walaupun konsepnya sama, saya bertanya-tanya apakah implementasi di setiap perangkat lunak adalah ...
Chris W
@ ChrisW Itu pertanyaan yang berharga tetapi yang agak sulit dijawab, saya kira. Saya akan berpikir bahwa, seperti kebanyakan masalah tata ruang, ada lebih dari satu cara untuk mencapai solusi, yang akan menyarankan bahwa ada implementasi yang berbeda.
WhiteboxDev
Maaf, saya lebih bersifat retoris. Saya hanya ingin menunjukkan bahwa walaupun konsepnya sama, dan secara umum Anda akan mendapatkan hasil yang sama (atau setidaknya jenis hasil) dalam dua perangkat lunak, bagaimana mereka melakukannya mungkin tidak sama dan hasilnya mungkin tidak persis sama. Pada dasarnya memilih untuk membaca lebih dalam pertanyaan daripada yang mungkin benar-benar diperlukan, tetapi bisa jadi masalah jika Anda melangkah cukup dalam.
Chris W
@ Chris Yap, begitulah cara saya menerjemahkan pertanyaan Anda. Dan itu adalah poin yang sangat valid yang Anda angkat. Saya akan berpikir bahwa detail implementasi dalam dua SIG yang menawarkan alat poligon Thiessen akan menyebabkan sedikit perbedaan dalam cara yang sama bahwa alat akumulasi aliran atau daerah aliran sungai yang diterapkan pada data yang sama dalam dua SIG yang berbeda mungkin sedikit berbeda. Ada banyak yang terjadi antara kerja teoretis dari suatu algoritma dan implementasi kode komputernya.
WhiteboxDev
@ ChrisW Kebetulan, justru pertanyaan Anda yang mengarahkan saya pada gagasan perangkat lunak 'akses terbuka' dan Whitebox GAT. Jika OP telah bertanya bagaimana alat poligon Thiessen Whitebox GAT bekerja, jawabannya akan sesederhana menekan tombol 'Lihat Kode' pada dialog alat. Lihat blog tertaut untuk perincian tentang apa yang saya maksud: whiteboxgeospatial.wordpress.com/2014/05/04/…
WhiteboxDev
9

Kami tidak dapat mengetahui perbedaan yang pasti karena kami tidak dapat melihat kode sumber implementasi ESRI. Namun, tampak dari pandangan sepintas bahwa kedua implementasi tersebut, pada kenyataannya, menggunakan metode yang sama yaitu terjemahan kasar dari algoritma sweepline klasik Steven Fortune .

Di sini Anda dapat melihat kode sumber aktual yang digunakan dalam QGIS. Ini termasuk deskripsi berikut:

For programmatic use two functions are available:

   computeVoronoiDiagram(points)

        Takes a list of point objects (which must have x and y fields).
        Returns a 3-tuple of:

           (1) a list of 2-tuples, which are the x,y coordinates of the
               Voronoi diagram vertices
           (2) a list of 3-tuples (a,b,c) which are the equations of the
               lines in the Voronoi diagram: a*x + b*y = c
           (3) a list of 3-tuples, (l, v1, v2) representing edges of the
               Voronoi diagram.  l is the index of the line, v1 and v2 are
               the indices of the vetices at the end of the edge.  If
               v1 or v2 is -1, the line extends to infinity.

   computeDelaunayTriangulation(points):

        Takes a list of point objects (which must have x and y fields).
        Returns a list of 3-tuples: the indices of the points that form a
        Delaunay triangle.

Sekarang kita tidak dapat melihat kode hak milik ESRI yang menggerakkan alat mereka , tetapi uraian dokumentasi mereka segera mengungkapkan bahwa dasar di balik kedua alat itu sama:

Poligon proksimal Thiessen dibuat sebagai berikut:

Semua poin di-triangulasi menjadi triangulated irregular network (TIN) yang memenuhi kriteria Delaunay. Garis-garis tegak lurus untuk setiap tepi segitiga dihasilkan, membentuk tepi-tepi poligon Thiessen. Lokasi perpotongan garis-garis menentukan lokasi titik poligon Thiessen.

Nuansa sebenarnya dari kode yang menggerakkan keduanya jelas berbeda, karena telah ditunjukkan bahwa terjemahan Bill Simon telah mengetahui bug yang tidak ada dalam versi ESRI.

Ada (sebagaimana telah dinyatakan dalam komentar di atas) beberapa cara lain yang berbeda untuk menghasilkan diagram Voronoi, bahkan dalam GIS, seperti metodologi berbasis raster ini . Ada juga metode berbasis vektor lainnya untuk menghasilkan diagram Voronoi di GIS.

Ada beberapa kelebihan dan kekurangan untuk masing-masing metode. Sebagai contoh, algoritma Fortune relatif cepat dan didokumentasikan dengan baik, tetapi saat ini tidak ada cara yang diketahui untuk menghasilkan diagram Voronoi berbobot ganda menggunakan implementasi langsungnya.

Metode raster pada umumnya jauh lebih lambat secara komputasional tetapi memungkinkan untuk pembuatan berbagai jenis diagram Voronoi ( seperti diagram Voronoi titik terjauh ) tanpa sepenuhnya menciptakan kembali metodologi.

Pengungkapan penuh: Saya telah bekerja sebagai asisten peneliti untuk profesor yang menulis makalah untuk metodologi berbasis raster untuk menghasilkan Diagram Voronoi.

TL; DR: Meskipun implementasi yang sebenarnya sedikit berbeda, mereka didasarkan pada algoritma yang sama dan keduanya harus menghasilkan hasil yang sama (selain dari beberapa kasus tepi yang menghasilkan bug yang dicatat dalam pertanyaan Dan Patterson terkait di atas).

Conor
sumber