我需要在2D平面计算两个三角形之间的重叠区域的面积。奇怪的是，我已经写了 code 的triangle-circle问题，并且工作得很好，健壮，但我有一个三角形，三角形问题的麻烦。

I need to compute the area of the region of overlap between two triangles in the 2D plane. Oddly, I have written up code for the triangle-circle problem, and that works quite well and robustly, but I have trouble with the triangle-triangle problem.

我已经第一次检查，看是否完全包含另一个，或者其他包含的第一个，以及获得所有边缘明智的交点。这些交点（最多6个，如在大卫的星），并结合所包含的其他三角形内的三角形的顶点，是交叉区域的顶点。这些点必须形成一个凸多边形

I already first check to see if one entirely contains the other, or if the other contains the first, as well as obtain all the edge-wise intersection points. These intersection points (up to 6, as in the star of David), combined with the triangle vertices that are contained within the other triangle, are the vertices of the intersection region. These points must form a convex polygon.

我所寻求的解决方案就是答案要么这些问题：

The solution I seek is the answer to either of these questions:

在给定一组已知点的所有的趴在点集的凸包，计算凸包的面积。需要注意的是它们是随机的顺序。 给定一组的半平面，确定交叉区域。这相当于描述两个三角形作为三个半平面的交点，和计算的溶液，作为本说明书的直接相交。 Given a set of points known to all lie on the convex hull of the point set, compute the area of the convex hull. Note that they are in random order. Given a set of half-planes, determine the intersecting area. This is equivalent to describing both triangles as the intersection of three half-planes, and computing the solution as the direct intersection of this description.

我已经考虑问题1简单地增加了所有可能的三角形的各个领域，然后通过计数的多重分裂，但是，似乎愚蠢，我不知道这是否是正确的。我觉得有某种扫描线算法的，会做的伎俩。然而，该解决方案还必须相对数值鲁棒

I have considered for question 1 simply adding up all areas of all possible triangles, and then dividing by the multiplicity in counting, but that seems dumb, and I'm not sure if it is correct. I feel like there is some kind of sweep-line algorithm that would do the trick. However, the solution must also be relatively numerically robust.

我根本不知道如何解决问题2，而是一个普遍的答案将是非常有益的，并提供code将使我的一天。这将允许凸多边形，而不必对他们进行三角分解的交叉领域的直接计算。

I simply have no idea how to solve question 2, but a general answer would be very useful, and providing code would make my day. This would allow for direct computation of intersection areas of convex polygons instead of having to perform a triangle decomposition on them.

修改：我知道这篇文章的描述的一般情况下用于求出相交的两个凸多边形的多边形。这似乎相当复杂只是三角形，而且，我并不真的需要得到的多边形本身。因此，也许这个问题是刚才问的懒惰在这一点上。

Edit: I am aware of this article which describes the general case for finding the intersection polygon of two convex polygons. It seems rather involved for just triangles, and furthermore, I don't really need the resulting polygon itself. So maybe this question is just asked in laziness at this point.

推荐答案

问题1：为什么在一个随机的顺序之分？如果是这样，你必须命令他们这样连续的连接点用直线产生了凸多边形。如何对它们进行排序 - 例如，通过运行一个凸包算法（虽然有可能是更简单的方法）。一旦你命令他们，计算区域如这里。

Question 1: why are the points in a random order? If they are, you have to order them so that connecting consecutive points with straight lines yields a convex polygon. How to order them -- for example, by running a convex hull algorithm (though there are probably also simpler methods). Once you have ordered them, compute the area as described here.

-

第二个问题比较简单。半平面由具有方程隐一个* X + b *的Y + C = 0的一行所定义;所有点（X，Y）为其中* X + b *的Y +℃下= 0（注意不等式）是后面半平面。现在，需要至少三个平面使得它们的负半空间的交叉点被关闭（这是必要的，但不是充分条件）。如果交集是封闭的，这将是一个凸多边形

Question 2 is simpler. Half-plane is defined by a single line having an implicit equation a*x+b*y+c=0 ; all points (x,y) for which a*x+b*y+c <= 0 (note the inequality) are "behind" the half-plane. Now, you need at least three planes so that the intersection of their negative half-spaces is closed (this is necessary, but not sufficient condition). If the intersection is closed, it will be a convex polygon.

我建议你保持顶点的链接列表。该算法三行初始化。计算三个点（一般情况下），其中线相交;这些都是你的区域（三角形）的起始顶点。您还必须检查每个顶点是幕后黑手半面由线经过的另外两个顶点定义;这保证了交集实际上是一个封闭的区域。

I suggest that you maintain a linked list of vertices. The algorithm is initialized with THREE lines. Compute the three points (in general case) where the lines intersect; these are the starting vertices of your region (triangle). You must also check that each vertex is "behind" the half-plane defined by the line going through the other two vertices; this guarantees that the intersection actually IS a closed region.

这些三个顶点也定义一个三角形的三个边。当与由一个新的半平面，只需检查该线限定的半平面和每个电流区域的边缘之间的交叉点;一般你会得到两个交点，但是你必须注意退化情况下，该行经过该地区的一个顶点。 （你也可以结束了一组空！）

These three vertices define also the the three edges of a triangle. When you intersect by a new half-plane, simply check for the intersection between the line defining the half-plane and each of the edges of the current region; in general you will get two intersection points, but you must watch out for degenerate cases where the line goes through a vertex of the region. (You can also end up with an empty set!)

新路口顶点定义拆分当前区域在两个区域的线。再次，使用新的半平面的取向，以决定分配哪些两个新区域以新的当前区域，并丢弃哪一个。

The new intersection vertices define a line that splits the current region in TWO regions. Again, use orientation of the new half-plane to decide which of the two new regions to assign to the new "current region", and which one to discard.

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

The points in the list defining the edges of the current region will be correctly ordered so you can apply the formula in the above link to compute its area.

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

If this description is not detailed/understandable, the next-best advice I can give you is that you invest in a book on computational geometry and linear algebra.