Java 圆与矩形的交点面积
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/622287/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Area of intersection between circle and rectangle
提问by user67424
I'm looking for a fast way to determine the area of intersection between a rectangle and a circle (I need to do millions of these calculations).
我正在寻找一种快速方法来确定矩形和圆形之间的交叉区域（我需要进行数百万次这样的计算）。
A specific property is that in all cases the circle and rectangle always have 2 points of intersection.
一个特定的属性是，在所有情况下，圆和矩形总是有 2 个交点。
采纳答案by Daniel LeCheminant
Given 2 points of intersection:
给定 2 个交点：
0 verticesis inside the circle: The area of a circular segment
0个顶点在圆内：圆弧段的面积
XXXXX -------------------
X X X X Circular segment
X X XX XX
+-X-------X--+ XXXXXXXX
| X X |
| XXXXX |
1 vertexis inside the circle: The sum of the areas of a circular segment and a triangle.
1个顶点在圆内：圆线段和三角形的面积之和。
XXXXX XXXXXXXXX
X X Triangle ->X _-X
X X X _- X
X +--X--+ X _- X <- Circular segment
X | X | X- XXX
XXXXX | XXXX
| |
2 verticesare inside the circle: The sum of the area of two triangles and a circular segment
2个顶点在圆内：两个三角形和一个圆线段的面积之和
XXXXX +------------X
X X | _--'/'X
X +--X--- Triangle->| _-- / X
X | X |_-- /XX <- Circular segment
X +-X---- +-------XX
XXXXX Triangle^
3 verticesare inside the circle: The area of the rectangle minus the area of a triangle plus the area of a circular segment
3个顶点在圆内：矩形的面积减去三角形的面积加上圆段的面积
XXXXX
X +--X+ XXX
X | X -------XXX-----+ <- Triangle outside
X | |X Rect ''. XXX |
X +---+X ''. XX|
X X ''. X <- Circular segment inside
X X ^|X
X X | X
XXXXX
To calculate these areas:
要计算这些面积：
Most of the points you'll need to use can be found by finding the intersection of a line and a circle
The areas you need to compute can be found by computing the area of a circular segmentand computing the area of a triangle.
You can determine if a vertex is inside the circle by calculating if its distance from the center is less than the radius.
回答by schnaader
Perhaps you can use the answer to this question, where the area of intersection between a circle and a triangle is asked. Split your rectangle into two triangles and use the algorithms described there.
也许您可以使用这个问题的答案，其中询问圆形和三角形之间的相交面积。将您的矩形分成两个三角形并使用那里描述的算法。
Another way is to draw a line between the two intersection points, this splits your area into a polygon (3 or 4 edges) and a circular segment, for both you should be able to find libraries easier or do the calculations yourself.
另一种方法是在两个交点之间画一条线，这将您的区域分成一个多边形（3 或 4 条边）和一个圆形线段，因为您应该能够更轻松地找到库或自己进行计算。
回答by Gant
The following is how to calculate the overlapping area between circle and rectangle where the center of circle lies outside the rectangle. Other cases can be reduced to this problem.
下面是如何计算圆心在矩形之外的圆和矩形之间的重叠区域。其他情况可以归结为这个问题。
The area can be calculate by integrating the circle equation y = sqrt[a^2 - (x-h)^2] + kwhere a is radius, (h,k) is circle center, to find the area under curve. You may use computer integration where the area is divided into many small rectangle and calculating the sum of them, or just use closed form here.
面积可以通过对圆方程y = sqrt[a^2 - (xh)^2] + k积分来计算，其中 a 是半径，(h,k) 是圆心，求出曲线下的面积。您可以使用计算机集成，将区域划分为许多小矩形并计算它们的总和，或者在这里仅使用封闭形式。
And here is a C# source implementing the concept above. Note that there is a special case where the specified x lies outside the boundaries of the circle. I just use a simple workaround here (which is not producing the correct answers in all cases)
这是实现上述概念的 C# 源代码。请注意，有一种特殊情况，即指定的 x 位于圆的边界之外。我只是在这里使用一个简单的解决方法（在所有情况下都不会产生正确的答案）
public static void RunSnippet()
{
// test code
double a,h,k,x1,x2;
a = 10;
h = 4;
k = 0;
x1 = -100;
x2 = 100;
double r1 = Integrate(x1, a, h, k);
double r2 = Integrate(x2, a, h, k);
Console.WriteLine(r2 - r1);
}
private static double Integrate(double x, double a,double h, double k)
{
double a0 = a*a - (h-x)*(h-x);
if(a0 <= 0.0){
if(k == 0.0)
return Math.PI * a * a / 4.0 * Math.Sign(x);
else
throw new Exception("outside boundaries");
}
double a1 = Math.Sqrt(a*a - (h-x)*(h-x)) * (h-x);
double area = 0.5 * Math.Atan(a1 / ((h-x)*(h-x) - a*a))*a*a - 0.5 * a1 + k * x;
return area;
}
Note:This problem is very similar to one in Google Code Jam 2008 Qualification roundproblem: Fly Swatter. You can click on the score links to download the source code of the solution too.
注意：此问题与Google Code Jam 2008 资格赛问题：Fly Swatter 中的问题非常相似。您也可以单击分数链接下载解决方案的源代码。
回答by user67424
Thanks for the answers,
感谢您的回答，
I forgot to mention that area estimatations were enough. That; s why in the end, after looking at all the options, I went with monte-carlo estimation where I generate random points in the circle and test if they're in the box.
我忘了提到面积估计就足够了。那; 为什么最后，在查看了所有选项后，我采用了蒙特卡罗估计，在该估计中我在圆圈中生成随机点并测试它们是否在框中。
In my case this is likely more performant. (I have a grid placed over the circle and I have to measure the ratio of the circle belonging to each of the grid-cells. )
在我的情况下，这可能更高效。（我在圆圈上放置了一个网格，我必须测量属于每个网格单元的圆圈的比例。）
Thanks
谢谢
回答by Bassam Alugili
Here is another solution for the problem:
这是该问题的另一种解决方案：
public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle)
{
var rectangleCenter = new PointF((rectangle.X + rectangle.Width / 2),
(rectangle.Y + rectangle.Height / 2));
var w = rectangle.Width / 2;
var h = rectangle.Height / 2;
var dx = Math.Abs(circle.X - rectangleCenter.X);
var dy = Math.Abs(circle.Y - rectangleCenter.Y);
if (dx > (radius + w) || dy > (radius + h)) return false;
var circleDistance = new PointF
{
X = Math.Abs(circle.X - rectangle.X - w),
Y = Math.Abs(circle.Y - rectangle.Y - h)
};
if (circleDistance.X <= (w))
{
return true;
}
if (circleDistance.Y <= (h))
{
return true;
}
var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) +
Math.Pow(circleDistance.Y - h, 2);
return (cornerDistanceSq <= (Math.Pow(radius, 2)));
}
回答by agentp
I hope its not bad form to post an answer to such an old question. I looked over the above solutions and worked out an algorithm which is similar to Daniels first answer, but a good bit tighter.
我希望发布对这样一个老问题的答案的形式还不错。我查看了上述解决方案并制定了一个类似于 Daniels first answer 的算法，但更紧密一些。
In short, assume the full area is in the rectangle, subtract off the four segments in the external half planes, then add any the areas in the four external quadrants, discarding trivial cases along the way.
简而言之，假设整个区域都在矩形中，减去外部半平面中的四个部分，然后添加四个外部象限中的任何区域，一路丢弃琐碎的情况。
pseudocde (my actual code is only ~12 lines..)
伪代码（我的实际代码只有 ~12 行..）
find the signed (negative out) normalized distance from the circle center
to each of the infinitely extended rectangle edge lines,
ie.
d_1=(xcenter-xleft)/r
d_2=(ycenter-ybottom)/r
etc
for convenience order 1,2,3,4 around the edge. If the rectangle is not
aligned with the cartesian coordinates this step is more complicated but
the remainder of the algorithm is the same
If ANY d_i <=- 1 return 0
if ALL d_i >= 1 return Pi r^2
this leave only one remaining fully outside case: circle center in
an external quadrant, and distance to corner greater than circle radius:
for each adjacent i,j (ie. i,j=1,2;2,3;3,4;4,1)
if d_i<=0 and d_j <= 0 and d_i^2+d_j^2 > 1 return 0
now begin with full circle area and subtract any areas in the
four external half planes
Area= Pi r^2
for each d_i>-1
a_i=arcsin( d_i ) #save a_i for next step
Area -= r^2/2 (Pi - 2 a_i - sin(2 a_i))
At this point note we have double counted areas in the four external
quadrants, so add back in:
for each adjacent i,j
if d_i < 1 and d_j < 1 and d_i^2+d_j^2 < 1
Area += r^2/4 (Pi- 2 a_i - 2 a_j -sin(2 a_i) -sin(2 a_j) + 4 sin(a_i) sin(a_j))
return Area
Incidentally, that last formula for the area of a circle contained in a plane quadrant is readily derived as the sum of a circular segment, two right triangles and a rectangle.
顺便说一下，平面象限中包含的圆面积的最后一个公式很容易导出为一个圆弧段、两个直角三角形和一个矩形的总和。
Enjoy.
享受。
回答by the swine
I realize this was answered a while ago but I'm solving the same problem and I couldn't find an out-of-the box workable solution I could use. Note that my boxes are axis aligned, this is not quite specified by the OP. The solution below is completely general, and will work for any number of intersections (not only two). Note that if your boxes are not axis-aligned (but still boxes with right angles, rather than general quads), you can take advantage of the circles being round, rotate the coordinates of everything so that the box ends up axis-aligned and thenuse this code.
我意识到这是不久前回答的，但我正在解决同样的问题，我找不到可以使用的开箱即用的可行解决方案。请注意，我的盒子是轴对齐的，这不是由 OP 完全指定的。下面的解决方案是完全通用的，适用于任意数量的交叉点（不仅仅是两个）。请注意，如果您的盒子不是轴对齐的（但仍然是直角的盒子，而不是一般的四边形），您可以利用圆形的优势，旋转所有东西的坐标，使盒子最终与轴对齐，然后使用此代码。
I want to use integration - that seems like a good idea. Let's start with writing an obvious formula for plotting a circle:
我想使用集成 - 这似乎是个好主意。让我们从写一个明显的绘制圆的公式开始：
x = center.x + cos(theta) * radius
y = center.y + sin(theta) * radius
^
|
|**### **
| #* # * * x
|# * # * # y
|# * # *
+-----------------------> theta
* # * #
* # * #
* #* #
***###
This is nice, but I'm unable to integrate the area of that circle over xor y; those are different quantities. I can only integrate over the angle theta, yielding areas of pizza slices. Not what I want. Let's try to change the arguments:
这很好，但我无法将该圆的面积整合到x或 上y；这些是不同的数量。我只能在角度上积分theta，产生比萨片的区域。不是我想要的。让我们尝试更改参数：
(x - center.x) / radius = cos(theta) // the 1st equation
theta = acos((x - center.x) / radius) // value of theta from the 1st equation
y = center.y + sin(acos((x - center.x) / radius)) * radius // substitute to the 2nd equation
That's more like it. Now given the range of x, I can integrate over y, to get an area of the upper half of a circle. This only holds for xin [center.x - radius, center.x + radius](other values will cause imaginary outputs) but we know that the area outside that range is zero, so that is handled easily. Let's assume unit circle for simplicity, we can always plug the center and radius back later on:
这还差不多。现在给定 的范围x，我可以对 进行积分y，得到圆上半部分的面积。这仅适用于xin [center.x - radius, center.x + radius]（其他值将导致虚输出），但我们知道该范围之外的区域为零，因此很容易处理。为简单起见，让我们假设单位圆，我们可以稍后再插入中心和半径：
y = sin(acos(x)) // x in [-1, 1]
y = sqrt(1 - x * x) // the same thing, arguably faster to compute http://www.wolframalpha.com/input/?i=sin%28acos%28x%29%29+
^ y
|
***|*** <- 1
**** | ****
** | **
* | *
* | *
----|----------+----------|-----> x
-1 1
This function indeed has an integral of pi/2, since it is an upper half of a unit circle (the area of half a circle is pi * r^2 / 2and we already said unit, which means r = 1). Now we can calculate area of intersection of a half-circle and an infinitely tall box, standing on the x axis (the center of the circle also lies on the the x axis) by integrating over y:
这个函数确实有一个积分pi/2，因为它是一个单位圆的上半部分（半圆的面积是pi * r^2 / 2我们已经说过的单位，这意味着r = 1）。现在我们可以通过积分计算一个半圆和一个无限高的盒子的交集面积，站在 x 轴上（圆心也位于 x 轴上）y：
f(x): integral(sqrt(1 - x * x) * dx) = (sqrt(1 - x * x) * x + asin(x)) / 2 + C // http://www.wolframalpha.com/input/?i=sqrt%281+-+x*x%29
area(x0, x1) = f(max(-1, min(1, x1))) - f(max(-1, min(1, x0))) // the integral is not defined outside [-1, 1] but we want it to be zero out there
~ ~
| ^ |
| | |
| ***|*** <- 1
****###|##|****
**|######|##| **
* |######|##| *
* |######|##| *
----|---|------+--|-------|-----> x
-1 x0 x1 1
This may not be very useful, as infinitely tall boxes are not what we want. We need to add one more parameter in order to be able to free the bottom edge of the infinitely tall box:
这可能不是很有用，因为无限高的盒子不是我们想要的。我们需要再添加一个参数，以便能够释放无限高的盒子的底部边缘：
g(x, h): integral((sqrt(1 - x * x) - h) * dx) = (sqrt(1 - x * x) * x + asin(x) - 2 * h * x) / 2 + C // http://www.wolframalpha.com/input/?i=sqrt%281+-+x*x%29+-+h
area(x0, x1, h) = g(min(section(h), max(-section(h), x1))) - g(min(section(h), max(-section(h), x0)))
~ ~
| ^ |
| | |
| ***|*** <- 1
****###|##|****
**|######|##| **
* +------+--+ * <- h
* | *
----|---|------+--|-------|-----> x
-1 x0 x1 1
Where his the (positive) distance of the bottom edge of our infinite box from the x axis. The sectionfunction calculates the (positive) position of intersection of the unit circle with the horizontal line given by y = hand we could define it by solving:
h无限长方体底部边缘到 x 轴的（正）距离在哪里。该section函数计算单位圆与由 给出的水平线的（正）交点位置，y = h我们可以通过求解来定义它：
sqrt(1 - x * x) = h // http://www.wolframalpha.com/input/?i=sqrt%281+-+x+*+x%29+%3D+h
section(h): (h < 1)? sqrt(1 - h * h) : 0 // if h is 1 or above, then the section is an empty interval and we want the area integral to be zero
^ y
|
***|*** <- 1
**** | ****
** | **
-----*---------+---------*------- y = h
* | *
----||---------+---------||-----> x
-1| |1
-section(h) section(h)
Now we can get the things going. So how to calculate the area of intersection of a finite box intersecting a unit circle above the x axis:
现在我们可以开始工作了。那么如何计算与x轴上方的单位圆相交的有限框的相交面积：
area(x0, x1, y0, y1) = area(x0, x1, y0) - area(x0, x1, y1) // where x0 <= x1 and y0 <= y1
~ ~ ~ ~
| ^ | | ^ |
| | | | | |
| ***|*** | ***|***
****###|##|**** ****---+--+**** <- y1
**|######|##| ** ** | **
* +------+--+ * <- y0 * | *
* | * * | *
----|---|------+--|-------|-----> x ----|---|------+--|-------|-----> x
x0 x1 x0 x1
^
|
***|***
****---+--+**** <- y1
**|######|##| **
* +------+--+ * <- y0
* | *
----|---|------+--|-------|-----> x
x0 x1
That's nice. So how about a box which is not above the x axis? I'd say not all the boxes are. Three simple cases arise:
那很好。那么一个不在 x 轴上方的盒子呢？我会说不是所有的盒子都是。出现三种简单的情况：
- the box is above the x axis (use the above equation)
- the box is below the x axis (flip the sign of y coordinates and use the above equation)
- the box is intersecting the x axis (split the box to upper and lower half, calculate the area of both using the above and sum them)
- 框在 x 轴上方（使用上面的等式）
- 该框位于 x 轴下方（翻转 y 坐标的符号并使用上述等式）
- 盒子与 x 轴相交（将盒子分成上半部分和下半部分，使用上面的计算两者的面积并将它们相加）
Easy enough? Let's write some code:
够容易吗？让我们写一些代码：
float section(float h, float r = 1) // returns the positive root of intersection of line y = h with circle centered at the origin and radius r
{
assert(r >= 0); // assume r is positive, leads to some simplifications in the formula below (can factor out r from the square root)
return (h < r)? sqrt(r * r - h * h) : 0; // http://www.wolframalpha.com/input/?i=r+*+sin%28acos%28x+%2F+r%29%29+%3D+h
}
float g(float x, float h, float r = 1) // indefinite integral of circle segment
{
return .5f * (sqrt(1 - x * x / (r * r)) * x * r + r * r * asin(x / r) - 2 * h * x); // http://www.wolframalpha.com/input/?i=r+*+sin%28acos%28x+%2F+r%29%29+-+h
}
float area(float x0, float x1, float h, float r) // area of intersection of an infinitely tall box with left edge at x0, right edge at x1, bottom edge at h and top edge at infinity, with circle centered at the origin with radius r
{
if(x0 > x1)
std::swap(x0, x1); // this must be sorted otherwise we get negative area
float s = section(h, r);
return g(max(-s, min(s, x1)), h, r) - g(max(-s, min(s, x0)), h, r); // integrate the area
}
float area(float x0, float x1, float y0, float y1, float r) // area of the intersection of a finite box with a circle centered at the origin with radius r
{
if(y0 > y1)
std::swap(y0, y1); // this will simplify the reasoning
if(y0 < 0) {
if(y1 < 0)
return area(x0, x1, -y0, -y1, r); // the box is completely under, just flip it above and try again
else
return area(x0, x1, 0, -y0, r) + area(x0, x1, 0, y1, r); // the box is both above and below, divide it to two boxes and go again
} else {
assert(y1 >= 0); // y0 >= 0, which means that y1 >= 0 also (y1 >= y0) because of the swap at the beginning
return area(x0, x1, y0, r) - area(x0, x1, y1, r); // area of the lower box minus area of the higher box
}
}
float area(float x0, float x1, float y0, float y1, float cx, float cy, float r) // area of the intersection of a general box with a general circle
{
x0 -= cx; x1 -= cx;
y0 -= cy; y1 -= cy;
// get rid of the circle center
return area(x0, x1, y0, y1, r);
}
And some basic unit tests:
以及一些基本的单元测试：
printf("%f\n", area(-10, 10, -10, 10, 0, 0, 1)); // unit circle completely inside a huge box, area of intersection is pi
printf("%f\n", area(-10, 0, -10, 10, 0, 0, 1)); // half of unit circle inside a large box, area of intersection is pi/2
printf("%f\n", area(0, 10, -10, 10, 0, 0, 1)); // half of unit circle inside a large box, area of intersection is pi/2
printf("%f\n", area(-10, 10, -10, 0, 0, 0, 1)); // half of unit circle inside a large box, area of intersection is pi/2
printf("%f\n", area(-10, 10, 0, 10, 0, 0, 1)); // half of unit circle inside a large box, area of intersection is pi/2
printf("%f\n", area(0, 1, 0, 1, 0, 0, 1)); // unit box covering one quadrant of the circle, area of intersection is pi/4
printf("%f\n", area(0, -1, 0, 1, 0, 0, 1)); // unit box covering one quadrant of the circle, area of intersection is pi/4
printf("%f\n", area(0, -1, 0, -1, 0, 0, 1)); // unit box covering one quadrant of the circle, area of intersection is pi/4
printf("%f\n", area(0, 1, 0, -1, 0, 0, 1)); // unit box covering one quadrant of the circle, area of intersection is pi/4
printf("%f\n", area(-.5f, .5f, -.5f, .5f, 0, 0, 10)); // unit box completely inside a huge circle, area of intersection is 1
printf("%f\n", area(-20, -10, -10, 10, 0, 0, 1)); // huge box completely outside a circle (left), area of intersection is 0
printf("%f\n", area(10, 20, -10, 10, 0, 0, 1)); // huge box completely outside a circle (right), area of intersection is 0
printf("%f\n", area(-10, 10, -20, -10, 0, 0, 1)); // huge box completely outside a circle (below), area of intersection is 0
printf("%f\n", area(-10, 10, 10, 20, 0, 0, 1)); // huge box completely outside a circle (above), area of intersection is 0
The output of this is:
这个的输出是：
3.141593
1.570796
1.570796
1.570796
1.570796
0.785398
0.785398
0.785398
0.785398
1.000000
-0.000000
0.000000
0.000000
0.000000
Which seems correct to me. You may want to inline the functions if you don't trust your compiler to do it for you.
这对我来说似乎是正确的。如果您不相信您的编译器会为您内联这些函数，您可能想要内联这些函数。
This uses 6 sqrt, 4 asin, 8 div, 16 mul and 17 adds for boxes that do not intersect the x axis and a double of that (and 1 more add) for boxes that do. Note that the divisions are by radius and could be reduced to two divisions and a bunch of multiplications. If the box in question intersected the x axis but did not intersect the y axis, you could rotate everything by pi/2and do the calculation in the original cost.
这对不与 x 轴相交的框使用 6 sqrt、4 asin、8 div、16 mul 和 17 个添加，对于与 x 轴相交的框使用两倍（以及 1 个添加）。请注意，除法是按半径划分的，可以减少为两个除法和一堆乘法。如果有问题的盒子与 x 轴相交但没有与 y 轴相交，您可以旋转所有内容pi/2并在原始成本中进行计算。
I'm using it as a reference to debug subpixel-precise antialiased circle rasterizer. It is slow as hell :), I need to calculate the area of intersection of each pixel in the bounding box of the circle with the circle to get alpha. You can sort of see that it works and no numerical artifacts seem to appear. The figure below is a plot of a bunch of circles with the radius increasing from 0.3 px to about 6 px, laid out in a spiral.
我将其用作调试亚像素精确抗锯齿圆形光栅化器的参考。它很慢:)，我需要计算圆的边界框中每个像素与圆的交集面积以获得 alpha。您可以看到它的工作原理，并且似乎没有出现数字伪影。下图是一堆半径从 0.3 px 增加到大约 6 px 的圆的图，它们呈螺旋状排列。
