Berechnen Sie den Schnittbereich zwischen einem Kreis und einem Dreieck?
https://stackoverflow.com/questions/540014
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie man den Bereich der Kreuzung zwischen einem Dreieck (angegeben als drei (X, Y) Paare) und ein Kreis (X, Y, R) nicht berechnen? Ich habe einige der Suche ohne Erfolg getan. Dies ist für die Arbeit, keine Schule. :)
Es wäre so etwas wie dies in C # aussehen:
struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;
// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
...
}
Lösung
Wenn Sie eine exakte Lösung (oder zumindest so genau wie möglich Gleitkommaarithmetik bekommen verwenden) dann dies eine Menge Lauferei beteiligen wird, weil es so viele Fälle sind zu berücksichtigen.
Ich zähle neun verschiedene Fälle (in der Abbildung unten durch die Anzahl der Eckpunkt des Dreiecks innerhalb des Kreises kategorisierten, und die Anzahl der Kanten des Dreiecks, die in dem Kreis schneiden oder enthalten sind):
(Allerdings ist diese Art der Aufzählung von geometrischen Fällen ist bekannt, schwierig zu sein, und es würde mich nicht überraschen, wenn ich ein oder zwei verpasst!)
So ist der Ansatz:
-
für jeden Eckpunkt des Dreiecks bestimmen, ob sie innerhalb des Kreises ist. Ich werde Sie wissen, zu übernehmen, wie das zu tun.
-
für jede Kante des Dreiecks bestimmen, ob er den Kreis schneidet. (Ich schrieb auf eine Methode hier oder sehen jede Computational Geometry Buch .) Sie werden den Punkt oder die Schnittpunkte (falls vorhanden) für die Verwendung in Schritt 4.
berechnen müssen
-
Sie fest, welche der neun Fälle, die Sie haben.
-
Berechnen Sie den Bereich der Kreuzung. Fälle 1, 2 und 9 sind einfach. in Dreiecken und Kreissegmente In den übrigen sechs Fällen habe ich gestrichelten Linien gezeichnet zu zeigen, wie die Schnittfläche partitionieren bezogen auf den ursprünglichen Eckpunkt des Dreiecks, und auf dem Schnittpunkt Sie berechnet in Schritt 2.
Dieser Algorithmus sein wird ziemlich empfindlich und anfällig für Fehler, die nur einer der Fälle betreffen, so stellen Sie sicher, dass Sie Testfälle, die alle neun Fälle abdecken (und ich schlage vor, Permutation die Eckpunkte der Testdreiecke auch). Achten Sie besonders auf Fälle, in denen einer der Eckpunkte des Dreiecks am Rand des Kreises ist.
Wenn Sie nicht eine exakte Lösung benötigen, dann die Zahlen Rastern und die Pixel in der Kreuzung zu zählen (wie durch ein paar anderen Befragten vorgeschlagen) scheint wie ein viel einfacher Ansatz, um Code und entsprechend weniger fehleranfällig.
Andere Tipps
Zuerst werden wir erinnern uns daran, wie die Fläche eines Polygons zu finden. Sobald wir dies getan haben, zu dem Algorithmus die Kreuzung zwischen einem Polygon zu finden und einem Kreis soll leicht zu verstehen sein.
Wie wird die Fläche eines Polygons finden
ist im Fall eines Dreiecks aussehen lassen, weil alle wesentlichen Logik erscheint. Nehmen wir an, wir mit den Eckpunkten eines Dreiecks haben (x1, y1), (x2, y2) und (x3, y3), wie Sie rund um das Dreieck gegen den Uhrzeigersinn gehen, wie in der folgenden Abbildung dargestellt:
Dann können Sie den Bereich, der durch die Formel berechnen
A = (x1 y2 + x2 y3 + x3 y1 - x2y1- x3 y2 - x1y3). / 2
Um zu sehen, warum diese Formel funktioniert, machen sie es neu anordnen, so dass es in der Form
A = (x1 y2 - x2 y1) / 2 + (x2 y3 - x3 y2) / 2 +. (X3 y1 - x1y3) / 2
Nun ist der erste Term ist die folgende Fläche, die in unserem Fall positiv ist:
Wenn es nicht klar ist, dass der Bereich der grünen Region in der Tat ist (x1 y2 - x2 y1) / 2, dann lesen Sie diese .
Der zweite Term ist dieser Bereich, was wiederum positiv ist:
Und der dritte Bereich ist in der folgenden Abbildung dargestellt. Dieses Mal ist der Bereich negativ
diese drei bis Hinzufügen erhalten wir folgendes Bild
Wir sehen, dass die grüne Fläche, die außerhalb des Dreiecks war durch den roten Bereich aufgehoben wird, so dass die Nettofläche nur die Fläche des Dreiecks ist, und das zeigt, warum unsere Formel in diesem Fall zutraf.
Was ich oben gesagt war die intuitive Erklärung, warum der Bereich Formel richtig war. Eine rigorosere Erklärung wäre zu beachten, dass, wenn wir den Bereich von einer Kante zu berechnen, der Bereich, erhalten wir die Umgebung, die wir von der Integration r ^ 2dθ / 2 erhalten würden, so dass wir die Integration effektiv r ^ 2dθ / 2 um die Grenze des Polygons, und schürt Satz ergibt dies das gleiche Ergebnis wie die Integration von rdrdθ über die Region um das Polygon begrenzt. Da die Integration von rdrdθ über den durch das Polygon begrenzten Bereich der Fläche gibt, schließen wir, dass unser Verfahren richtig das Gebiet geben muss.
Bereich der Kreuzung eines Kreises mit einem Polygon
Lassen Sie sich nun darüber diskutieren, wie die Fläche des Schnittpunktes eines Kreises mit dem Radius R mit einem Polygon zu finden, wie zeigt in der folgenden Abbildung:
Wir interessieren uns für den Bereich der grünen Region. Wir können, wie im Fall des einzelnen Polygon, brechen unsere Berechnung für jede Seite des Polygons eine Fläche in der Suche, und dann die Bereiche addieren.
Unser erster Bereich wird wie folgt aussehen:
Der zweite Bereich wird wie folgt aussehen
Und der dritte Bereich wird
Auch hier sind die ersten beiden Bereiche positiv in unserem Fall, während der dritte negativ sein wird. Hoffentlich wird die Stornierungen arbeiten, so dass die Nettofläche ist in der Tat das Gebiet, das wir interessiert sind. Mal sehen.
Tatsächlich ist die Summe der Flächen wird Bereich sind wir interessiert an.
Auch hier können wir eine strengere Erklärung geben, warum das funktioniert. Lasse ich die Region durch den Schnittpunkt definiert sein und P das Polygon sein. Dann aus der vorherigen Diskussion wissen wir, dass wir an den Computer wollen das Integral von r ^ 2dθ /2 um die Grenze von I. dies schwierig jedoch zu tun, weil es die Kreuzung zu finden, erfordert.
Stattdessen haben wir ein Integral über das Polygon. Wir integrierten max (R, R) ^ 2 d & thgr; / 2 über die Grenze des Polygons. Um zu sehen, warum dies die richtige Antwort gibt, lassen Sie sich eine Funktion π definieren, die einen Punkt in Polarkoordinaten nimmt (r, θ) zu dem Punkt (max (r, R), θ). Es sollte nicht verwirrend sein, auf denen die Koordinatenfunktionen von π (r) = max (R, R) und π (θ) = θ zu beziehen. Dann, was wir taten, war π (r) ^ 2 dR / 2 über die Grenze des Polygons zu integrieren.
Auf der anderen Seite, da π (θ) = θ, das ist das gleiche wie die Integration von π (r) ^ 2 dπ (θ) / 2 über die Grenze des Polygons.
Jetzt eine Veränderung der Variablen tun, finden wir, dass wir die gleiche Antwort bekommen würde, wenn wir r ^ 2 dR / 2 über die Grenze von π (P) integriert, wobei π (P), um das Bild von P unter π ist.
Stokes Theorem Mit wieder wissen wir, dass r Integration ^ 2 dR / 2 über die Grenze von π (P) gibt uns die Fläche von π (P). Mit anderen Worten gibt es die gleiche Antwort wie die Integration von dxdy über π (P).
Mit einer Änderung der Variable wieder, wissen wir, dass die Integration von dxdy über π (P) ist die gleiche wie Jdxdy über P Integration, wobei J die Jacobi von π ist.
Jetzt können wir das Integral von Jdxdy in zwei Bereiche aufgeteilt: der Teil in dem Kreis und der Teil außerhalb des Kreises. Nun π läßt Punkte im Kreis allein so J = 1 gibt, so ist der Beitrag von diesem Teil von P ist der Bereich des Teils von P, die im Kreis liegt das heißt, der Bereich der Kreuzung. Der zweite Bereich ist der Bereich außerhalb des Kreises. Es J = 0, da π diesen Teil an die Grenze des Kreises kollabiert nach unten.
So was wir berechnen ist in der Tat der Bereich der Kreuzung.
Nun, da wir relativ sicher sind, wir wissen, konzeptionell, wie die Gegend zu finden, lassen Sie uns genauer darüber sprechen, wie der Beitrag von einem einzelnen Segment zu berechnen. Lassen Sie uns, indem Sie auf ein Segment in beginnen, was ich nennen „Standardgeometrie“. Es wird unten gezeigt.
In der Standardgeometrie, geht die Kante horizontal von links nach rechts. Es wird durch drei Zahlen beschrieben: xi, die x-Koordinate, wo die Kante beginnt, xf, die x-Koordinate, wo die Kante endet, und y, das y des Randes koordinieren.
Nun sehen wir, dass, wenn | y | Der Bereich der Region 2 ist nur die Fläche eines Dreiecks. Allerdings müssen wir vorsichtig Zeichen sein. Wir wollen, dass der Bereich, positiv sein gezeigt, so dass wir das Gebiet werden sagen - (Xint - (-Xint)). Y / 2 Eine andere Sache im Auge zu behalten ist, dass im Allgemeinen, xi nicht weniger sein muss als -Xint und xf nicht als Xint größer sein muss. Der andere Fall zu prüfen ist, | y | > R. Dieser Fall einfacher, weil es nur ein Stück ist, der Region 1 in der Figur ähnlich ist. Nun, da wir wissen, wie das Gebiet von einer Kante in Standardgeometrie zu berechnen, das einzige, was zu tun ist, beschreiben, wie man jede Kante in Standard-Geometrie zu verwandeln. Aber das ist nur eine einfache Änderung der Koordinaten. Gegeben einig mit Anfangspunkt vi und letzten Vertex vf, der neue x-Einheitsvektor ist der Einheitsvektor zeigt von vi zu vf. Dann xi ist nur die Verschiebung des VI von der Mitte des Kreises in x punktiert, und xf ist nur xi plus dem Abstand zwischen VI und vf. Inzwischen y wird durch den Keil Produkt von x mit der Verschiebung von vi von der Mitte des Kreises gegeben. Das ist die Beschreibung des Algorithmus, jetzt ist es Zeit, einen Code zu schreiben. Ich werde Java verwenden. Zunächst einmal, da wir mit Kreisen arbeiten, sollten wir einen Kreis Klasse Für Polygone, werde ich Javas Jetzt für die eigentliche Arbeit. Ich werde die Logik der Iterieren durch die Kanten trennen, um die Kanten in Standardgeometrie usw. setzen, aus der Logik der Berechnung der Fläche Sobald dies erledigt ist. Der Grund dafür ist, dass Sie in der Zukunft etwas anderes neben oder zusätzlich zu dem Bereich berechnen wollen, und Sie wollen in der Lage sein, den Code wieder zu verwenden, die mit Iterieren durch die Kanten zu behandeln. Also ich habe eine generische Klasse, die eine Eigenschaft der Klasse Es hat drei statische Methoden, die nur Rechen Geometrie helfen: Es gibt zwei Instanzfelder, ein Als nächstes kommt die Methode zur Berechnung, was wir berechnen möchten: Lassen Sie uns einen zweiten nehmen schnell an Als nächstes Ich erkläre die Die Die meisten der Rest des Codes dieser Methode ist uninteressant Logik im Zusammenhang durch die Knoten iterieren. Die wichtige Sache ist, dass einmal pro Iteration der while-Schleife nenne ich auf den Code für Bei diesem Verfahren implementieren I die Schritte eine Kante in die Standardgeometrie zu transformieren, wie oben beschrieben. Zuerst berechnen Als nächstes berechne ich die Länge der Verschiebung, da dies notwendig ist, um das x-Einheitsvektor zu erhalten. Sobald ich diese Informationen vorliegen, berechne ich die Verschiebung von der Mitte des Kreises auf den Anfangspunkt. Das Skalarprodukt dieses mit Nun, da ich das Problem in die Standardgeometrie verwandelt habe, wird es leicht sein, zu beschäftigen. Das ist, was die Die erste Wenn Schnittpunkt möglich ist, berechnen I die x-Koordinate des Schnitt, Region 1 zu handhaben, ich überprüfen, ob Ich habe eine ähnliche Sache zu handhaben Bereich 3. Für Bereich 2, ich habe eine gewisse Logik zu tun, dass Lassen Sie uns auf den Code für ich einfach Lassen Sie uns auf der erweiterten Klasse aussehen Nun } Es hat ein Feld Nun ist die nette Sache ist, wenn wir den Überblick über den Umfang halten, wollen wir müssen mehr Arbeit nicht tun, dass viel. Ich definiert eine und jetzt brauchen wir nur noch einmal unsere abstrakte Klasse erweitern Wir haben eine variable Als Referenz hier ist der vollständige Code von Wie auch immer, das ist meine Beschreibung des Algorithmus. Ich denke, es ist schön, weil esgenau, und es gibt nicht wirklich, dass viele Fälle zu überprüfen. Code
public class Circle {
final Point2D center;
final double radius;
public Circle(double x, double y, double radius) {
center = new Point2D.Double(x, y);
this.radius = radius;
}
public Circle(Point2D.Double center, double radius) {
this(center.getX(), center.getY(), radius);
}
public Point2D getCenter() {
return new Point2D.Double(getCenterX(), getCenterY());
}
public double getCenterX() {
return center.getX();
}
public double getCenterY() {
return center.getY();
}
public double getRadius() {
return radius;
}
}
Shape Klasse. Shapes hat eine PathIterator, die ich verwenden kann, durch die Kanten des Polygons iterieren. T über unsere Polygon Kreis Kreuzung berechnet. public abstract class CircleShapeIntersectionFinder<T> { private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
}
private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
}
static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
}
Circle, die nur eine Kopie des Kreises hält, und die currentSquareRadius, die eine Kopie des quadratischen Radius hält. Dies mag seltsam erscheinen, aber die Klasse verwende ich tatsächlich ausgestattet, die Bereiche einer ganzen Sammlung von Kreis-Polygon-Kreuzungen zu finden. Deshalb habe ich mich auf einen der Kreise als „aktuell“. private Circle currentCircle;
private double currentSquareRadius;
public final T computeValue(Circle circle, Shape shape) {
initialize();
processCircleShape(circle, shape);
return getValue();
}
initialize() und getValue() sind abstrakt. initialize() würde die Variable, die insgesamt der Bereich auf Null zu halten, und getValue() würde nur den Bereich zurück. Die Definition für processCircleShape ist private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
initializeForNewCirclePrivate(circle);
if (cellBoundaryPolygon == null) {
return;
}
PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
double[] firstVertex = new double[2];
double[] oldVertex = new double[2];
double[] newVertex = new double[2];
int segmentType = boundaryPathIterator.currentSegment(firstVertex);
if (segmentType != PathIterator.SEG_MOVETO) {
throw new AssertionError();
}
System.arraycopy(firstVertex, 0, newVertex, 0, 2);
boundaryPathIterator.next();
System.arraycopy(newVertex, 0, oldVertex, 0, 2);
segmentType = boundaryPathIterator.currentSegment(newVertex);
while (segmentType != PathIterator.SEG_CLOSE) {
processSegment(oldVertex, newVertex);
boundaryPathIterator.next();
System.arraycopy(newVertex, 0, oldVertex, 0, 2);
segmentType = boundaryPathIterator.currentSegment(newVertex);
}
processSegment(newVertex, firstVertex);
}
initializeForNewCirclePrivate zu suchen. Diese Methode nur setzt die Instanzfelder und ermöglicht die abgeleitete Klasse jede Eigenschaft des Kreises zu speichern. Seine Definition ist private void initializeForNewCirclePrivate(Circle circle) {
currentCircle = circle;
currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
initializeForNewCircle(circle);
}
initializeForNewCircle ist abstrakt und eine Implementierung wäre für die Kreise Radius speichern zu vermeiden, Quadratwurzeln zu tun. Wie auch immer wieder processCircleShape. Nach initializeForNewCirclePrivate rufen, überprüfen wir, ob das Polygon null (die ich als ein leeres Polygon bin Interpretation), und wir zurück, wenn es null ist. In diesem Fall würde unsere berechnete Fläche gleich Null sein. Wenn das Polygon nicht ist null dann erhalten wir die PathIterator des Polygons. Das Argument für die getPathIterator Methode I nennen, ist eine affine Transformation, die auf den Weg angewendet werden können. Ich will nicht beantragen, obwohl, so gebe ich null nur. double[]s die Spur der Eckpunkte halten. Ich muß den ersten Eckpunkt erinnern, weil die PathIterator mir nur einmal jede Ecke gibt, also muß ich zurückgehen, nachdem sie mir die letzte Ecke gegeben hat, und mit diesem letzten Scheitelpunkt und dem ersten Scheitelpunkt eine Kante bilden. currentSegment Methode in der nächsten Zeile setzt den nächsten Scheitelpunkt in seinem Argument. Es gibt einen Code, der Ihnen sagt, wenn er aus Eckpunkten ist. Deshalb ist der Steuerausdruck für meine while-Schleife ist, was es ist. processSegment und dann nenne ich processSegment wieder am Ende des Verfahrens die Kanten zu verarbeiten, die die letzte Ecke mit dem ersten Scheitelpunkt verbunden ist. processSegment Werfen wir einen Blick: private void processSegment(double[] initialVertex, double[] finalVertex) {
double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
return;
}
double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
final double rightX = leftX + segmentLength;
final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
processSegmentStandardGeometry(leftX, rightX, y);
}
segmentDisplacement I, wobei die Verschiebung von dem Anfangsscheitelpunkt zu dem endgültigen Scheitelpunkt. Dies definiert die x-Achse des Standard geometry. Ich habe eine baldige Rückkehr, wenn diese Verschiebung gleich Null ist. segmentDisplacement gibt mir leftX, die ich hatte xi angerufen. Dann rightX, die ich hatte xf angerufen, nur leftX + segmentLength. Schließlich habe ich den Keil Produkt y zu erhalten, wie oben beschrieben. processSegmentStandardGeometry Verfahren der Fall ist. Schauen wir uns den Code aussehen private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
if (y * y > getCurrentSquareRadius()) {
processNonIntersectingRegion(leftX, rightX, y);
} else {
final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
if (leftX < -intersectionX) {
final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
}
if (intersectionX < rightX) {
final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
}
final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
processIntersectingRegion(middleRegionLength, y);
}
}
if unterscheidet die Fälle, in denen y klein genug ist, dass der Rand des Kreises schneiden. Wenn y groß ist, und es gibt keine Möglichkeit der Kreuzung, dann rufe ich die Methode, diesen Fall zu behandeln. Ansonsten behandeln ich den Fall, in dem Schnittpunkt möglich ist. intersectionX und I teilen den Rand in drei Abschnitte, die Bereichen entsprechen 1, 2 und 3 der Standardgeometrie obigen Abbildung. Zuerst habe ich Griff Region 1. leftX in der Tat weniger als -intersectionX sonst dort 1. keine Region wäre, wenn es eine Region 1 ist, dann muß ich wissen, wann es endet. Es endet mit dem Minimum von rightX und -intersectionX. Nachdem ich diese x-Koordinaten gefunden habe, beschäftige ich mich mit diesem Nicht-Kreuzungsbereich. leftX und rightX überprüfen Sie tatsächlich etwas Region zwischen -intersectionX und intersectionX umklammern. Nachdem die Region zu finden, ich brauche nur die Länge der Region und y, so gebe ich diese beiden Zahlen auf eine abstrakte Methode, die die Region 2 behandelt. processNonIntersectingRegion Betrachten Sie nun private void processNonIntersectingRegion(double leftX, double rightX, double y) {
final double initialTheta = Math.atan2(y, leftX);
final double finalTheta = Math.atan2(y, rightX);
double deltaTheta = finalTheta - initialTheta;
if (deltaTheta < -Math.PI) {
deltaTheta += 2 * Math.PI;
} else if (deltaTheta > Math.PI) {
deltaTheta -= 2 * Math.PI;
}
processNonIntersectingRegion(deltaTheta);
}
atan2 verwenden, um die Winkeldifferenz zwischen leftX und rightX zu berechnen. Dann füge ich Code mit der Diskontinuität in atan2 zu behandeln, aber das ist wahrscheinlich nicht notwendig, weil die Unterbrechung entweder bei 180 Grad oder 0 Grad auftritt. Dann gebe ich den Unterschied in Winkeln auf eine abstrakte Methode. Schließlich haben wir nur abstrakte Methoden und Getter: protected abstract void initialize();
protected abstract void initializeForNewCircle(Circle circle);
protected abstract void processNonIntersectingRegion(double deltaTheta);
protected abstract void processIntersectingRegion(double length, double y);
protected abstract T getValue();
protected final Circle getCurrentCircle() {
return currentCircle;
}
protected final double getCurrentSquareRadius() {
return currentSquareRadius;
}
}
CircleAreaFinder public class CircleAreaFinder extends CircleShapeIntersectionFinder<Double> {
public static double findAreaOfCircle(Circle circle, Shape shape) {
CircleAreaFinder circleAreaFinder = new CircleAreaFinder();
return circleAreaFinder.computeValue(circle, shape);
}
double area;
@Override
protected void initialize() {
area = 0;
}
@Override
protected void processNonIntersectingRegion(double deltaTheta) {
area += getCurrentSquareRadius() * deltaTheta / 2;
}
@Override
protected void processIntersectingRegion(double length, double y) {
area -= length * y / 2;
}
@Override
protected Double getValue() {
return area;
}
@Override
protected void initializeForNewCircle(Circle circle) {
}
area Spur des Bereichs zu halten. initialize setzt Fläche auf Null, wie erwartet. Wenn wir eine nicht schneidende Kante verarbeitet, inkrementieren wir den Bereich, der durch R ^ 2 Δθ / 2, wie wir uns oben geschlossen sein sollten. Für eine schneidende Kante, dekrementieren wir den Bereich von y*length/2. Das war so, dass negative Werte für y zu positiven Flächen entsprechen, als wir beschlossen, sie sollten. AreaPerimeter Klasse: public class AreaPerimeter {
final double area;
final double perimeter;
public AreaPerimeter(double area, double perimeter) {
this.area = area;
this.perimeter = perimeter;
}
public double getArea() {
return area;
}
public double getPerimeter() {
return perimeter;
}
}
AreaPerimeter als Typen verwendet wird. public class CircleAreaPerimeterFinder extends CircleShapeIntersectionFinder<AreaPerimeter> {
public static AreaPerimeter findAreaPerimeterOfCircle(Circle circle, Shape shape) {
CircleAreaPerimeterFinder circleAreaPerimeterFinder = new CircleAreaPerimeterFinder();
return circleAreaPerimeterFinder.computeValue(circle, shape);
}
double perimeter;
double radius;
CircleAreaFinder circleAreaFinder;
@Override
protected void initialize() {
perimeter = 0;
circleAreaFinder = new CircleAreaFinder();
}
@Override
protected void initializeForNewCircle(Circle circle) {
radius = Math.sqrt(getCurrentSquareRadius());
}
@Override
protected void processNonIntersectingRegion(double deltaTheta) {
perimeter += deltaTheta * radius;
circleAreaFinder.processNonIntersectingRegion(deltaTheta);
}
@Override
protected void processIntersectingRegion(double length, double y) {
perimeter += Math.abs(length);
circleAreaFinder.processIntersectingRegion(length, y);
}
@Override
protected AreaPerimeter getValue() {
return new AreaPerimeter(circleAreaFinder.getValue(), perimeter);
}
}
perimeter Spur des Umfangs zu halten, erinnern wir uns, den Wert des radius Math.sqrt eine Menge rufen zu vermeiden, und wir die Berechnung der Fläche in unseren CircleAreaFinder delegieren. Wir können sehen, dass die Formeln für den Umfang sind einfach. CircleShapeIntersectionFinder private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
}
private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
}
static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
}
private Circle currentCircle;
private double currentSquareRadius;
public final T computeValue(Circle circle, Shape shape) {
initialize();
processCircleShape(circle, shape);
return getValue();
}
private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
initializeForNewCirclePrivate(circle);
if (cellBoundaryPolygon == null) {
return;
}
PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
double[] firstVertex = new double[2];
double[] oldVertex = new double[2];
double[] newVertex = new double[2];
int segmentType = boundaryPathIterator.currentSegment(firstVertex);
if (segmentType != PathIterator.SEG_MOVETO) {
throw new AssertionError();
}
System.arraycopy(firstVertex, 0, newVertex, 0, 2);
boundaryPathIterator.next();
System.arraycopy(newVertex, 0, oldVertex, 0, 2);
segmentType = boundaryPathIterator.currentSegment(newVertex);
while (segmentType != PathIterator.SEG_CLOSE) {
processSegment(oldVertex, newVertex);
boundaryPathIterator.next();
System.arraycopy(newVertex, 0, oldVertex, 0, 2);
segmentType = boundaryPathIterator.currentSegment(newVertex);
}
processSegment(newVertex, firstVertex);
}
private void initializeForNewCirclePrivate(Circle circle) {
currentCircle = circle;
currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
initializeForNewCircle(circle);
}
private void processSegment(double[] initialVertex, double[] finalVertex) {
double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
return;
}
double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
final double rightX = leftX + segmentLength;
final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
processSegmentStandardGeometry(leftX, rightX, y);
}
private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
if (y * y > getCurrentSquareRadius()) {
processNonIntersectingRegion(leftX, rightX, y);
} else {
final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
if (leftX < -intersectionX) {
final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
}
if (intersectionX < rightX) {
final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
}
final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
processIntersectingRegion(middleRegionLength, y);
}
}
private void processNonIntersectingRegion(double leftX, double rightX, double y) {
final double initialTheta = Math.atan2(y, leftX);
final double finalTheta = Math.atan2(y, rightX);
double deltaTheta = finalTheta - initialTheta;
if (deltaTheta < -Math.PI) {
deltaTheta += 2 * Math.PI;
} else if (deltaTheta > Math.PI) {
deltaTheta -= 2 * Math.PI;
}
processNonIntersectingRegion(deltaTheta);
}
protected abstract void initialize();
protected abstract void initializeForNewCircle(Circle circle);
protected abstract void processNonIntersectingRegion(double deltaTheta);
protected abstract void processIntersectingRegion(double length, double y);
protected abstract T getValue();
protected final Circle getCurrentCircle() {
return currentCircle;
}
protected final double getCurrentSquareRadius() {
return currentSquareRadius;
}
Ich bin fast ein Jahr und eine Hälfte zu spät, aber ich dachte, vielleicht Menschen in
Unter der Annahme, Sie sprechen integer Pixel, nicht real, die naive Implementierung einer Schleife durch jedes Pixel des Dreiecks sein würde, und prüfen Sie den Abstand von dem Mittelpunkt des Kreises gegen seinen Radius. Es ist nicht eine nette Formel oder besonders schnell, aber es macht den Job zu erledigen.
Hinweis: Dies ist kein triviales Problem, ich hoffe, es ist nicht Hausaufgaben; -)
Wenn Sie eine GPU zur Verfügung haben, können Sie diese Technik für eine Pixelanzahl der Kreuzung zu erhalten ..
Ich denke, man solle nicht angenäherten Kreis als eine Reihe von Dreiecken, statt dass Sie nähern es ist Form mit einem Polygon. Der naive Algorithmus kann wie folgt aussehen:
- Konvertieren Sie mit einer gewünschten Anzahl von Eckpunkten Kreis Polygon.
- Berechne den Schnittpunkt zweier Polygone (konvertierte Kreis und ein Dreieck).
- Berechnen Quadrat dieser Kreuzung.
Sie können diesen Algorithmus optimieren, indem die Schritte 2 und 3 in einzelne Funktion kombiniert werden.
Lesen Sie diese Links:
Fläche von konvexen Polygon
Überschneidung von konvexen Polygonen
Da Ihre Formen konvex sind, können Sie Monte Carlo Bereich Schätzung verwendet werden.
Zeichnen Sie ein Feld um den Kreis und Dreieck.
Wählen Sie beliebige Punkte in der Box und halten eine zu zählen, wie viele fallen in den Kreis, und wie viele fallen sowohl im Kreis und Dreieck.
Schnittbereich ≅ Fläche des Kreises * # Punkte in Kreis und Dreieck / # Punkte im Kreis
Haltepunkte wählen, wenn die geschätzte Fläche von mehr ändert sich nicht als einen bestimmten Betrag über eine bestimmte Anzahl von Runden, oder einfach nur eine feste Anzahl von Punkten basierend auf dem Bereich der Box wählen. Der Bereich Schätzung sollte ziemlich schnell konvergieren, wenn man nicht von Ihren Formen sehr wenig Fläche hat.
Hinweis: Hier ist, wie Sie bestimmen, ob ein Punkt in einem Dreieck ist: Baryzentrische Koordinaten
Wie genau müssen Sie sein? Wenn Sie den Kreis mit einfacheren Formen annähern können, können Sie das Problem vereinfachen. Es wäre nicht schwer, einen Kreis als eine Reihe von sehr schmalen Dreiecken in der Mitte treffen zu modellieren, zum Beispiel.
Wenn nur einer der Liniensegmente des Dreiecks den Kreis schneidet, ist die reine mathematische Lösung nicht zu hart. Sobald Sie wissen, wenn die beiden Schnittpunkte sind, können Sie die Abstandsformel verwenden, um die Sehnenlänge zu finden.
Nach diese Gleichungen :
ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))
, wobei C die Sehnenlänge ist, r der Radius, θ der Winkel wird durch das Zentrum, und A die Fläche. Beachten Sie, dass diese Lösung bricht, wenn mehr als die Hälfte der Kreis abgeschnitten wird.
Es ist wahrscheinlich nicht der Mühe wert, wenn Sie nur eine Annäherung benötigen, da es mehrere Annahmen über macht, was die eigentliche Kreuzung aussieht.
Mein erster Instinkt wäre alles zu transformieren, so dass der Kreis auf Herkunft, trans das Dreieck in Polarkoordinaten zentriert ist, und für den Schnittpunkt (oder encompassment) des Dreiecks mit dem Kreis lösen. Ich habe nicht funktioniert es eigentlich noch auf dem Papier durch, obwohl, so dass nur eine Vermutung.
