منطقة التقاطع بين الدائرة والمستطيل
https://stackoverflow.com/questions/622287
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أبحث عن طريقة سريعة لتحديد مساحة التقاطع بين المستطيل والدائرة (أحتاج إلى القيام بملايين هذه الحسابات).
خاصية محددة هي أنه في جميع الحالات ، تحتوي الدائرة والمستطيل دائمًا على نقطتين من التقاطع.
المحلول
بالنظر إلى 2 نقطتين من التقاطع:
0 رؤوس داخل الدائرة: منطقة أ الجزء الدائري
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] (ستؤدي القيم الأخرى إلى مخرجات وهمية) لكننا نعلم أن المنطقة خارج هذا النطاق هي صفر ، بحيث يتم التعامل معها بسهولة. دعنا نفترض دائرة الوحدة للبساطة ، يمكننا دائمًا توصيل المركز ونصف قطرها لاحقًا:
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 يضيف لصناديق لا تتقاطع مع المحور x ومقالفة من ذلك (وإضافة واحدة أخرى) للمربعات التي تفعل. لاحظ أن الانقسامات حسب نصف القطر ويمكن تقليلها إلى قسمين ومجموعة من الضربات. إذا تقاطع المربع المعني مع محور X لكنه لم يتقاطع مع محور Y ، فيمكنك تدوير كل شيء pi/2 والقيام الحساب في التكلفة الأصلية.
أنا أستخدمه كمرجع لتصحيح Debug Subpixel-Circise Circle Dircledizer. إنه بطيء مثل الجحيم :) ، أحتاج إلى حساب مساحة تقاطع كل بكسل في المربع المحيط بالدائرة مع الدائرة للحصول على ألفا. يمكنك أن ترى نوعًا ما أنه يعمل ولا يبدو أن هناك قطع أثرية رقمية. الشكل أدناه هو قطعة من مجموعة من الدوائر مع زيادة نصف القطر من 0.3 بكسل إلى حوالي 6 بكسل ، وضعت في دوامة.
آمل أن لا يكون شكل سيء نشر إجابة على مثل هذا السؤال القديم. نظرت إلى الحلول المذكورة أعلاه وعملت خوارزمية تشبه الإجابة الأولى من دانييلز ، لكنها أكثر إحكاما.
باختصار ، افترض أن المنطقة الكاملة في المستطيل ، قم بطرح الأجزاء الأربعة في الطائرات النصف الخارجية ، ثم أضف أي المناطق في الأرباع الخارجية الأربعة ، مع التخلص من الحالات التافهة على طول الطريق.
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
بالمناسبة ، يتم اشتقاق هذه الصيغة الأخيرة لمنطقة دائرة موجودة في رباعية الطائرة بسهولة كمجموع للجزء الدائري ، ومثلاثتين يمين ومستطيل.
يتمتع.
فيما يلي كيفية حساب المنطقة المتداخلة بين الدائرة والمستطيل حيث يقع مركز الدائرة خارج المستطيل. يمكن تخفيض حالات أخرى إلى هذه المشكلة.
يمكن حساب المنطقة من خلال دمج معادلة الدائرة y = sqrt [a^2 - (xh)^2] + k حيث يكون A RADIUS ، (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;
}
ملحوظة: هذه المشكلة تشبه إلى حد كبير واحدة في جولة تأهيل Code Jam 2008 مشكلة: يطير الضيق. يمكنك النقر فوق روابط النتيجة لتنزيل الكود المصدري للحل أيضًا.
شكرا على الإجابات ،
لقد نسيت أن أذكر أن تقديرات المنطقة كانت كافية. الذي - التي؛ S في النهاية ، بعد النظر في جميع الخيارات ، ذهبت مع تقدير Monte-Carlo حيث أقوم بإنشاء نقاط عشوائية في الدائرة واختبار ما إذا كانت في المربع.
في حالتي ، من المحتمل أن يكون هذا أكثر أداء. (لدي شبكة وضعت على الدائرة وعلي أن أقسس نسبة الدائرة التي تنتمي إلى كل من خلايا الشبكة.)
شكرًا
ربما يمكنك استخدام الإجابة على هذا السؤال, ، حيث يتم طلب منطقة التقاطع بين الدائرة والمثلث. اقسم مستطلك إلى مثلثتين واستخدم الخوارزميات الموضحة هناك.
طريقة أخرى هي رسم خط بين نقطتي التقاطع ، وهذا يقسم منطقتك إلى مضلع (3 أو 4 حواف) و الجزء الدائري, ، لكلاهما يجب أن تكون قادرًا على العثور على المكتبات أسهل أو إجراء الحسابات بنفسك.
إليك حل آخر للمشكلة:
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)));
}
