Saya memerlukan fungsi dasar untuk menemukan jarak terpendek antara titik dan segmen garis. Jangan ragu untuk menulis solusi dalam bahasa apa pun yang Anda inginkan; Saya bisa menerjemahkannya ke dalam apa yang saya gunakan (Javascript).
EDIT: Segmen baris saya ditentukan oleh dua titik akhir. Jadi segmen garis saya AB
ditentukan oleh dua poin A (x1,y1)
dan B (x2,y2)
. Saya mencoba mencari jarak antara segmen garis ini dan satu titik C (x3,y3)
. Keterampilan geometri saya berkarat, jadi contoh yang saya lihat membingungkan, saya minta maaf untuk mengakui.
language-agnostic
geometry
distance
line-segment
Eli Courtwright
sumber
sumber
Jawaban:
Eli, kode yang Anda pilih salah. Suatu titik di dekat garis di mana segmen terletak tetapi jauh salah satu ujung segmen akan dinilai secara salah di dekat segmen.Pembaruan: Jawaban yang salah tersebut tidak lagi diterima.Berikut ini beberapa kode yang benar, di C ++. Ini mengandaikan kelas 2D-vektor
class vec2 {float x,y;}
, pada dasarnya, dengan operator untuk menambahkan, subract, skala, dll, dan fungsi produk jarak dan titik (yaitux1 x2 + y1 y2
)EDIT: Saya membutuhkan implementasi Javascript, jadi ini dia, tanpa dependensi (atau komentar, tetapi ini adalah port langsung di atas). Poin direpresentasikan sebagai objek dengan
x
dany
atribut.EDIT 2: Saya membutuhkan versi Java, tetapi yang lebih penting, saya membutuhkannya di 3d bukan 2d.
sumber
p
ke garis adalah titik pada garis yang paling dekat dengannyap
. (Dan tegak lurus terhadap garis proyeksi akan melewatip
.) Jumlaht
adalah seberapa jauh sepanjang segmen garis dariv
kew
proyeksi jatuh. Jadi jikat
0 proyeksi jatuh tepatv
; jika 1, aktifw
; misalnya 0,5, misalnya, maka separuh jalan. Jikat
kurang dari 0 atau lebih besar dari 1 itu jatuh pada garis melewati satu ujung atau yang lain dari segmen. Dalam hal ini jarak ke segmen akan menjadi jarak ke ujung yang lebih dekat.Berikut ini adalah kode lengkap paling sederhana dalam Javascript.
x, y adalah titik target Anda dan x1, y1 ke x2, y2 adalah segmen garis Anda.
DIPERBARUI: perbaiki untuk masalah garis 0 panjang dari komentar.
sumber
Ini adalah implementasi yang dibuat untuk FINANCE LINE SEGMENTS, bukan garis tak terbatas seperti kebanyakan fungsi lain di sini (itulah sebabnya saya membuat ini).
Implementasi teori oleh Paul Bourke .
Python:
AS3:
Jawa
sumber
distAnother(0, 0, 4, 0, 2, 2)
memberikan 2.8284271247461903 (salah).distAnother(0., 0., 4., 0., 2., 2.)
memberi 2.0 (benar). Harap perhatikan hal ini. Saya pikir kode dapat ditingkatkan untuk memiliki konversi mengambang di suatu tempat.Di utas pertanyaan saya sendiri bagaimana cara menghitung jarak 2D terpendek antara titik dan segmen garis dalam semua kasus di C, C # / .NET 2.0 atau Java? Saya diminta untuk memberikan jawaban C # di sini ketika saya menemukan satu: jadi ini dia, dimodifikasi dari http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :
Saya @SO bukan untuk menjawab tetapi mengajukan pertanyaan jadi saya harap saya tidak mendapatkan jutaan suara untuk beberapa alasan tetapi membangun kritik. Saya hanya ingin (dan didorong) untuk berbagi ide orang lain karena solusi di utas ini baik dengan beberapa bahasa eksotis (Fortran, Mathematica) atau ditandai sebagai salah oleh seseorang. Satu-satunya yang berguna (oleh Grumdrig) bagi saya ditulis dengan C ++ dan tidak ada yang menandainya salah. Tetapi tidak ada metode (titik dll.) Yang dipanggil.
sumber
Dalam F #, jarak dari titik
c
ke segmen garis antaraa
danb
diberikan oleh:Vektor
d
menunjuk daria
keb
sepanjang segmen garis. Produk titikd/s
denganc-a
memberikan parameter titik pendekatan terdekat antara garis tak terbatas dan titikc
. Fungsimin
danmax
digunakan untuk menjepit parameter ini ke rentang0..s
sehingga titik terletak di antaraa
danb
. Akhirnya, panjangnyaa+p-c
adalah jarak daric
ke titik terdekat pada segmen garis.Contoh penggunaan:
sumber
(a + p - c).Length
lambda
danp
sebagailet lambda = (c - a) * d / (s * s)
danlet p = a + (lambda |> max 0.0 |> min 1.0) * d
, masing-masing. Setelah itu fungsi mengembalikan jarak yang benar misalnya untuk kasus di manaa = (0,1)
,b = (1,0)
danc = (1,1)
.Bagi siapa pun yang tertarik, inilah konversi sepele kode Javascript Joshua ke Objective-C:
Saya membutuhkan solusi ini untuk bekerja
MKMapPoint
sehingga saya akan membagikannya jika ada orang lain yang membutuhkannya. Hanya beberapa perubahan kecil dan ini akan mengembalikan jarak dalam meter:sumber
Dalam Mathematica
Ini menggunakan deskripsi parametrik segmen, dan memproyeksikan titik ke garis yang ditentukan oleh segmen. Saat parameter beralih dari 0 ke 1 di segmen, jika proyeksi berada di luar batas ini, kami menghitung jarak ke titik terkait, alih-alih garis lurus normal ke segmen.
Merencanakan hasil:
Plot titik-titik itu lebih dekat daripada jarak cutoff :
Contour Plot:
sumber
Hei, saya baru saja menulis ini kemarin. Ada dalam Actionscript 3.0, yang pada dasarnya adalah Javascript, meskipun Anda mungkin tidak memiliki kelas Point yang sama.
Juga, ada diskusi yang cukup lengkap dan mudah dibaca dari masalah di sini: notejot.com
sumber
Untuk yang malas, inilah port Objective-C saya dari solusi @ Grumdrig di atas:
sumber
return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
sqrtf(x) = x*x
.Tidak dapat menahan pengkodean dengan python :)
Ditto for fortran :)
sumber
Berikut ini ejaan yang lebih lengkap dari solusi Grumdrig. Versi ini juga mengembalikan titik terdekat itu sendiri.
sumber
Satu solusi garis menggunakan arctangents:
Idenya adalah untuk memindahkan A ke (0, 0) dan memutar segitiga searah jarum jam untuk membuat C berbaring di sumbu X, ketika ini terjadi, By akan menjadi jarak.
C #
Satu baris C # (untuk dikonversi ke SQL)
sumber
Pertimbangkan modifikasi ini untuk jawaban Grumdrig di atas. Sering kali Anda akan menemukan bahwa ketidaktepatan floating point dapat menyebabkan masalah. Saya menggunakan ganda dalam versi di bawah ini, tetapi Anda dapat dengan mudah berubah menjadi mengapung. Bagian yang penting adalah ia menggunakan epsilon untuk menangani "slop". Selain itu, Anda akan berkali-kali ingin tahu DI MANA persimpangan itu terjadi, atau jika itu terjadi sama sekali. Jika t yang dikembalikan <0,0 atau> 1,0, tidak ada tabrakan terjadi. Namun, bahkan jika tidak ada tabrakan, berkali-kali Anda ingin tahu di mana titik terdekat pada segmen ke P, dan dengan demikian saya menggunakan qx dan qy untuk mengembalikan lokasi ini.
sumber
Saya berasumsi Anda ingin menemukan terpendekjarak antara titik dan segmen garis; untuk melakukan ini, Anda perlu menemukan garis (lineA) yang tegak lurus dengan segmen garis Anda (lineB) yang melewati titik Anda, menentukan persimpangan antara garis itu (lineA) dan garis Anda yang melewati segmen garis Anda (lineB) ; jika titik itu berada di antara dua titik segmen garis Anda, maka jaraknya adalah jarak antara titik Anda dan titik yang baru saja Anda temukan yang merupakan perpotongan garis A dan garis B; jika titik tersebut tidak berada di antara dua titik segmen garis Anda, Anda perlu mendapatkan jarak antara titik Anda dan yang lebih dekat dari dua ujung segmen garis; ini dapat dilakukan dengan mudah dengan mengambil jarak kuadrat (untuk menghindari akar kuadrat) antara titik dan dua titik segmen garis; mana yang lebih dekat, ambil akar kuadrat dari yang itu.
sumber
Implementasi C ++ / JavaScript Grumdrig sangat berguna bagi saya, jadi saya telah menyediakan port langsung Python yang saya gunakan. Kode lengkapnya ada di sini .
sumber
Kode Matlab, dengan built-in "self test" jika mereka memanggil fungsi tanpa argumen:
sumber
Dan sekarang solusi saya juga ...... (Javascript)
Ini sangat cepat karena saya mencoba menghindari fungsi Math.pow.
Seperti yang Anda lihat, pada akhir fungsi saya memiliki jarak garis.
kode berasal dari lib http://www.draw2d.org/graphiti/jsdoc/#!/example
sumber
dikodekan dalam t-sql
intinya adalah (@px, @py) dan segmen baris berjalan dari (@ax, @ay) ke (@bx, @by)
sumber
Sepertinya hampir semua orang di StackOverflow telah menyumbangkan jawaban (23 jawaban sejauh ini), jadi inilah kontribusi saya untuk C #. Ini sebagian besar didasarkan pada jawaban oleh M. Katz, yang pada gilirannya didasarkan pada jawaban oleh Grumdrig.
Dan inilah program pengujian kecil.
Seperti yang Anda lihat, saya mencoba mengukur perbedaan antara menggunakan versi yang menghindari metode Sqrt () dan versi normal. Tes saya menunjukkan Anda mungkin dapat menghemat sekitar 2,5%, tapi saya bahkan tidak yakin akan hal itu - variasi dalam berbagai uji coba memiliki urutan yang sama besarnya. Saya juga mencoba mengukur versi yang diposting oleh Matti (ditambah optimasi yang jelas), dan versi itu tampaknya sekitar 4% lebih lambat daripada versi berdasarkan kode Katz / Grumdrig.
Sunting: Kebetulan, saya juga mencoba mengukur metode yang menemukan jarak ke garis tak terbatas (bukan segmen garis) menggunakan produk silang (dan Sqrt ()), dan ini sekitar 32% lebih cepat.
sumber
Ini adalah versi C ++ devnullicus yang dikonversi ke C #. Untuk implementasi saya, saya perlu tahu titik persimpangan dan menemukan solusinya untuk bekerja dengan baik.
sumber
Ini dia menggunakan Swift
sumber
C #
Diadaptasi dari @Grumdrig
sumber
Solusi 2D dan 3D
Pertimbangkan perubahan basis sedemikian rupa sehingga segmen garis menjadi
(0, 0, 0)-(d, 0, 0)
dan intinya(u, v, 0)
. Jarak terpendek terjadi di pesawat itu dan diberikan oleh(jarak ke salah satu titik akhir atau ke garis pendukung, tergantung pada proyeksi ke garis. Lokus iso-jarak terbuat dari dua setengah lingkaran dan dua segmen garis.)
Dalam ungkapan di atas, d adalah panjang segmen AB, dan u, v masing-masing adalah produk skalar dan (modulus dari) produk silang AB / d (vektor satuan ke arah AB) dan AC. Karena itu secara vectorially,
sumber
lihat Matlab GEOMETRY toolbox di situs web berikut: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html
ctrl + f dan ketik "segmen" untuk menemukan fungsi terkait segmen garis. fungsi "segment_point_dist_2d.m" dan "segment_point_dist_3d.m" adalah yang Anda butuhkan.
Kode GEOMETRI tersedia dalam versi C dan versi C ++ dan versi FORTRAN77 dan versi FORTRAN90 dan versi MATLAB.
sumber
Versi AutoHotkeys berdasarkan Javascript Joshua:
sumber
Tidak melihat implementasi Java di sini, jadi saya menerjemahkan fungsi Javascript dari jawaban yang diterima ke kode Java:
sumber
Versi WPF:
sumber
Inilah kode yang akhirnya saya tulis. Kode ini mengasumsikan bahwa suatu titik didefinisikan dalam bentuk
{x:5, y:7}
. Perhatikan bahwa ini bukan cara yang paling efisien mutlak, tetapi ini adalah kode paling sederhana dan paling mudah dipahami yang bisa saya buat.sumber
Fungsi di atas tidak berfungsi pada garis vertikal. Berikut adalah fungsi yang berfungsi dengan baik! Baris dengan poin p1, p2. dan CheckPoint adalah p;
sumber
Berikut hal yang sama dengan jawaban C ++ tetapi diport ke pascal. Urutan parameter titik telah berubah agar sesuai dengan kode saya tetapi merupakan hal yang sama.
sumber