两个三角形或一组半平面的交集面积或凸点集的面积
我需要计算 2D 平面中两个三角形之间重叠区域的面积。奇怪的是，我已经为 代码 编写了 < href="https://stackoverflow.com/questions/540014/compute-the-area-of-intersection- Between-a-circle-and-a-triangle">三角圆问题，并且工作得很好而且很稳健，但是我在解决三角形-三角形问题时遇到了麻烦。
我已经首先检查一个是否完全包含另一个，或者另一个是否包含第一个，以及获取所有边缘交叉点。这些交点（最多 6 个，如大卫之星）与另一个三角形中包含的三角形顶点相结合，就是交集区域的顶点。这些点必须形成凸多边形。
我寻求的解决方案是以下任一问题的答案：
- 给定一组已知的点全部都位于点集的凸包上，计算凸包的面积。请注意，它们的顺序是随机的。
- 给定一组半平面，确定相交面积。这相当于将两个三角形描述为三个半平面的交集，并将解计算为该描述的直接交集。
对于问题 1，我考虑过简单地将所有可能三角形的所有面积相加，然后除以计数的重数，但这看起来很愚蠢，而且我不确定它是否正确。我觉得有某种扫线算法可以解决这个问题。然而，该解决方案还必须在数值上相对稳健。
我根本不知道如何解决问题 2，但一般性的答案会非常有用，并且提供代码会让我很高兴。这将允许直接计算凸多边形的交叉面积，而不必对它们执行三角形分解。
编辑：我知道这篇文章 描述了查找两个凸多边形的相交多边形的一般情况。它似乎只涉及三角形，而且，我实际上并不需要生成的多边形本身。所以也许这个问题只是在此时出于懒惰而提出的。
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.
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.
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
问题1：为什么点的顺序是随机的？如果是，则必须对它们进行排序，以便用直线连接连续的点产生凸多边形。如何对它们进行排序——例如，通过运行凸包算法（尽管可能还有更简单的方法）。订购后，请按照此处所述计算面积。
——
问题2比较简单。半平面由具有隐式方程
a*x+b*y+c=0的单线定义；a*x+b*y+c <= 0（注意不等式）的所有点 (x, y) 都位于半平面“后面”。现在，您至少需要三个平面，以便它们的负半空间的交集是封闭的（这是必要的，但不是充分条件）。如果交点是闭合的，它将是凸多边形。我建议您维护一个顶点链接列表。该算法用三行初始化。计算直线相交的三个点（一般情况）；这些是您所在区域（三角形）的起始顶点。您还必须检查每个顶点是否位于由穿过其他两个顶点的线定义的半平面“后面”；这保证了交叉点实际上是一个封闭区域。
这三个顶点还定义了三角形的三条边。当与新的半平面相交时，只需检查定义半平面的线与当前区域的每条边之间的交点即可；一般来说，您会得到两个交点，但您必须注意直线穿过区域顶点的退化情况。 （您也可以得到一个空集！）
新的交点顶点定义一条线，将当前区域分成两个区域。再次，使用新半平面的方向来决定将两个新区域中的哪一个分配给新的“当前区域”，以及丢弃哪一个。
列表中定义当前区域边缘的点将被正确排序，因此您可以应用上面链接中的公式来计算其面积。
如果这个描述不详细/无法理解，我能给你的下一个最好的建议是你投资一本关于计算几何和线性代数的书。
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.
--
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 whicha*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.