Mengukur kelurusan segmen kurva (direpresentasikan sebagai polyline)

11

Saya sedang mengerjakan algoritma pelabelan kontur ketinggian otomatis dan salah satu faktor yang ingin saya perhitungkan ketika menentukan posisi label adalah seberapa "lurus" segmen tertentu dari sebuah kontur. Semakin lurus, semakin besar kemungkinan akan digunakan untuk menempatkan label pada segmen itu.

Setiap kontur diwakili oleh polyline (tetapi dengan titik-titik yang berdekatan agar terlihat seperti kurva dengan mata telanjang). Saya kemudian memiliki panjang tetap (lebar label), katakanlah, 100 piksel. Jika saya secara acak (atau sebaliknya) memilih segmen kontur dengan lebar 100 piksel, saya ingin dapat memperoleh nilai kuantitatif numerik kelurusannya (katakan nol untuk segmen kontur yang benar-benar lurus, beberapa nilai lebih besar dari nol untuk yang tidak segmen begitu lurus, dan nilai ini meningkat seiring dengan meningkatnya kebengkokan).

Saya telah mencari-cari jawaban tetapi saya tidak menemukan sesuatu yang benar-benar berguna. Saya akan berterima kasih atas petunjuk apa pun.

Igor Brejc
sumber

Jawaban:

9

Jawabannya tergantung pada konteks : jika Anda akan menyelidiki hanya sejumlah kecil (dibatasi) segmen, Anda mungkin dapat membeli solusi yang mahal secara komputasi. Namun, sepertinya Anda ingin menggabungkan perhitungan ini dalam beberapa jenis pencarian untuk mendapatkan label yang bagus. Jika demikian, akan sangat menguntungkan untuk memiliki solusi yang cepat secara komputasi atau memungkinkan pembaruan cepat dari solusi ketika segmen garis kandidat sedikit bervariasi.

Misalnya, Anda berniat melakukan pencarian sistematismelintasi seluruh komponen yang terhubung dari sebuah kontur, direpresentasikan sebagai urutan titik P (0), P (1), ..., P (n). Ini akan dilakukan dengan menginisialisasi satu pointer (indeks ke dalam urutan) s = 0 ("s" untuk "mulai") dan pointer lain f (untuk "selesai") menjadi indeks terkecil untuk jarak mana (P (f), P (s))> = 100, dan kemudian memajukan s selama jarak (P (f), P (s + 1))> = 100. Ini menghasilkan kandidat polyline (P (s), P (s + 1) ..., P (f-1), P (f)) untuk evaluasi. Setelah mengevaluasi "kebugaran" -nya untuk mendukung label, Anda kemudian akan menambah s dengan 1 (s = s + 1) dan melanjutkan untuk meningkatkan f ke (katakanlah) f 'dan s ke s' sampai sekali lagi calon polyline melebihi batas minimum rentang 100 diproduksi, diwakili sebagai (P (s '), ... P (f), P (f + 1), ..., P (f')). Dengan demikian, simpul P ... s (P ' Sangat diinginkan bahwa kebugaran dapat dengan cepat diperbarui dari pengetahuan hanya simpul terjatuh dan ditambahkan. (Prosedur pemindaian ini akan dilanjutkan sampai s = n; seperti biasa, f harus diizinkan untuk "membungkus" dari n kembali ke 0 dalam proses.)

Pertimbangan ini mengesampingkan banyak kemungkinan ukuran kebugaran ( sinuositas , tortuositas , dll.) Yang mungkin menarik. Ini mengarahkan kita untuk mendukung langkah-langkah berbasis L2 , karena mereka biasanya dapat diperbarui dengan cepat ketika data yang mendasarinya sedikit berubah. Mengambil analogi dengan Analisis Komponen Utama menunjukkan bahwa kami memiliki ukuran berikut (di mana yang kecil lebih baik, seperti yang diminta): gunakan yang lebih kecil dari dua nilai eigen dari matriks kovariansdari titik koordinat. Secara geometris, ini adalah salah satu ukuran deviasi "dari" sisi-ke-sisi dari simpul-simpul dalam bagian kandidat dari polyline. (Salah satu interpretasi adalah bahwa akar kuadratnya adalah semi-sumbu yang lebih kecil dari elips yang mewakili momen kedua inersia dari simpul-simpul polyline.) Itu akan sama dengan nol hanya untuk set simpul collinear; jika tidak, itu melebihi nol. Ini mengukur rata-rata penyimpangan sisi-ke-sisi relatif terhadap garis dasar 100 piksel yang dibuat pada awal dan akhir polyline, dan karenanya memiliki interpretasi sederhana.

Karena matriks kovarians hanya 2 per 2, nilai eigen dengan cepat ditemukan dengan menyelesaikan persamaan kuadrat tunggal. Selain itu, matriks kovarians adalah jumlah kontribusi dari masing-masing simpul dalam polyline. Dengan demikian, ia diperbarui dengan cepat ketika titik-titik dikeluarkan atau ditambahkan, yang mengarah ke algoritma O (n) untuk kontur titik-n: ini akan berskala baik ke kontur yang sangat rinci yang dibayangkan dalam aplikasi.

Berikut adalah contoh hasil dari algoritma ini. Titik-titik hitam adalah simpul kontur. Garis merah solid adalah segmen polyline kandidat terbaik dengan panjang ujung ke ujung lebih besar dari 100 dalam kontur itu. (Calon yang jelas secara visual di kanan atas tidak cukup lama.)

Angka

whuber
sumber
Wow, Anda membuat saya tersesat di sana :). Anda benar tentang pencarian sistematis, saya sudah harus melakukan itu untuk mendapatkan garis singgung dari setiap polyline / polygon vertex (label horizontal lebih disukai daripada yang vertikal), jadi secara teori saya dapat memperluas pencarian ini untuk mencakup pengukuran lain. BTW: apakah Anda menghasilkan plot sampel menggunakan algoritma aktual atau secara manual?
Igor Brejc
1
Ilustrasi ini nyata, tetapi implementasi yang saya gunakan tidak menggunakan prosedur pembaruan kovarians dan oleh karena itu tidak optimal secara komputasi.
whuber
2
Grafik di akhir membuat jawaban ini lebih luar biasa
Ragi Yaser Burhum
2
Igor, saya harus menyebutkan bahwa arah label datang secara gratis: diberikan oleh arah sumbu utama elips (vektor eigen yang terkait dengan nilai eigen yang lebih besar). Karena itu, Anda dapat secara bersamaan mencari dengan efisien untuk kombinasi terbaik dari orientasi label dan linearitas kontur bagian.
whuber
3

Dalam komunitas komputer grafis, seringkali perlu untuk menemukan kotak pembatas di sekitar objek. Akibatnya, itu adalah masalah yang dipelajari dengan baik, dengan algoritma cepat. Misalnya, lihat artikel algoritma kotak batas minimum Wikipedia . Anda bisa menemukan persegi panjang area minimum di sekitar polyline Anda, dan kemudian menggunakan rasio aspek persegi panjang, tinggi / panjang. Untuk mendapatkan ukuran yang lebih tepat, Anda bisa melihat penyimpangan polyline dari garis tengah persegi panjang pembatas ini.

Joseph O'Rourke
sumber
1
Saya sudah memikirkan menggunakan min. kotak pembatas, tapi saya melihat dua masalah: a) kompleksitas perhitungan menghitung kotak yang benar-benar minimum (dan dengan demikian dirotasi), b) dua segmen kurva dengan rasio aspek yang sama dapat memiliki kelengkungan yang sangat berbeda (pikirkan sinusoidal kurva dengan amplitudo yang sama tetapi periode gelombang berbeda).
Igor Brejc
1
Senang melihat Anda di sini di halaman GIS, Joseph!
whuber
1
Ya, saya memiliki buku "Geometri Komputasi dalam C" di tangan saya sekarang :)
Igor Brejc
1
Terima kasih atas sambutannya, semuanya! :-) Saya menyadari saran saya bukanlah ukuran yang ideal, tetapi pengkodeannya tidak tersedia (jika Anda memiliki rak yang tepat). Jenis masalah ini telah dipelajari sedikit dalam konteks manufaktur, di mana mereka perlu mengukur kualitas bagian mesin.
Joseph O'Rourke
3

Saya tidak tahu apakah ini membantu, atau bahkan jika itu dianggap sebagai jawaban, tetapi ketika saya duduk di sini memikirkan pertanyaan yang baru saja saya posting, saya punya pemikiran:

Bagaimana jika Anda menempatkan lingkaran dengan jari-jari tertentu pada garis kontur Anda. Lingkaran itu akan memotong garis kontur di setidaknya dua tempat. Semakin lurus garis, semakin pendek jarak sepanjang garis kontur antara dua titik persimpangan. Semakin jauh jarak sepanjang garis kontur antara titik persimpangan, semakin lengkung garis tersebut. Jika ada lebih dari dua titik persimpangan, garis kontur terlalu melengkung.

Anda bisa mengetahui berapa panjang yang akan memberikan indikator kelurusan terbaik, dan mengatur rutin untuk melangkah di setiap garis kontur dan di mana itu cukup lurus, letakkan label.

Saya yakin ini tidak banyak membantu, dan apa yang saya katakan dalam bahasa Inggris jauh lebih sulit dalam bahasa pemrograman apa pun yang Anda gunakan, tetapi ini mungkin permulaan?

Rex-H
sumber
Ide yang menarik. Untuk membuatnya lebih sederhana, Anda bisa menghitung rasio antara panjang segmen di satu sisi dan jarak antara titik awal dan akhir. Ini tidak begitu tepat, tetapi cepat untuk menghitung. Dan ide Anda untuk menggunakan lingkaran akan memungkinkan perhitungan kelurusan yang lebih tepat.
Igor Brejc
3

Pendekatan termudah yang bisa saya pikirkan adalah rasio antara panjang jalur aktual antara awal dan akhir dan jarak terpendek (garis lurus) dari awal ke titik akhir. Garis lurus akan memiliki rasio mendekati satu sedangkan garis yang sangat melengkung akan memiliki rasio yang sangat tinggi.

Ini harus menjadi solusi yang sangat mudah untuk diterapkan.


Pembaruan: Seperti yang diperhatikan Mike dengan benar, ini akan sama dengan Sinuosity .

masukkan deskripsi gambar di sini

underdark
sumber
Apa yang muncul di pikiran saya setelah membaca jawaban Rex :)
Igor Brejc
4
pada dasarnya kebalikan dari sinuositas
Mike T
persis :) ....
underdark
2
Anda benar bahwa ini akan mudah diimplementasikan, karena memperbarui panjang sebagai salah satu pencarian untuk segmen yang sesuai untuk label semudah menambahkan dan mengurangi panjang antara simpul berturut-turut. Namun, sinuositas tidak secara efektif menangkap pengertian di mana kurva dapat berangkat dari linearitas. Misalnya, bandingkan setengah lingkaran diameter 100 dengan urutan linier setengah lingkaran diameter 1 : kedua kurva memiliki sinuositas yang sama, tetapi penyimpangan sisi-ke-sisi yang pertama adalah 100 kali lipat dari yang kedua (yang akan menjadi basis yang bagus untuk label).
whuber
Pertimbangkan bahwa jika polyline Anda menggambar sebuah lingkaran, metode ini akan memberi Anda sinuositas tanpa batas yang mungkin bukan hasil yang diinginkan.
obchardon
1

Dengan mencari "kelengkungan" dan "polyline", saya mendapat info ini Bagaimana saya bisa menemukan kelengkungan dari polyline? . Di sana ia menyarankan menggunakan kembali ke definisi kelengkungan - K= DF/Ds. Di sini Fmaksudnya phi, atau Tdalam notasi wikipedia di sini ( http://en.wikipedia.org/wiki/Curvature ).

Katakanlah Anda memiliki urutan tiga poin, p0, p1 dan p2. menghitung jarak santara p0 dan p1, yang merupakan delta s ( Ds), dengan asumsi poin cukup dekat satu sama lain. Maka Anda perlu delta T ( DT), yang merupakan perubahan dalam vektor tangensial satuan antara p0 dan p1. mungkin ada cara canggih tetapi metode kasar saya bisa memikirkan untuk mengambil dua bujursangkar p0-> p1, p1-> p2, menormalkan masing-masing memiliki panjang satu, kemudian mengambil pengurangan vektor dari keduanya kemudian menentukan besarnya. Yaitu DT. Divisi menghasilkan kelengkungan K0_1. ambil p1, p2 dan p3 untuk menghitung K1_2dan seterusnya.

Saya bertanya-tanya apakah Anda mendapatkan kontur sebagai polyline, bukan sebagai piksel yang diberikan. Anda mengatakan 100px sehingga membuat saya sedikit khawatir.

yosukesabai
sumber
Terima kasih atas tautannya, saya harus mempelajari matematika di baliknya. Saya menyebutkan 100px hanya karena teks label yang diberikan memiliki lebar tertentu (dalam piksel), 100px hanyalah sebuah contoh.
Igor Brejc
Memikirkan kelengkungan adalah ide yang bagus. Lengkungan di seluruh bagian kontur yang sangat halus dengan panjang yang cukup mungkin tepat, tetapi lekukan itu sendiri tidak: zig-zag kecil tunggal akan memiliki kelengkungan yang sangat tinggi, misalnya, tetapi secara keseluruhan akan ngawur. Jadi, pada dasarnya, Anda akan menggunakan beberapa ringkasan statistik deviasi dari linearitas di seluruh bagian polyline. Di antara calon yang mungkin, kelengkungan akan menjadi salah satu perhitungan yang lebih rumit untuk dilakukan.
whuber