Memesan satu set poin yang tidak terorganisir di sepanjang kurva

Saya memiliki satu set poin 3D (yang saya pulihkan dari perpustakaan yang melakukan penghentian benda padat) yang termasuk dalam kurva (yaitu, tepi benda padat). Itu berarti bahwa kurva pasti melewati masing-masing titik ini.

Namun demikian, set titiknya tidak berurutan jadi saya perlu mengurutkannya agar dapat menggambar kurva ini dengan benar.

Apakah ada pendekatan yang diketahui untuk jenis masalah ini?

Beberapa informasi tambahan:

Kurva bersifat parametrik secara umum (splines / bezier, irisan lingkaran ..).
Poin diberikan sebagai koordinat floating point.
Poin-poinnya dikemas sangat padat (tetapi mereka bisa sepadat yang saya inginkan). Untuk memberi Anda gambaran, untuk kurva yang menempati 19 unit di x, 10 unit di x dan 5 unit di z, saya kutip urutan poin dalam segmen kurva: (20.7622, 25.8676, 0) (20.6573, 25.856, 0) (20.5529, 25.8444, 0) (20.4489, 25.8329, 0) (20.3454, 25.8213, 0)

geometry mesh curve andrea.al
sumber

Sekalipun kita mengetahui urutannya hingga jumlah kurva yang tak terbatas sesuai dengan poin. Bahkan jika kita menambahkan kendala tambahan, maka ujung terbuka bermasalah karena orientasi singgung mereka dapat berubah-ubah. Sebuah gambar di sini

joojaa

@ joojaa Ya, Anda benar. Tapi karena pengepakan poin sangat padat, saya tidak berharap itu tepat. Jika saya mendapatkan urutan yang benar, saya berencana untuk menghubungkan urutan titik sebagai polyline.

andrea.al

Dalam kode yang perlu memesan poin, apakah Anda mengetahui bentuk parametrik kurva? (Jika tidak, saya akan menghapus jawaban pertama saya, karena mengharuskan Anda untuk mengetahui bentuk parametrik.)

Martin Ender

@ MartinBüttner Ya, saya memiliki akses ke bentuk parametrik kurva, jika diperlukan.

andrea.al

Tolong tunjukkan set poin khas!

Yves Daoust

Jawaban:

Anda memiliki contoh masalah yang disebut rekonstruksi kurva dari titik yang tidak terorganisir . Sekarang Anda tahu apa yang harus dicari, Anda akan menemukan beberapa metode, seperti kerak, kerak-NN, dll. Berikut adalah beberapa tautan:

Applet Rekonstruksi Kurva Kerak
Rekonstruksi Kurva oleh Tamal Dey
Rekonstruksi Kurva dan Permukaan: Algoritma dengan Analisis Matematika , buku karya Tamal K. Dey, Cambridge University Press, 2006

Karena Anda berurusan dengan kurva dan sampelnya padat, saya sarankan Anda menghitung pohon spanning minimal Euclidean.

lhf
sumber

Setelah beberapa klarifikasi, mungkin ada pendekatan yang jauh lebih baik yang bahkan tidak perlu mengetahui bentuk parametrik kurva, dan juga menghindari langkah minimisasi numerik yang berpotensi bermasalah.

Jika kurva tidak berpotongan sendiri dan titik-titik cukup padat pada kurva (dan maksud saya mereka harus lebih dekat daripada dua titik pada kurva yang bukan milik segmen yang sama, misalnya oleh pembungkus kurva sekitar sendiri), maka Anda dapat dengan mudah menentukan titik sebelumnya dan berikutnya untuk setiap sampel:

$O(n \log n)$
Anda harus melakukan perawatan khusus untuk titik akhir. Dua tetangga terdekat mereka akan menjadi dua poin berikutnya di sepanjang kurva alih-alih satu di setiap sisi. Anda dapat mendeteksi ini secara heuristik jika rasio jarak ke dua tetangga berbeda lebih dari beberapa ambang batas (1,5 katakan, tergantung pada kelancaran kurva Anda dan seberapa padat poin yang dikemas). Atau Anda dapat memperlakukan data tetangga terdekat Anda sebagai grafik, di mana Anda akan menemukan bahwa dua tetangga titik akhir saling menunjuk (yang seharusnya tidak terjadi di tempat lain dalam grafik).
Sekarang Anda cukup memilih satu titik akhir, dan berjalan di sepanjang tetangga terdekat (selalu memilih yang tidak Anda datangi) untuk melintasi titik-titik di sepanjang kurva.

$\theta$

Martin Ender
sumber

$(X,Y,Z)$ $(x(t), y(t), z(t))$

(X - x (t))^{2} + (Y - y (t))^{2} + (Z - z (t))^{2}

$(X-x(t))^2+(Y-y(t))^2+(Z-z(t))^2$

$t$

$t$ $t$ $t$

Martin Ender
sumber