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

我需要计算 2D 平面中两个三角形之间重叠区域的面积。奇怪的是我已经写了code http://github.com/victorliu/Templated-Numerics/blob/master/AnalyticGeometry/TIntersection2.hpp为了三角圆问题 https://stackoverflow.com/questions/540014/compute-the-area-of-intersection-between-a-circle-and-a-triangle，并且效果非常好且稳健，但我在三角三角问题上遇到了麻烦。

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

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

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

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

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

Edit: 我知道本文 http://www.iro.umontreal.ca/~plante/compGeom/index.html它描述了查找两个凸多边形的相交多边形的一般情况。它似乎只涉及三角形，而且，我实际上并不需要生成的多边形本身。所以也许这个问题只是在此时出于懒惰而提出的。

问题1：为什么点的顺序是随机的？如果是，则必须对它们进行排序，以便用直线连接连续的点产生凸多边形。如何对它们进行排序——例如，通过运行凸包算法（尽管可能还有更简单的方法）。订购后，按照描述计算面积here http://www.mathwords.com/a/area_convex_polygon.htm.

--

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

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

这三个顶点还定义了三角形的三条边。当与新的半平面相交时，只需检查定义半平面的线与当前区域的每条边之间的交点即可；一般来说，您会得到两个交点，但您必须注意直线穿过区域顶点的退化情况。 （您也可能会得到一个空集！）

新的相交顶点定义一条线，将当前区域分为两个区域。再次，使用新半平面的方向来决定将两个新区域中的哪一个分配给新的“当前区域”，以及丢弃哪一个。

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

如果这个描述不详细/无法理解，我能给你的下一个最好的建议是你投资一本关于计算几何和线性代数的书。