Tôi đang tìm một cách nhanh chóng để xác định diện tích giao nhau giữa hình chữ nhật và hình tròn (tôi cần thực hiện hàng triệu tính toán này).Diện tích giao lộ giữa hình tròn và hình chữ nhật
Thuộc tính cụ thể là trong mọi trường hợp hình tròn và hình chữ nhật luôn có 2 điểm giao nhau.
Với 2 điểm giao nhau:
0 đỉnh là bên trong vòng tròn: Diện tích của một circular segment
XXXXX -------------------
X X X X Circular segment
X X XX XX
+-X-------X--+ XXXXXXXX
| X X |
| XXXXX |
1 đỉnh là bên trong vòng tròn: Tổng số các lĩnh vực một đoạn hình tròn và một hình tam giác.
XXXXX XXXXXXXXX
X X Triangle ->X _-X
X X X _- X
X +--X--+ X _- X <- Circular segment
X | X | X- XXX
XXXXX | XXXX
| |
2 đỉnh là bên trong vòng tròn: Tổng diện tích của hai tam giác và một phân khúc tròn
XXXXX +------------X
X X | _--'/'X
X +--X--- Triangle->| _-- /X
X | X |_-- /XX <- Circular segment
X +-X---- +-------XX
XXXXX Triangle^
3 đỉnh là bên trong vòng tròn: Diện tích trừ hình chữ nhật diện tích hình tam giác cộng với diện tích của đoạn đường tròn
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
Để tính toán reas:
Hầu hết các điểm bạn sẽ cần phải sử dụng có thể được tìm thấy bằng cách tìm các intersection of a line and a circle
Các khu vực bạn cần phải tính toán có thể được tìm thấy bằng cách computing the area of a circular segment và computing the area of a triangle.
Bạn có thể xác định liệu một đỉnh có nằm trong vòng tròn hay không bằng cách tính toán nếu khoảng cách của nó từ trung tâm nhỏ hơn bán kính.
Có lẽ bạn có thể sử dụng câu trả lời cho this question, trong đó khu vực giao nhau giữa vòng tròn và hình tam giác được hỏi. Chia hình chữ nhật của bạn thành hai hình tam giác và sử dụng các thuật toán được mô tả ở đó.
Cách khác là vẽ một đường thẳng giữa hai điểm giao nhau, điều này chia khu vực của bạn thành đa giác (3 hoặc 4 cạnh) và circular segment, cho cả hai bạn sẽ có thể dễ dàng tìm thấy thư viện hoặc tự tính toán.
Sau đây là cách tính diện tích chồng chéo giữa hình tròn và hình chữ nhật trong đó tâm vòng tròn nằm bên ngoài hình chữ nhật. Các trường hợp khác có thể được giảm xuống vấn đề này.
Khu vực có thể được tính bằng cách tích hợp phương trình vòng tròn y = sqrt [a^2 - (xh)^2] + k trong đó bán kính là (h, k) là tâm tròn, để tìm khu vực dưới đường cong. Bạn có thể sử dụng tích hợp máy tính nơi mà khu vực được chia thành nhiều hình chữ nhật nhỏ và tính tổng của chúng, hoặc chỉ sử dụng hình thức đóng ở đây.
Và đây là nguồn C# triển khai khái niệm ở trên. Lưu ý rằng có một trường hợp đặc biệt trong đó x được chỉ định nằm ngoài ranh giới của vòng tròn. Tôi chỉ cần sử dụng một cách giải quyết đơn giản ở đây (không sản xuất các đáp án đúng trong mọi trường hợp)
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;
}
Lưu ý: Vấn đề này rất giống với một trong Google Code Jam 2008 Qualification round vấn đề: Fly Swatter. Bạn có thể nhấp vào liên kết điểm để tải xuống mã nguồn của giải pháp.
Cảm ơn câu trả lời,
Tôi quên đề cập đến ước lượng diện tích đó là đủ. Điều đó; tại sao cuối cùng, sau khi xem xét tất cả các tùy chọn, tôi đã đi với ước tính monte-carlo nơi tôi tạo ra các điểm ngẫu nhiên trong vòng tròn và kiểm tra xem chúng có nằm trong hộp hay không.
Trong trường hợp của tôi, điều này có thể có hiệu suất cao hơn. (Tôi có một mạng lưới đặt trên vòng tròn và tôi có để đo tỷ lệ của vòng tròn thuộc mỗi tế bào lưới.)
Cảm ơn
Ah, ước tính không sao tạo ra sự khác biệt lớn:] –
Dưới đây là một giải pháp cho vấn đề này:
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)));
}
Tôi hy vọng hình thức không tồi của nó để đăng câu trả lời cho câu hỏi cũ như vậy. Tôi đã xem xét các giải pháp trên và làm ra một thuật toán tương tự như câu trả lời đầu tiên của Daniels, nhưng một chút tốt hơn.
Tóm lại, giả sử toàn bộ khu vực nằm trong hình chữ nhật, trừ đi bốn đoạn trong mặt phẳng nửa bên ngoài, sau đó thêm bất kỳ khu vực nào trong bốn góc phần tư bên ngoài, loại bỏ các trường hợp tầm thường trên đường đi.
pseudocde (mã thực tế của tôi là chỉ ~ 12 dòng ..)
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
Ngẫu nhiên, rằng công thức cuối cùng cho diện tích hình tròn chứa trong một góc phần tư chiếc máy bay được dễ dàng có nguồn gốc là tổng của một phân khúc tròn , hai tam giác vuông và hình chữ nhật.
Tận hưởng.
Tôi nhận thấy điều này đã được trả lời trong khi trước đây nhưng tôi đang giải quyết cùng một vấn đề và tôi không thể tìm thấy giải pháp khả thi hoàn toàn có thể sử dụng được. Lưu ý rằng các hộp của tôi là axis aligned, điều này không được OP xác định rõ ràng. Các giải pháp dưới đây là hoàn toàn chung chung, và sẽ làm việc cho bất kỳ số lượng các nút giao (không chỉ có hai). Lưu ý rằng nếu hộp của bạn không được căn chỉnh theo trục (nhưng các hộp có góc vuông, thay vì chung là quads), bạn có thể tận dụng vòng tròn tròn, xoay tọa độ của mọi thứ sao cho hộp kết thúc theo trục và sau đó sử dụng mã này.
Tôi muốn sử dụng tích hợp - điều đó có vẻ như là một ý tưởng hay. Hãy bắt đầu với viết một công thức rõ ràng cho âm mưu một vòng tròn:
x = center.x + cos(theta) * radius
y = center.y + sin(theta) * radius
^
|
|**### **
| #* # * * x
|# * # * # y
|# * # *
+-----------------------> theta
* # * #
* # * #
* #* #
***###
này là tốt đẹp, nhưng tôi không thể để tích hợp các khu vực của vòng tròn đó qua x hoặc y; đó là những số lượng khác nhau.Tôi chỉ có thể tích hợp trên các góc theta, năng suất các lát bánh pizza. Không phải những gì tôi muốn. Hãy cố gắng thay đổi các đối số:
(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
Điều đó giống như vậy. Bây giờ cho phạm vi của x, tôi có thể tích hợp trên y, để có được một khu vực của nửa trên của một vòng tròn. Điều này chỉ giữ cho x trong [center.x - radius, center.x + radius] (các giá trị khác sẽ gây ra kết quả đầu ra ảo) nhưng chúng tôi biết rằng khu vực bên ngoài phạm vi đó bằng 0, do đó được xử lý dễ dàng. Giả sử vòng tròn đơn vị cho đơn giản, chúng tôi luôn có thể cắm trung tâm và bán kính quay lại sau trên:
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
Chức năng này thực sự có thể thiếu trong pi/2, vì nó là một nửa trên của một vòng tròn đơn vị (diện tích nửa vòng tròn là pi * r^2/2 và chúng tôi đã nói đơn vị, có nghĩa là r = 1). Bây giờ chúng ta có thể tính toán diện tích giao điểm của một nửa vòng tròn và một hộp cao vô cùng, đứng trên trục x (trung tâm của vòng tròn cũng nằm trên trục x) bằng cách tích hợp trên 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
này có thể không hữu ích lắm, vì hộp cao vô cùng không phải là thứ chúng ta muốn. Chúng ta cần phải thêm một tham số hơn để có thể giải phóng mép dưới cùng của hộp cao vô hạn:
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
đâu h là (dương tính) khoảng cách cạnh đáy của hộp vô hạn của chúng tôi từ trục x . Chức năng section tính (dương tính) vị trí giao nhau của đường tròn đơn vị với các đường ngang do y = h và chúng ta có thể định nghĩa nó bằng cách giải quyết:
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)
Bây giờ chúng ta có thể nhận được điều đang xảy ra. Vì vậy, cách tính diện tích giao nhau của một hộp hữu hạn giao nhau với một vòng tròn đơn vị phía trên trục 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
Thật tuyệt. Vậy làm thế nào về một hộp mà không phải là trên trục x? Tôi muốn nói không phải tất cả các hộp đều có. Ba trường hợp đơn giản nảy sinh:
Đủ dễ dàng? Hãy viết một số mã:
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);
}
Và một số xét nghiệm đơn vị cơ bản:
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
Kết quả của việc này là:
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
Mà dường như đúng với tôi. Bạn có thể muốn nội tuyến các chức năng nếu bạn không tin tưởng trình biên dịch của bạn để làm điều đó cho bạn.
Điều này sử dụng 6 sqrt, 4 asin, 8 div, 16 mul và 17 bổ sung cho các hộp không giao nhau với trục x và gấp đôi số đó (và 1 thêm) cho hộp làm. Lưu ý rằng các phân chia là bởi bán kính và có thể được giảm xuống hai đơn vị và một loạt các phép nhân. Nếu hộp được đề cập giao cắt trục x nhưng không giao nhau với trục y, bạn có thể xoay mọi thứ theo pi/2 và thực hiện phép tính theo giá gốc.
Tôi đang sử dụng nó làm tài liệu tham khảo để gỡ lỗi trình chỉnh sửa vòng tròn antialiased chính xác subpixel. Nó là chậm như địa ngục :), tôi cần phải tính toán diện tích giao nhau của mỗi điểm ảnh trong hộp giới hạn của vòng tròn với vòng tròn để có được alpha. Bạn có thể thấy rằng nó hoạt động và không có hiện vật số dường như xuất hiện. Hình bên dưới là đồ thị của một loạt các vòng tròn có bán kính tăng từ 0,3 px đến khoảng 6 px, được bố trí theo hình xoắn ốc.
Họ chỉ có 2 điểm giao lộ? Hay họ có ít nhất 2 điểm giao nhau? – bigmonachus
Bạn có cần tính diện tích theo đơn vị vuông hoặc trả về một tập hợp các đoạn đường xác định khu vực không? – Leonard
Nếu một trong hai bên kia, hoặc nếu cả hai không chồng lên nhau, thì không có điểm giao nhau. Nếu đường tròn tiếp xúc với bất kỳ cạnh nào của hình chữ nhật, thì chỉ có một điểm giao nhau. – duffymo