非轴对齐的矩形交叉点

Question

我试图找到一个算法，它将计算两个矩形之间的交集，它们不一定是轴对齐的，并返回结果交集。

This question描述查找是否存在交集。如果它存在，我想要得到十字路口的最终形状。

我的算法应用程序将使用一个轴对齐的矩形和一个不一定轴对齐的矩形，但是一般算法会更好。

谢谢！

Answer 1

One algorithm for finding the intersection任何两个凸多边形涉及首先找到所有顶点周围的凸包。凸包沿着多边形的轮廓最外层;你正在寻找的形状遵循无论哪个多边形的轮廓最内层，所以请按照凸包不遵循的任何一个。相同算法的Here is a prettier picture。

This extremely brief wiki page提到了另外两种算法。你有一个把多边形分解成梯形。另一种是在锁定步骤中逆时针在两个多边形周围走动的非常聪明的方式。我认为我最喜欢这一点，但正如wiki所说，这很难形容。

Answer 2

Here's一个多边形 - 多边形相交算法，其中包含C和Java中的源，它返回交集的面积。