Schnittfläche zwischen Kreis und Rechteck
https://stackoverflow.com/questions/622287
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich suche nach einer schnellen Möglichkeit, die Schnittfläche zwischen einem Rechteck und einem Kreis zu bestimmen (ich muss Millionen dieser Berechnungen durchführen).
Eine Besonderheit besteht darin, dass Kreis und Rechteck in allen Fällen immer 2 Schnittpunkte haben.
Lösung
Gegeben sind 2 Schnittpunkte:
0 Eckpunkte liegt innerhalb des Kreises:Die Fläche von a Kreissegment
XXXXX -------------------
X X X X Circular segment
X X XX XX
+-X-------X--+ XXXXXXXX
| X X |
| XXXXX |
1 Scheitelpunkt liegt innerhalb des Kreises:Die Summe der Flächen eines Kreissegments und eines Dreiecks.
XXXXX XXXXXXXXX
X X Triangle ->X _-X
X X X _- X
X +--X--+ X _- X <- Circular segment
X | X | X- XXX
XXXXX | XXXX
| |
2 Eckpunkte sind innerhalb des Kreises:Die Summe der Fläche zweier Dreiecke und eines Kreissegments
XXXXX +------------X
X X | _--'/'X
X +--X--- Triangle->| _-- / X
X | X |_-- /XX <- Circular segment
X +-X---- +-------XX
XXXXX Triangle^
3 Eckpunkte sind innerhalb des Kreises:Die Fläche des Rechtecks minus die Fläche eines Dreiecks plus die Fläche eines Kreissegments
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
Um diese Flächen zu berechnen:
Die meisten Punkte, die Sie verwenden müssen, finden Sie unter Schnittpunkt einer Geraden und eines Kreises
Die Flächen, die Sie berechnen müssen, finden Sie unter Berechnen der Fläche eines Kreissegments Und Berechnen der Fläche eines Dreiecks.
Sie können feststellen, ob sich ein Scheitelpunkt innerhalb des Kreises befindet, indem Sie berechnen, ob sein Abstand vom Mittelpunkt kleiner als der Radius ist.
Andere Tipps
Mir ist klar, dass dies vor einiger Zeit beantwortet wurde, aber ich löste das gleiche Problem und ich konnte keine außerhalb der Box-praktikable Lösung finden, die ich verwenden konnte. Beachten Sie, dass meine Kästchen sind Achse ausgerichtet, Dies wird durch das OP nicht ganz angegeben. Die folgende Lösung ist völlig allgemein und funktioniert für eine beliebige Anzahl von Kreuzungen (nicht nur zwei). Beachte Quads), Sie können die runden Kreise ausnutzen, die Koordinaten von allem drehen, so dass die Box axis ausgerichtet ist und dann Verwenden Sie diesen Code.
Ich möchte Integration verwenden - das scheint eine gute Idee zu sein. Beginnen wir mit dem Schreiben einer offensichtlichen Formel zum Aufstellen eines Kreises:
x = center.x + cos(theta) * radius
y = center.y + sin(theta) * radius
^
|
|**### **
| #* # * * x
|# * # * # y
|# * # *
+-----------------------> theta
* # * #
* # * #
* #* #
***###
Das ist schön, aber ich kann den Bereich dieses Kreises nicht über integrieren x oder y; Das sind unterschiedliche Mengen. Ich kann mich nur über den Winkel integrieren theta, nachgibt Bereiche von Pizza -Scheiben. Nicht was ich will. Versuchen wir, die Argumente zu ändern:
(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
Das ist eher so. Jetzt angegeben der Bereich von x, Ich kann mich integrieren y, um einen Bereich der oberen Hälfte eines Kreises zu bekommen. Dies gilt nur für x in [center.x - radius, center.x + radius] (Andere Werte verursachen imaginäre Ausgänge), aber wir wissen, dass der Bereich außerhalb dieses Bereichs Null ist, so dass dies leicht behandelt wird. Nehmen wir den Einfachheit halber an, wir können die Mitte immer später anschließen und später zurückversetzen:
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
Diese Funktion hat in der Tat ein Integral von pi/2, Da es sich um eine obere Hälfte eines Einheitskreises handelt (der Bereich eines halben Kreises ist pi * r^2 / 2 Und wir sagten bereits Einheit, was bedeutet r = 1). Jetzt können wir den Schnittbereich eines halben Kreises und eine unendlich hohe Kiste berechnen, die auf der X-Achse steht (die Mitte des Kreises liegt auch auf der X-Achse), indem wir über integriert sind 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
Dies ist möglicherweise nicht sehr nützlich, da unendlich hohe Kisten nicht das sind, was wir wollen. Wir müssen einen weiteren Parameter hinzufügen, um die untere Kante der unendlich hohen Kiste zu befreien:
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
Wo h ist der (positive) Abstand der Unterkante unserer unendlichen Kiste von der x -Achse. Das section Die Funktion berechnet die (positive) Position des Schnittpunkts des Einheitskreises mit der durch die horizontalen Linie gegeben durch y = h Und wir konnten es durch Lösen definieren:
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)
Jetzt können wir die Dinge in Gang bringen. So berechnen Sie den Schnittbereich eines endlichen Kastens, der einen Einheitskreis über der x -Achse schneidet:
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
Das ist schön. Wie wäre es also mit einer Box, die nicht über der x -Achse liegt? Ich würde sagen, nicht alle Kisten sind. Drei einfache Fälle entstehen:
- Die Box befindet sich über der x -Achse (Verwenden Sie die obige Gleichung)
- Die Box befindet sich unter der x -Achse (drehen Sie das Vorzeichen von Y -Koordinaten und verwenden Sie die obige Gleichung)
- Die Box kreuzt die x -Achse (teilen Sie die Box in die obere und untere Hälfte auf, berechnen Sie die Fläche von beiden mit der oben genannten und summieren Sie sie).
Leicht genug? Schreiben wir einen 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);
}
Und einige grundlegende 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
Die Ausgabe davon ist:
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
Was mir richtig erscheint. Möglicherweise möchten Sie die Funktionen einführen, wenn Sie Ihrem Compiler nicht vertrauen, dass Sie dies für Sie tun.
Dies verwendet 6 sqrt, 4 Asin, 8 Div, 16 Mul und 17 hinzu, für Kästen, die die X -Achse nicht schneiden, und ein Doppel davon (und 1 weitere Add) für Kästchen, die dies tun. Beachten Sie, dass die Abteilungen im Radius erfolgen und auf zwei Abteilungen und eine Reihe von Multiplikationen reduziert werden können. Wenn das fragliche Box die x -Achse schneidet, aber die y -Achse nicht schnitt pi/2 und machen Sie die Berechnung in den ursprünglichen Kosten.
Ich benutze es als Verweis auf Debugg-Rasterizer mit Subpixel-Precise Antialias Circle. Es ist höllisch langsam :), ich muss den Schnittbereich jedes Pixels im Begrenzungsfeld des Kreises mit dem Kreis berechnen, um Alpha zu erhalten. Sie können sehen, dass es funktioniert und keine numerischen Artefakte erscheinen. Die folgende Abbildung ist ein Diagramm einer Reihe von Kreisen, wobei der Radius von 0,3 px auf etwa 6 px steigt und in einer Spirale ausgelegt ist.
Ich hoffe, es ist nicht schlecht, eine Antwort auf eine so alte Frage zu posten.Ich habe mir die oben genannten Lösungen angesehen und einen Algorithmus ausgearbeitet, der Daniels erster Antwort ähnelt, aber ein gutes Stück enger ist.
Kurz gesagt: Gehen Sie davon aus, dass sich die gesamte Fläche im Rechteck befindet, subtrahieren Sie die vier Segmente in den äußeren Halbebenen, addieren Sie dann alle Flächen in den vier äußeren Quadranten und verwerfen Sie dabei triviale Fälle.
pseudocde (mein tatsächlicher Code besteht nur aus ~12 Zeilen.)
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
Übrigens lässt sich die letzte Formel für die Fläche eines Kreises in einem ebenen Quadranten leicht als Summe eines Kreissegments, zweier rechtwinkliger Dreiecke und eines Rechtecks ableiten.
Genießen.
Im Folgenden wird beschrieben, wie die Überlappungsfläche zwischen Kreis und Rechteck berechnet wird, wobei der Mittelpunkt des Kreises außerhalb des Rechtecks liegt.Andere Fälle lassen sich auf dieses Problem reduzieren.
Die Fläche kann durch Integration der Kreisgleichung berechnet werden y = sqrt[a^2 - (x-h)^2] + k Dabei ist a der Radius und (h,k) der Kreismittelpunkt, um die Fläche unter der Kurve zu ermitteln.Sie können die Computerintegration verwenden, bei der die Fläche in viele kleine Rechtecke unterteilt wird und deren Summe berechnet wird, oder Sie verwenden hier einfach die geschlossene Form.
Und hier ist eine C#-Quelle, die das obige Konzept implementiert.Beachten Sie, dass es einen Sonderfall gibt, bei dem das angegebene x außerhalb der Grenzen des Kreises liegt.Ich verwende hier nur eine einfache Problemumgehung (die nicht in allen Fällen zu den richtigen Antworten führt).
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;
}
Notiz: Dieses Problem ist einem in sehr ähnlich Qualifikationsrunde für Google Code Jam 2008 Problem: Fliegenklatsche.Sie können auch auf die Score-Links klicken, um den Quellcode der Lösung herunterzuladen.
Danke für die Antworten,
Ich habe vergessen zu erwähnen, dass die Gebietsschätzungen genug waren. Dass; S Warum ich am Ende, nachdem ich alle Optionen angesehen hatte, habe ich mich mit Monte-Carlo-Schätzung angesehen, bei der ich zufällige Punkte im Kreis generiere und testet, wenn sie in der Box sind.
In meinem Fall ist dies wahrscheinlich leistungsfähiger. (Ich habe ein Netz über den Kreis und muss das Verhältnis des Kreises zu jedem der Netzzellen messen.)
Vielen Dank
Vielleicht können Sie die Antwort auf verwenden diese Frage, wo der Schnittbereich zwischen einem Kreis und einem Dreieck gefragt wird. Teilen Sie Ihr Rechteck in zwei Dreiecke und verwenden Sie die dort beschriebenen Algorithmen.
Eine andere Möglichkeit besteht darin, eine Linie zwischen den beiden Schnittpunkten zu ziehen, dies spaltet Ihren Bereich in ein Polygon (3 oder 4 Kanten) und a auf Rundsegment, Für beide sollten Sie in der Lage sein, Bibliotheken leichter zu finden oder die Berechnungen selbst durchzuführen.
Hier ist eine weitere Lösung für das 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)));
}
