在矩形區域中找到最接近的矩形的位置

Question

我在2D城堡防禦上編程，今天我遇到了一個問題，我無法找到一個好的解決方案。見下圖：

http://imgur.com/zOe2Muv

我想找到最接近的可能位置放置在長方形的這一領域的紅色矩形不重疊任何矩形。最接近的位置是指最接近當前鼠標位置的位置，因此通常是與任何給定點最接近的位置。

這個問題的正確算法是什麼？

謝謝！

Answer 1

這是一個優化問題，其約束條件爲線性，目標函數爲（分段）二次或線性，具體取決於您希望如何定義與光標的距離。

假設矩形由 x_i, y_i, w_i, h_i for i=1..n 定義和紅色矩形具有大小w, h，決策變量是用於紅色矩形x, y位置。

非重疊的約束，則：

x >= x_i + w_i或y >= y_i + h_i或x <= x_i - w或y <= y_i - h所有i=1..n

有多種方式，你可以定義你的目標（紅色矩形從光標的距離） ：

• 適當的遊標與紅色矩形最近點之間的Eucledian平方距離（導致分段二次函數nction我認爲）
• 的Eucledian平方距離從紅色矩形的中心（二次）
從紅色矩形的中心（分段線性）
• 曼哈頓距離

那麼你可以使用一個quadratic programming solver或MILP（混合整數線性規劃）求解器來找到答案。如果矩形的數量不是太大（比如不到一百），那麼即使使用免費解算器（如GLPK或LP Solve），它的速度也會很快。

請注意，要正確地爲這些求解器表達約束條件，您可能必須轉換約束條件和目標，例如使用big M method作爲約束，或使用transform將問題轉換爲線性目標。這意味着你將會有額外的二進制變量和一些更多的約束（附加變量和約束的數量將與矩形的數量成正比）。