원과 사각형 사이의 교차 영역
https://stackoverflow.com/questions/622287
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
사각형과 원 사이의 교차 영역을 결정하는 빠른 방법을 찾고 있습니다 (수백만 개의 계산을 수행해야합니다).
특정 속성은 모든 경우에 원과 사각형이 항상 2 점의 교차점을 가지고 있다는 것입니다.
해결책
교차로 2 점 주어진 :
0 정점 원 안에 있습니다 : a의 면적 원형 세그먼트
XXXXX -------------------
X X X X Circular segment
X X XX XX
+-X-------X--+ XXXXXXXX
| X X |
| XXXXX |
1 vertex 원 안에 있습니다 : 원형 세그먼트의 영역과 삼각형의 합.
XXXXX XXXXXXXXX
X X Triangle ->X _-X
X X X _- X
X +--X--+ X _- X <- Circular segment
X | X | X- XXX
XXXXX | XXXX
| |
2 개의 정점 원 안에 있습니다 : 두 삼각형의 면적과 원형 세그먼트의 합
XXXXX +------------X
X X | _--'/'X
X +--X--- Triangle->| _-- / X
X | X |_-- /XX <- Circular segment
X +-X---- +-------XX
XXXXX Triangle^
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
이 영역을 계산하려면 :
사용해야 할 대부분의 포인트는 다음을 찾아서 찾을 수 있습니다. 선과 원의 교차점
계산 해야하는 영역은 원형 세그먼트의 영역을 계산합니다 그리고 삼각형의 영역을 계산합니다.
중심으로부터의 거리는 반경보다 적은지 계산하여 정점이 원 안에 있는지 확인할 수 있습니다.
다른 팁
나는 이것이 얼마 전에 대답했다는 것을 알고 있지만 같은 문제를 해결하고 있으며 사용할 수있는 실행 가능한 솔루션을 찾을 수 없었습니다. 내 상자가 있습니다 축이 정렬되었습니다, 이것은 OP에 의해 명시되지 않습니다. 아래 솔루션은 완전히 일반적이며 여러 교차로 (두 개뿐만 아니라)에서 작동합니다. 상자가 축 정렬되지 않은 경우 (그러나 여전히 일반보다는 직각이있는 상자 쿼드), 당신은 원이 둥글고, 모든 것의 좌표를 회전시켜 상자가 축으로 정렬되고, 그 다음에 이 코드를 사용하십시오.
통합을 사용하고 싶습니다. 좋은 생각처럼 보입니다. 원을 플로팅하기위한 명백한 공식을 작성하는 것으로 시작합시다.
x = center.x + cos(theta) * radius
y = center.y + sin(theta) * radius
^
|
|**### **
| #* # * * x
|# * # * # y
|# * # *
+-----------------------> theta
* # * #
* # * #
* #* #
***###
이것은 좋지만 그 원의 영역을 통합 할 수는 없습니다. 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
그것은 더 비슷합니다. 이제 범위가 주어졌습니다 x, 나는 통합 할 수 있습니다 y, 원의 상반부 영역을 얻기 위해. 이것은 단지 보유합니다 x 안에 [center.x - radius, center.x + radius] (다른 값은 상상의 출력을 유발할 것입니다) 그러나 우리는 그 범위 외부의 영역이 0이므로 쉽게 처리됩니다. 단순성을 위해 단위 원을 가정 해 봅시다. 우리는 항상 중심과 반경을 나중에 다시 연결할 수 있습니다.
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
이 기능은 실제로 필수적인 것입니다 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
무한히 큰 상자가 우리가 원하는 것이 아니기 때문에 이것은 그다지 유용하지 않을 수 있습니다. 무한한 키가 큰 상자의 하단 가장자리를 제거하려면 하나 더 매개 변수를 추가해야합니다.
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
어디에 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)
이제 우리는 일을 갈 수 있습니다. 따라서 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
멋지다. 그렇다면 X 축 위에없는 상자는 어떻습니까? 나는 모든 상자가 있다고 말하는 것은 아닙니다. 세 가지 간단한 사례가 발생합니다.
- 상자는 X 축 위에 있습니다 (위의 방정식 사용)
- 상자는 X 축 아래에 있습니다 (Y 좌표의 부호를 뒤집고 위의 방정식을 사용하십시오).
- 상자는 X 축을 교차합니다 (상자를 상단 및 하반부로 분할하고 위의 영역을 계산하고 합계)
충분히 쉽습니까? 코드를 작성합시다.
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);
}
그리고 일부 기본 단위 테스트 :
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
이것의 출력은 다음과 같습니다.
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
나에게 옳은 것 같습니다. 컴파일러가 자신을 위해 수행 할 수있는 컴파일러를 신뢰하지 않으면 함수를 인화하고 싶을 수도 있습니다.
이것은 6 개의 SQRT, 4 ASIN, 8 DIV, 16 MUL 및 17 ADDS를 X 축을 교차하지 않는 상자와 상자의 두 배 (및 1 개 추가)를 사용합니다. 분열은 반경에 의한 것이며 두 개의 부서와 많은 곱셈으로 축소 될 수 있습니다. 문제의 상자가 X 축을 교차했지만 y 축을 교차하지 않으면 모든 것을 회전시킬 수 있습니다. pi/2 원래 비용으로 계산하십시오.
나는 그것을 서브 픽셀-프롤링 antialiased circle Rasterizer를 디버그하기위한 참조로 사용하고 있습니다. 지옥처럼 느립니다 :), 나는 알파를 얻기 위해 원과 원의 경계 상자에서 각 픽셀의 교차 영역을 계산해야합니다. 당신은 그것이 작동하고 수치 인공물이 나타나지 않는다는 것을 알 수 있습니다. 아래 그림은 반경이 0.3 px에서 약 6 px로 증가하여 나선형으로 배치 된 많은 원의 플롯입니다.
나는 그런 오래된 질문에 대한 답을 게시하는 것이 나쁜 형태가 아니기를 바랍니다. 나는 위의 솔루션을 살펴보고 Daniels의 첫 번째 답변과 비슷한 알고리즘을 만들었지 만 약간 더 단단합니다.
요컨대, 전체 영역이 직사각형에 있다고 가정하고 외부 반 평면의 4 개의 세그먼트를 빼낸 다음 4 개의 외부 사분면에 영역을 추가하여 사소한 경우를 버립니다.
pseudocde (나의 실제 코드는 ~ 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
또한, 평면 사분면에 포함 된 원의 영역에 대한 마지막 공식은 원형 세그먼트, 2 개의 오른쪽 삼각형 및 사각형의 합으로 쉽게 도출됩니다.
즐기다.
다음은 원의 중심이 사각형 외부에있는 원과 사각형 사이의 겹치는 영역을 계산하는 방법입니다. 다른 경우 가이 문제로 줄일 수 있습니다.
영역은 원 방정식을 통합하여 계산할 수 있습니다. y = sqrt [a^2- (xh)^2] + k 여기서 A는 반경, (h, k)는 곡선 아래 영역을 찾기 위해 원 중심입니다. 영역이 많은 작은 사각형으로 나누어지고 합계를 계산하는 경우 컴퓨터 통합을 사용할 수 있습니다.
위의 개념을 구현하는 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;
}
메모: 이 문제는 IN과 매우 유사합니다 Google Code Jam 2008 자격 라운드 문제: 파리와 chatter. 스코어 링크를 클릭하여 솔루션의 소스 코드를 다운로드 할 수 있습니다.
답변 주셔서 감사합니다.
나는 지역 추정이 충분하다고 언급하는 것을 잊었다. 저것; 결국, 모든 옵션을 살펴본 후, 나는 원에서 임의의 지점을 생성하고 상자에 있는지 테스트하는 Monte-Carlo 추정과 함께 갔다.
제 경우에는 이것이 더 성능이있을 것입니다. (원 위에 그리드가 배치되어 있으며 각 그리드 세포에 속하는 원의 비율을 측정해야합니다.)
감사
다음은 문제에 대한 또 다른 해결책입니다.
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)));
}
