2011-02-23 462 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:如果您想包含遏制,则可以使用交叉线内部多边形。它增加了计算时间,但不是复杂性。 –