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.)
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.
sumber
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?
sumber
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 .
sumber
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 siniF
maksudnyaphi
, atauT
dalam notasi wikipedia di sini ( http://en.wikipedia.org/wiki/Curvature ).Katakanlah Anda memiliki urutan tiga poin, p0, p1 dan p2. menghitung jarak
s
antara 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. YaituDT
. Divisi menghasilkan kelengkunganK0_1
. ambil p1, p2 dan p3 untuk menghitungK1_2
dan seterusnya.Saya bertanya-tanya apakah Anda mendapatkan kontur sebagai polyline, bukan sebagai piksel yang diberikan. Anda mengatakan 100px sehingga membuat saya sedikit khawatir.
sumber