我在二維空間中有一個正方形（寬度=高度）。該正方形當前由兩個點定義：BottomLeft(X1,Y1) 和 TopRight(X2,Y2)。正方形是軸對齊的，因此找到其他兩個角就像 (X1, Y2) 和 (X2, Y1) 一樣簡單。我還有兩點——一是總是在方陣內，二是肯定在方陣外。它們不一定位于廣場的中心——它們可以位于任何地方。我也知道他們的坐標。我需要的是找到這兩點定義的線段與正方形邊之間的交點。我還想知道我與正方形的哪一邊相交。給我帶來麻煩的是線對角線延伸并且靠近正方形角的情況 - 例如它可以與頂線或邊線相交。暴力法是嘗試計算正方形每條邊的交點并檢查它是否存在?？梢酝ㄟ^計算第二個點相對于正方形的位置并丟棄兩條線來優化它（例如，如果 X 和 Y 坐標都增加，則無需檢查正方形的底部和左側）。我想知道是否有更好/更快的解決方案來解決我的問題？我會用Java寫
2 回答
萬千封印
TA貢獻1891條經驗 獲得超3個贊
設內點為(x0, y0)，外點為(ox, oy)
以參數形式表示線
vx = ox - x0
vy = oy - y0
//equations:
x = x0 + vx * t
y = y0 + vy * t
現在根據方向找到潛在的邊界位置：
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
一般情況下查找與水平和垂直邊緣線相交的參數
tx = (ex - x0) / vx
ty = (ey - y0) / vy
并獲取較小參數值的交集
if tx <= ty then //meet vertical edge first
return cx = ex, cy = y0 + tx * vy
else
return cx = x0 + ty * vx, cy = ey
蕭十郎
TA貢獻1815條經驗 獲得超13個贊
高效的解決方案：
我假設您知道哪個點在正方形（也可以是矩形）內。
從所有其他點（第二個端點和四個角）中減去該點的坐標?？紤]通過延伸正方形的邊而將平面細分為九個區域。需要進行四次符號測試才能知道另一個點位于八個外部區域中的哪一個。
然后，如果該點位于“邊”區域，您就隱含地知道穿過了哪邊。如果該點位于“角”區域，則必須在兩側之間做出決定，這是通過檢查角位于線段的哪一側來完成的。這需要計算三角形的有符號面積（兩次乘法和一次減法）。
當你知道穿過哪條邊時，使用比例找到交點就很容易了。這需要一個部門。
最后，將其平移回內部點的原始位置。總成本是
四次減法，
四項標志測試，
對于角區域，兩次乘法和一次減法，
一個部門，
兩個補充
加上一點粘合邏輯。
這不能保證是絕對最小值，但必須接近。
添加回答
舉報
0/150
提交
取消