计算一个圆和一个三角形之间的交叉区域？ [英] Compute the area of intersection between a circle and a triangle?

问题描述

一个人如何计算一个三角形（指定为三（X，Y）对）之间的交叉区和一个圆（X，Y，R）？我做了一些搜索无果。这是工作，而不是学校。 ：）

它看起来在C＃中是这样的：

 结构{的PointF VERT [3]; } 三角形;
结构{的PointF中心;漂浮半径; } 圈;

//返回交集，例如面积：
//如果圆圈中包含的三角形，三角形返回区
//如果三角形中包含了一圈，回圈的面积
//如果部分路口，可以认识到这一点
//如果不相交，则返回0
双AreaOfIntersection（三角形T，圆C）
{
 ...
}
 

解决方案

如果你想要一个确切的解决方案（或至少是准确的，你可以使用浮点运算得到），那么这将涉及很多跑腿的，因为有这么多的情况下考虑。

余数九个不同的情况下（分类如下图由圆圈内的三角形的顶点的数目，和相交或包含在圆的三角形的边的数量）：

（不过，这种几何案例列举的是众所周知的是棘手的，它不会让我感到吃惊，如果我错过了一个或两个！）

所以，方法是：

1. 确定为三角形的每个顶点，如果它的圆圈内。我会假设你知道该怎么做。

2. 确定为三角形的每个边缘，如果相交的圆圈。 （我写了一种方法这里，或看到任何计算几何本书。）你需要计算交叉点或点（如果有的话），在步骤4中使用。

3. 确定其中的九个情况下，你有。

4. 计算的相交的区域。例1，2，和图9是容易的。在其余六情况下，我已经画虚线显示如何交集区域分割成三角形和圆弧段基于三角形的原始顶点的，并在交叉点在步骤2中计算

此算法将是相当微妙的，而且容易影响只有一个的情况下错误，所以请确保您有测试用例覆盖所有九例（我建议置换测试三角形的顶点太）。要特别注意的情况，即三角形的顶点之一是圆的边缘。

如果你并不需要一个确切的解决方案，那么光栅化图形和计算的像素在路口（所建议的几个其他的受访者）似乎是一个更容易的方法来code，并相应地不容易错误。

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. :)

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!)

So the approach is:

1. Determine for each vertex of the triangle if it's inside the circle. I'm going to assume you know how to do that.

2. 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.

3. Determine which of the nine cases you have.

4. 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.

这篇关于计算一个圆和一个三角形之间的交叉区域？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！