首頁猿問直線和正方形之間的交點(diǎn)

直線和正方形之間的交點(diǎn)

Java

皈依舞 2023-08-16 16:20:54

我在二維空間中有一個(gè)正方形（寬度=高度）。該正方形當(dāng)前由兩個(gè)點(diǎn)定義：BottomLeft(X1,Y1) 和 TopRight(X2,Y2)。正方形是軸對(duì)齊的，因此找到其他兩個(gè)角就像 (X1, Y2) 和 (X2, Y1) 一樣簡單。我還有兩點(diǎn)——一是總是在方陣內(nèi)，二是肯定在方陣外。它們不一定位于廣場的中心——它們可以位于任何地方。我也知道他們的坐標(biāo)。我需要的是找到這兩點(diǎn)定義的線段與正方形邊之間的交點(diǎn)。我還想知道我與正方形的哪一邊相交。給我?guī)砺闊┑氖蔷€對(duì)角線延伸并且靠近正方形角的情況 - 例如它可以與頂線或邊線相交。暴力法是嘗試計(jì)算正方形每條邊的交點(diǎn)并檢查它是否存在。可以通過計(jì)算第二個(gè)點(diǎn)相對(duì)于正方形的位置并丟棄兩條線來優(yōu)化它（例如，如果 X 和 Y 坐標(biāo)都增加，則無需檢查正方形的底部和左側(cè)）。我想知道是否有更好/更快的解決方案來解決我的問題？我會(huì)用Java寫

查看完整描述

2 回答

萬千封印

TA貢獻(xiàn)1891條經(jīng)驗(yàn) 獲得超3個(gè)贊

設(shè)內(nèi)點(diǎn)為(x0, y0)，外點(diǎn)為(ox, oy)

以參數(shù)形式表示線

vx = ox - x0

vy = oy - y0

//equations:

x = x0 + vx * t

y = y0 + vy * t

現(xiàn)在根據(jù)方向找到潛在的邊界位置：

if vx > 0 then

ex = x2

else

ex = x1

if vy > 0 then

ey = y2

else

ey = y1

檢查水平/垂直線方向的額外情況：

if vx = 0 then

return cx = x0, cy = ey

if vy = 0 then

return cx = ex, cy = y0

一般情況下查找與水平和垂直邊緣線相交的參數(shù)

tx = (ex - x0) / vx

ty = (ey - y0) / vy

并獲取較小參數(shù)值的交集

if tx <= ty then //meet vertical edge first

return cx = ex, cy = y0 + tx * vy

else

return cx = x0 + ty * vx, cy = ey

反對(duì) 回復(fù) 2023-08-16

蕭十郎

TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超13個(gè)贊

高效的解決方案：

我假設(shè)您知道哪個(gè)點(diǎn)在正方形（也可以是矩形）內(nèi)。

從所有其他點(diǎn)（第二個(gè)端點(diǎn)和四個(gè)角）中減去該點(diǎn)的坐標(biāo)?？紤]通過延伸正方形的邊而將平面細(xì)分為九個(gè)區(qū)域。需要進(jìn)行四次符號(hào)測(cè)試才能知道另一個(gè)點(diǎn)位于八個(gè)外部區(qū)域中的哪一個(gè)。

然后，如果該點(diǎn)位于“邊”區(qū)域，您就隱含地知道穿過了哪邊。如果該點(diǎn)位于“角”區(qū)域，則必須在兩側(cè)之間做出決定，這是通過檢查角位于線段的哪一側(cè)來完成的。這需要計(jì)算三角形的有符號(hào)面積（兩次乘法和一次減法）。

當(dāng)你知道穿過哪條邊時(shí)，使用比例找到交點(diǎn)就很容易了。這需要一個(gè)部門。

最后，將其平移回內(nèi)部點(diǎn)的原始位置?？偝杀臼?/p>