Algoritma untuk memperbaiki kesalahan topologi dalam aplikasi perangkat lunak GIS

19

Pertanyaan terkait di sini.

Saya perhatikan bahwa memastikan kebenaran topologi sangat penting untuk aplikasi SIG, ini karena input dari pengguna atau operasi boolean poligon dapat memiliki masalah topologi yang parah (meskipun poligon terlihat benar) yang akan berkompromi pada kualitas operasi selanjutnya.

Poligon bersih adalah cara Geo Wizards lakukan untuk memastikan kebenaran topologi.

Arcgis juga memiliki perintah untuk membersihkan sliver.

Pertanyaan saya bukan tentang bagaimana menggunakan paket perangkat lunak yang ada untuk memastikan bahwa data input poligon benar secara topologi; alih-alih, pertanyaan saya adalah tentang bagaimana paket perangkat lunak ini menerapkan prosedur pembersihan tersebut. Dengan kata lain, apa algoritma yang dapat saya gunakan untuk memastikan bahwa saya dapat memperbaiki semua kesalahan topologi, mengingat serangkaian input poligon?

Graviton
sumber
2
Ada alat GP ArcGIS lain, yang disebut "Integrate", yang memiliki penjelasan singkat tentang algoritma dalam sumber daya bantuan: help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//… - Namun itu tidak ditentukan dengan baik.
Allan Adair
Tautan Anda sendiri dari Geo Wizards sebenarnya mewakili algoritme dengan cukup baik. Apa lagi yang Anda harapkan?
johanvdw
@hohanvdw, apa yang ditampilkan tautan bukan algoritma, melainkan langkah-langkah tentang cara menggunakan perangkat lunak untuk mengaktifkan algoritme untuk membersihkan poligon. Perbedaan antara keduanya sangat besar.
Graviton
1
Mencari algoritma planarisasi mungkin menemukan sesuatu yang bermanfaat.
Kirk Kuykendall
@KirkKuykendall, saya tidak tahu bagaimana planarisasi membantu algo; Saya pikir itu lebih berlaku untuk teori grafik daripada hal-hal geometri komputasi seperti ini?
Graviton

Jawaban:

7

Pencarian Google Cendekia yang cepat menemukan artikel-artikel berikut yang dikutip dengan baik:

blah238
sumber
+1 Sepertinya kertas yang dipikirkan dengan matang. Saya berharap para penulis akan mendefinisikan apa yang mereka maksud dengan "adegan".
Kirk Kuykendall
Terima kasih, saya menambahkan artikel kedua (oleh salah satu penulis yang sama), tetapi pada pandangan pertama saya masih tidak tahu apa 'adegan' itu.
blah238
10

Anda dapat menemukan deskripsi terperinci tentang rutinitas pembersihan topologi dalam kode sumber dan manual GRASS GIS: http://grass.osgeo.org/programming7

Rutinitas pembersihan diberi kode di sini: http://trac.osgeo.org/grass/browser/grass/trunk/vector/v.clean

Contoh untuk rutinitas yang mendasarinya:

Konsep yang mendasari diuraikan di sini: http://grass.osgeo.org/programming7/vectorlib.html#vlibTopoExamples

markN
sumber
4

Meskipun bukan algoritma, halaman ini memberi Anda beberapa informasi tentang apa jenis kesalahan topologi "periksa geometri" terlihat di alat ArcGIS. Periksa Geometri / Perbaikan Geometri. http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003v000000

Null geometry: The record will be deleted from the feature class. To keep records with null geometry, uncheck the tool dialog option Delete Features with    Null Geometry, or in scripting set the delete_null parameter to KEEP_NULL.
Short segment: The geometry's short segment will be deleted.
Incorrect ring ordering: The geometry will be updated to have correct ring ordering.
Incorrect segment orientation: The geometry will be updated to have correct segment orientation.
Self intersections: the areas of overlap in a polygon will be dissolved.
Unclosed rings: The unclosed rings will be closed by connecting the ring's end points.
Empty parts: The parts that are null or empty will be deleted.
Duplicate vertex: One of the vertices will be deleted.
Mismatched attributes: The Z or M coordinate will be updated to match.
Discontinuous parts: Multiple parts will be created from the existing discontinuous part.
Empty Z values: The Z value will be set to 0.
Michael Markieta
sumber
3

Saya tidak berpikir ada cara untuk mengotomatisasi kesalahan topologi sepenuhnya dalam dataset yang diberikan. Beberapa hal, seperti menggantung mungkin dapat mengotomatisasi pemisahan dan kemudian menghapus menjuntai yang dihasilkan. Tapi bagaimana dengan sliver antara dua poligon yang berdekatan, mana poligon yang harus digabung dengan sliver mana yang harus dihilangkan? Jenis pertanyaan seperti itu tampaknya membutuhkan input pengguna. Untuk mengidentifikasi kesalahan namun saya pikir algoritma menggunakan semacam variasi DE-9IM (Dimensi 9 diperluas sesuatu sesuatu). Saya pikir taruhan terbaik Anda adalah dengan melihat Java Topology Suite (JTS). Khususnya kelas Grafik Geometri. Saya pikir ini dapat digunakan untuk membangun berbagai komponen geometri tertentu, dan kemudian digunakan untuk memeriksa berbagai masalah topologi. Saya belum pernah melakukannya, tetapi belum lama ini saya melihatnya.

Jika Anda tidak terbiasa dengan Java, GEOS adalah rasa C ++ dari JTS, atau NetTopologySuite adalah rasa C #.

Semoga itu bisa membantu.

dslamb
sumber
1

Dokumentasi perintah Integrasi ArcGIS telah disebutkan, tetapi ESRI juga telah menghasilkan makalah teknis Memahami Pemrosesan Geometrik dalam ArcGIS yang mendokumentasikan logika pemrosesan yang digunakan oleh Integrate (dan operasi geoproses yang melibatkan toleransi secara lebih umum). Ini difokuskan pada penghindaran dan koreksi kesalahan topologi yang dihasilkan dari geoprocessing. Ada beberapa referensi yang diberikan yang mungkin juga bermanfaat.

Andy Harfoot
sumber