2011-02-23 461 views
7

我正在用Python編寫一個程序。我有一系列的形狀(多邊形,定義爲一系列座標對),我需要告訴它們是否重疊了一個特定的矩形。使用Python,如何判斷矩形和形狀是否重疊?

是否有一個簡單的算法來處理這個問題?或者,更好的是,是否有一個純Python庫可以爲我處理這些計算?

+2

你的任意形狀是真正的任意形狀,還是多邊形?描述這些多邊形頂點的「座標對序列」是什麼?如果不是,那是什麼? –

+0

澄清問題 –

回答

3

假設你的「任意形狀」確實是多邊形(假設它們被描述爲座標對),確定它們是否重疊(以任何語言)是相對平凡的計算。你只需要計算多邊形A的任何一邊是否與多邊形B的任何一邊相交。

如果你需要一個例子,在the Drexel Math Forum有一個相當全面的演練。

有許多的Python模塊,可以幫助您在這個追求,如SympyNumpyPyGame等,但所有的人都比較重,如果這是你需要做的唯一的幾何計算。

+0

在多邊形A完全包含多邊形B的情況下,「邊相交」不起作用。 –

+1

@Chris檢查交點是否在您要檢查的兩邊的端點之間(「xA1 < = xInt <= xA2和xB1 <= xInt <= xB2和yA1 <= yInt <= yA2和yB1 <= yInt <= yB2') – user470379

+0

@Chris:如果您想包含遏制,則可以使用交叉線內部多邊形。它增加了計算時間,但不是複雜性。 –