算法 - 打矩形的檢測旋轉矩形內

我上的圖像編輯器項目，在這裏你可以旋轉，裁剪圖像工作。

我目前面臨的問題是，一旦我旋轉了圖像，我想能夠將裁剪框拖到旋轉圖像的邊界內的任何位置。到目前爲止，我一直在尋找Liang-Barsky和Cohen-Sutherland換行算法，以及Separating Axis Theorem，但我很努力地看到如何在我的用例中實現這些。

任何人都可以指向正確的方向嗎？我吠叫錯了樹嗎？

來源

2017-09-14 daviestar

檢查內部矩形的所有四個角都是外矩形內。 – alain

天真的方法是檢查較小矩形的每個線段，看它是否與較大矩形的任何線段相交。你有旋轉矩形的點（假設你知道旋轉角度），所以它只有16條線相交測試。不是最佳的，但它是一個開始。如果可以做出一些假設（如選擇矩形的左側不能與旋轉矩形的右側相交），則可以減少必須進行的測試次數。 –

使用Alain的評論。要檢查角落的內部，只需反轉圖像以使其邊緣對齊。然後你有一個簡單的軸心對齊框問題。

（我的意思不是說你真的要旋轉圖像，僅幾何圖形。）

來源

2017-09-15 12:29:19

謝謝，這是巧妙:)稍微更強烈的反旋轉操作可以在鼠標下進行，然後在鼠標移動我可以檢查是否所有4個角落都在框中。大！ – daviestar

強化？你什麼意思？這必須在0.1微秒以內。 –

javascript中的原生trig函數可能會很慢，所以很高興您的回答允許我策略性地緩存這些計算（在mousedown上）並且不會在60fps（在mousemove上）觸發它們。 – daviestar

如果用戶嘗試製作的運動是[dx，dy]，則考慮從選區的角點到由[dx，dy]（下例中的黃線）轉換的點的線段。這些線可能與某些點（紅點）處的旋轉圖像邊界（綠線）相交。如果沒有交集，那麼運動是合法的。如果有一個或多個交叉點，它們會告訴你該運動是合法的哪一點;最接近其原始位置的交點（檢查水平距離或垂直距離就足以確定這一點）確定最大移動（示例中的右下角）。那麼你可以限制翻譯到這一點。

取決於哪個象限的移動的方向是在（朝向例如右上角）可以跳過檢查角部中的一個（在本例中左下角）;其他角落將首先碰到邊界。
通過比較移動的方向和圖像的旋轉角度，您也可以跳過檢查兩個邊界（示例中的底部和左邊）。
所以你需要檢查3條線段與2條線段的交點。對於線段交叉碼，參見例如this question。

如果用戶只拖動一側，並延長矩形而不是移動矩形，那麼您只需檢查正在移動的兩個角。

來源

2017-09-15 01:12:58 m69

@daviestar難道你不認爲知道最後的法律位置是有用的嗎？或者僅僅是你認爲這與伊夫的回答相比這是不必要的複雜？ – m69

算法 - 打矩形的檢測旋轉矩形內

回答

相關問題