Re: [運算] 怎算出兩條線有沒有交叉？交點已回收

看板MATLAB作者Roronoa (羅羅亞)時間15年前 (2011/02/14 17:25)推噓3(3推 0噓 1→)

留言4則, 4人參與討論串3/3 (看更多)

冷飯熱炒一下在眾多討論怎麼沒人覺得我的方法最簡單勒@@ (程式po在上一篇) 這邊說明一下概念如果有點 a b c d ，要判斷線段 ab , cd 是否有交點只要判斷 1. ab 是否在直線cd 同側 2. cd 是否在直線ab 同側上面1&2 只要有一項符合則線段 ab 和線段cd無交點 -- 演算法如下 step1 用 abcd 點座標，公式解直線ab和直線cd係數得直線 ab = p1*x + p2*y + p3 直線 cd = q1*x + q2*y + q3 step2 判斷兩點 c d 是否在直線ab同側根據直線性質，把直線同側的點代入直線方程式，會得到相同正負結果 ex c(1,0) d(0,1) ab = x+y c 和 d 代入 x+y 均為 1>0 同號 => c,d 在直線ab同側反之異號則不同側所以這步只判斷點c,d座標代入直線ab的結果是否 > 0 (同號) 點a,b座標代入直線cd的結果是否 > 0 即可得知兩線段是否相交綜合兩個步驟，全部都只要簡單的加減乘除... -- 寫完上面手癢直接 function code都補上好了，input(a,b,c,d)為點座標 function cross=test(a,b,c,d) p1 = b(2)-a(2); p2 = a(1)-b(1); p3 = b(1)*a(2)-a(1)*b(2); q1 = d(2)-c(2); q2 = c(1)-d(1); q3 = d(1)*c(2)-c(1)*d(2); sign1 = ( p1*c(1)+p2*c(2)+p3 ) * ( p1*d(1)+p2*d(2)+p3 ); sign2 = ( q1*a(1)+q2*a(2)+q3 ) * ( q1*b(1)+q2*b(2)+q3 ); % cross = sign1*sign2<0; 修改此行 cross = (sign1 < 0 && sign2 < 0) end Example: a = rand(1,2);b = rand(1,2);c = rand(1,2);d = rand(1,2); test(a,b,c,d) plot([a(1) b(1)] , [a(2) b(2)],'o-'); hold on; plot([c(1) d(1)] , [c(2) d(2)],'o-r'); hold off; -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.208.41

推

gamer

02/14 17:29, , 1^F

02/14 17:29, 1^F

→

Roronoa

02/14 17:40, , 2^F

02/14 17:40, 2^F

修改最後的判斷跟繪圖感謝版友指正~ ※ 編輯: Roronoa 來自: 140.113.208.41 (02/14 18:09)

推

bridge23

02/14 21:04, , 3^F