Menggabungkan garis ketika arah tidak diketahui

Saya berjuang dengan masalah ini. Saya memiliki polyline yang terdiri dari beberapa segmen. Setiap segmen terdiri dari titik, setiap titik diidentifikasi dalam ruang 3D oleh koordinat dan ketinggian. Bersama-sama, jika diplot, segmen membentuk garis yang kurang lebih kontinu (mungkin ada jeda antar segmen), tetapi segmen itu sendiri tidak berurutan, juga tidak semua titik di semua segmen mengikuti arah perjalanan yang sama.
Pertanyaannya adalah: bagaimana saya bisa membuat, menggunakan Python lebih disukai, satu baris dari segmen non-berurutan ini sehingga saya bisa mengukur jarak antara titik dan total panjang garis.
Saya bahkan tidak tahu segmen mana yang merupakan yang pertama atau yang terakhir dalam barisan, tetapi entah bagaimana saya harus meletakkannya dalam urutan yang benar dan memastikan semuanya menunjuk ke arah yang sama sehingga saya bisa mengukurnya.
Terima kasih atas segala bantuannya. Saya akan dengan senang hati memberikan info tambahan, data, dll. Saya menekankan saya tidak meminta kode python yang sebenarnya (bukan bahwa saya akan menolaknya ...), hanya strateginya. Bob

Segmen dapat digunakan untuk membentuk grafik G abstrak di mana mereka memainkan peran node . Pertimbangkan node yang merupakan segmen (busur) dari titik P ke titik Q, PQ. Biarkan R menjadi titik akhir terdekat di antara semua titik akhir segmen lainnya ke P dan biarkan S menjadi titik akhir lain dari segmen R. G kemudian berisi tepi dari simpul PQ ke simpul RS dan kami akan memberi label tepi ini dengan titik P dan R.

Jika kita ingin sukses, maka G adalah grafik linier atau siklus tunggal. Anda dapat mendeteksi yang mana dengan menyimpan derajat node saat Anda membuat tepi. (Derajat sebuah simpul menghitung tepi yang berasal dari simpul itu.) Semua simpul, kecuali mungkin dua dari mereka, harus memiliki derajat 2. Dua lainnya harus memiliki derajat 2 (untuk suatu siklus) atau derajat 1: ini menandai mereka sebagai ujung polyline. Dalam kasus pertama pilih sembarang simpul untuk mulai membangun polyline; dalam kasus kedua, pilih salah satu dari derajat 1. Kombinasi derajat lainnya adalah kesalahan.

Polyline diinisialisasi ke simpul awal (busur). Lihatlah salah satu tepi e insiden pada node ini: simpul lainnya memberitahu Anda yang busur untuk memproses berikutnya dan label memberitahu Anda yang simpul dari mereka busur untuk bergabung. (Bergabung dengan simpul dengan segmen garis baru jika mereka tidak memiliki koordinat identik.) Update polyline tumbuh dengan cara ini dan, pada saat yang sama, menghapus tepi e dari grafik G . Lanjutkan sampai terjadi kesalahan (dan laporkan bahwa ujung-ujungnya tidak membentuk polyline yang terhubung tanpa cabang) atau semua tepi dihilangkan. Jika tidak ada kesalahan yang muncul, hasilkan polyline yang Anda buat.

Contoh

Dalam gambar arcs adalah AB, CD, EF, dan FG. Karena itu, simpul grafik {AB, CD, EF, FG}. Tepinya adalah AB - CD (berlabel B dan C), CD-EF (berlabel E dan F), dan EF - FG (dilabeli dengan F dan F). Derajat AB dan FG adalah 1 sedangkan derajat CD dan EF adalah 2. Berikut adalah skema grafik abstrak dan label tepinya:

Mari kita mulai dengan FG, salah satu dari node derajat-satu. Karena memiliki derajat 1, ada sisi unik EF - FG yang terhubung dengannya, berlabel F. Menginisialisasi polyline dengan busur G -> F. Karena label menunjuk titik akhir umum GF dan EF, kita tidak perlu membuat koneksi baru. Hapus tepi EF - FG dari grafik dan perpanjang polyline dengan EF melalui G -> F -> E.

Penghapusan tepi ini mengurangi derajat EF dari 2 menjadi 1, meninggalkannya dengan satu tepi ke busur CD berlabel E dan D. Ini memberitahu Anda untuk memperpanjang polyline dari E ke D (dengan segmen garis baru di sana) dan kemudian sepanjang arc CD: G -> F -> E -> D -> C. Dengan cara yang sama, setelah menghapus ED - CD tepi, Anda akan memperluas polyline lebih jauh ke bentuk akhir G -> F -> E -> D -> C -> B -> A. Anda berhenti karena semua tepi telah dihapus dari grafik: ini menunjukkan prosedur telah berhasil.

Menyusul dari jawaban whuber, jika Anda ingin melakukan ini dengan Python kemudian lihat di perpustakaan NetworkX yang memiliki semua jenis fungsi yang berkaitan dengan grafik, node, dan tepi. Saya pikir itu adalah fungsi Traversal yang mengimplementasikan apa yang dideskripsikan whuber. Ini juga mencakup fungsionalitas menggambar dasar.

Setelah Anda memiliki pesanan baris, maka Anda dapat dengan mudah membuat geometri di Shapely untuk melakukan analisis tipe GIS lebih lanjut, atau ditampilkan di MatPlotLib, ekspor ke GeoJSON dll.

Saya akan menghitung jarak antara setiap segmen awal dan segmen akhir, dan kemudian bergabung dengan yang dengan jarak terpendek di antara mereka?

Anda memiliki banyak segmen, tanpa urutan atau orientasi tertentu. Anda tidak tahu mana yang benar-benar menyentuh atau tumpang tindih, dan mana yang dekat.

Untuk setiap segmen hanya titik awal dan titik akhir yang penting. Tujuannya adalah untuk membuat satu polyline besar, orientasi polyline itu tidak penting, kurasa.

Dalam hal ini saya akan membuat beberapa set / array segmen, mulai dengan yang pertama, yang sepenuhnya acak.

Dalam pseudocode, lakukan sesuatu seperti

all_segments = set of all segments

# take the first segment out of set
new_polyline = all_segments.pop

until all_segments.empty?
  start_segm = find_segment_closest_to(new_polyline.start_point)
  remove_from_all_segments(start_segm)
  expand_polyline_at_begin(new_polyline, start_segm) 
  end_segm = find_segment_closest_to(new_polyline.end_point)
  expand_polyline_at_end(new_polyline, end_segm)
  remove_from_all_segments(end_segm)
end

Sesuatu seperti itu? Itu adalah level yang sangat tinggi. Anda harus menangani kasus batas. Saya kira Anda tahu atau mungkin celah / jarak terbesar yang mungkin, karena Anda akan perlu untuk entah bagaimana mengecualikan poin yang ditemukan: jika titik terdekat yang mungkin adalah di ujung polyline daripada itu bukan pilihan :) The Cara termudah untuk menanganinya adalah dengan menentukan jarak gap maksimum. Ini juga akan membatasi jumlah poin yang harus Anda perhatikan untuk setiap segmen.

[EDIT: detailkan find_segment_closes_to]

Untuk membuatnya sangat jelas bagaimana saya akan menemukan segmen yang ditutup, saya akan menulis terlebih dahulu pendekatan yang sangat kasar:

def find_segment_closes_to(point)
  closest_point = nothing
  closest_distance = MAX_GAP_RANGE
  all_segments.each do |segment|
    if distance(segment.end_point, point) < closest_distance
      closest_point = segment.end_point
      closest_segment = segment
      closest_distance = distance(segment.end_point, point)
   else if distance(segment.start_point, point) < closest_distance
      closest_point = segment.start_point
      closest_segment = segment
      closest_distance = distance(segment.start_point, point)
    end       
  end  
  # the closest segment
  return closest_segment
end     

Ini adalah pendekatan yang sangat kasar, yang akan mengulangi semua segmen dan memeriksa setiap titik akhir yang terdekat.

Idealnya Anda akan memiliki beberapa struktur data di mana Anda bisa meminta semua titik awal dan akhir yang berada dalam jangkauan dan hanya menemukan titik terdekat di antara mereka.

Apakah itu membantu? Saya harap ini memulainya.