问题描述
如何计算三角形(指定为三个 (X,Y) 对)和圆 (X,Y,R) 之间的相交面积?我已经做了一些搜索无济于事.这是为了工作，而不是学校.:)
How does one compute the area of intersection between a triangle (specified as three (X,Y) pairs) and a circle (X,Y,R)? I've done some searching to no avail. This is for work, not school. :)
它在 C# 中看起来像这样:
It would look something like this in C#:
struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;
// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
...
}
推荐答案
如果你想要一个精确的解决方案(或者至少尽可能精确地使用浮点运算)，那么这将涉及大量的跑腿工作，因为要考虑的情况太多了.
If you want an exact solution (or at least as exact as you can get using floating-point arithmetic) then this is going to involve a lot of legwork, because there are so many cases to consider.
我统计了九种不同的情况(下图中按三角形在圆内的顶点数，以及与圆相交或包含在圆内的三角形边数分类):
I count nine different cases (categorized in the figure below by the number of vertices of the triangle inside the circle, and the number of edges of the triangle that intersect or are contained in the circle):
(不过，这种几何案例的枚举是众所周知的棘手，如果我漏掉一两个我也不会感到惊讶！)
(However, this kind of enumeration of geometric cases is well known to be tricky, and it wouldn't surprise me at all if I missed one or two!)
所以方法是:
确定三角形的每个顶点是否在圆内.我假设您知道该怎么做.
Determine for each vertex of the triangle if it's inside the circle. I'm going to assume you know how to do that.
确定三角形的每条边是否与圆相交.(我在此处写了一个方法，或者查看任何计算几何书籍.) 您需要计算在步骤 4 中使用的一个或多个交点(如果有).
Determine for each edge of the triangle if it intersects the circle. (I wrote up one method here, or see any computational geometry book.) You'll need to compute the point or points of intersection (if any) for use in step 4.
确定您有九种情况中的哪一种.
Determine which of the nine cases you have.
计算交叉点的面积.情况 1、2 和 9 很容易.在剩下的六种情况下，我画了虚线来展示如何将交叉区域划分为三角形和圆形线段 基于三角形的原始顶点，以及您在步骤 2 中计算的交点.
Compute the area of the intersection. Cases 1, 2, and 9 are easy. In the remaining six cases I've drawn dashed lines to show how to partition the area of intersection into triangles and circular segments based on the original vertices of the triangle, and on the points of intersection you computed in step 2.
此算法将相当精细，并且容易出现仅影响其中一种情况的错误，因此请确保您的测试用例涵盖所有九种情况(我建议也排列测试三角形的顶点).特别注意三角形的顶点之一在圆的边缘的情况.
This algorithm is going to be rather delicate and prone to errors that affect only one of the cases, so make sure you have test cases that cover all nine cases (and I suggest permuting the vertices of the test triangles too). Pay particular attention to cases in which one of the vertices of the triangle is on the edge of the circle.
如果您不需要精确的解决方案，那么对图形进行光栅化并计算交点中的像素数(如其他几个受访者所建议的)似乎是一种更简单的编码方法，并且相应地不易出错.
If you don't need an exact solution, then rasterizing the figures and counting the pixels in the intersection (as suggested by a couple of other respondents) seems like a much easier approach to code, and correspondingly less prone to errors.
这篇关于计算圆形和三角形之间的相交面积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！