algorithm - 两个三角形的交集面积，或一组半平面，或凸点集的面积

Question

我需要计算二维平面中两个三角形重叠区域的面积。奇怪的是，我写了code对于 triangle-circle problem ，而且效果很好，很稳健，但我在三角形-三角形问题上遇到了麻烦。

我已经首先检查一个是否完全包含另一个，或者另一个是否包含第一个，以及获取所有的边缘交叉点。这些交点(最多 6 个，如大卫之星)与包含在另一个三角形内的三角形顶点相结合，就是相交区域的顶点。这些点必须形成一个凸多边形。

我寻求的解决方案是以下任一问题的答案:

1. 给定一组所有已知的点位于点集的凸包上，计算凸包的面积。请注意，它们的顺序是随机的。
2. 给定一组半平面，确定相交面积。这相当于将两个三角形描述为三个半平面的交集，并将解计算为该描述的直接交集。

对于问题 1，我考虑过简单地将所有可能的三角形的所有面积相加，然后除以重数进行计数，但这似乎很愚蠢，我不确定它是否正确。我觉得有某种扫描线算法可以解决问题。但是，解决方案还必须在数值上相对稳健。

我根本不知道如何解决问题 2，但一般答案会非常有用，提供代码会让我开心。这将允许直接计算凸多边形的交叉区域，而不必对其执行三角形分解。

编辑:我知道this article它描述了寻找两个凸多边形的交点多边形的一般情况。它似乎只涉及三角形，而且，我真的不需要生成的多边形本身。所以也许这个问题只是在此时懒惰地问。

Answer 1

问题一:为什么点的顺序是随机的？如果是，则必须对它们进行排序，以便用直线连接连续的点会产生一个凸多边形。如何对它们进行排序——例如，通过运行凸包算法(尽管可能还有更简单的方法)。一旦您订购了它们，请按照描述计算面积 here .

--

问题2比较简单。半平面由具有隐式方程 a*x+b*y+c=0 的单条线定义; a*x+b*y+c <= 0 的所有点 (x, y) (注意不等式)在半平面“后面”。现在，您至少需要三个平面，以便它们的负半空间的交点闭合(这是必要条件，但不是充分条件)。如果相交是封闭的，它将是一个凸多边形。

我建议你维护一个顶点链表。该算法用三行初始化。计算线相交的三个点(一般情况下)；这些是您所在区域(三角形)的起始顶点。您还必须检查每个顶点是否位于通过其他两个顶点的线所定义的半平面“后面”；这保证了交叉点实际上是一个封闭区域。

这三个顶点也定义了三角形的三个边。当你与一个新的半平面相交时，只需检查定义半平面的线与当前区域的每条边之间的交点；通常你会得到两个交点，但你必须注意直线穿过区域顶点的退化情况。 (你也可以得到一个空集!)

新的交叉点定义了一条线，将当前区域分成两个区域。同样，使用新半平面的方向来决定将两个新区域中的哪一个分配给新的“当前区域”，以及丢弃哪一个。

定义当前区域边缘的列表中的点将正确排序，因此您可以应用上述链接中的公式来计算其面积。

如果这个描述不够详细/难以理解，我可以给你的次佳建议是你投资一本关于计算几何和线性代数的书。