Berechnen Sie den Schnittbereich zwischen einem Kreis und einem Dreieck?

Zuerst will ich uns daran erinnern, wie man die Fläche eines Polygons. Sobald wir dies getan haben, ist der Algorithmus zum finden der Schnittmenge zwischen einem polygon und einem Kreis sollte leicht zu verstehen.

Wie finden Sie die Fläche eines Polygons

Betrachten wir den Fall eines Dreiecks, da alle wesentlichen Logik erscheint es. Nehmen wir an wir haben ein Dreieck mit den Eckpunkten (x1,y1), (x2,y2), (x3,y3) wie gehen Sie um das Dreieck gegen den Uhrzeigersinn, wie in der folgenden Abbildung dargestellt:

Dann können Sie berechnen Sie die Fläche, die durch die Formel

A=(x1 y2 + x2 y3 + x3 y1 - x2y1 - x3 y2 - x1y3)/2.

Zu sehen, warum diese Formel funktioniert, lassen Sie uns zu verschieben, so ist es in der form

A=(x1 y2 - x2 y1)/2 + (x2 y3 - x3 y2)/2 + (x3 y1 - x1y3 )/2.

Nun der erste Begriff ist die folgende Fläche, die positiv in unserem Fall:

Wenn es ist nicht klar, dass die Gegend der grünen region ist in der Tat (x1 y2 - x2 y1)/2, dann Lesen Sie diese.

Der zweite Begriff ist das Gebiet, das ist wieder positiv:

Und der Dritte Bereich ist in der folgenden Abbildung dargestellt. Diese Zeit, die Fläche ist negativ

Hinzufügen dieser drei oben erhalten wir das folgende Bild

Sehen wir, dass der grüne Bereich wurde außerhalb des Dreiecks ist die Kündigung durch den roten Bereich, so dass die Netto-Fläche wird nur die Fläche eines Dreiecks, und dies zeigt, warum unsere Formel war in diesem Fall true.

Was ich oben sagte war die intuitive Erklärung, warum der Bereich Formel korrekt war. Eine genauere Erklärung wäre zu beachten, dass bei der Berechnung der Fläche von einer Kante, dem Gebiet, das wir bekommen, ist der gleiche Bereich, den wir erhalten würden, die sich aus der integration von r^2dθ/2, so haben wir effektiv die Integration von r^2dθ/2 um die Grenze des Polygons, und durch die stokes-theorem, das gibt das gleiche Ergebnis wie die Integration rdrdθ über die region begrenzt das polygon. Da die Integration rdrdθ über die region begrenzt durch die polygon gibt den Bereich, schließen wir, dass unser Verfahren müssen richtig geben der Gegend.

Bereich des Schnittpunktes eines Kreises mit einem polygon

Lassen Sie uns jetzt besprechen, wie es um den Bereich zu finden der den Schnittpunkt von einem Kreis mit radius R mit einem polygon, wie in der folgenden Abbildung:

Wir sind daran interessiert, finden Sie den Bereich der grünen region. Wir können, genau wie im Fall des einzigen polygon, brechen unsere Berechnung in der Suche nach einer Fläche für jede Seite des Polygons, und fügen Sie dann diese Bereiche.

Unsere erste Bereich wird wie folgt Aussehen:

Den zweiten Bereich Aussehen wird

Und der Dritte Bereich wird

Wieder, die ersten zwei Bereiche sind positiv, in unserem Fall, während die Dritte negativ sein wird. Hoffentlich werden die Stornierungen wird die Arbeit aus, so dass die Netto-Fläche ist in der Tat das Gebiet, in dem wir interessiert sind. Mal sehen.

In der Tat die Summe der Bereiche wird ein Bereich, den wir interessiert sind.

Wieder, die wir geben können, eine genauere Erklärung, warum das funktioniert. Lassen ich der region, definiert durch den Schnittpunkt und sei P das polygon. Dann aus der bisherigen Diskussion wissen wir, dass wir wollen, dass computer das integral von r^2dθ/2 entlang der Grenze des I. dies Jedoch schwer zu tun, weil es erfordert die Suche nach der Schnittmenge.

Stattdessen haben wir ein integral über das polygon. Wir integrierten max(r,R)^2 dθ/2 über die Grenze des Polygons. Um zu sehen, warum dies gibt die richtige Antwort, definieren wir eine Funktion π, die einen Punkt in Polarkoordinaten (r,θ) auf den Punkt (max(r,R),θ). Es sollte nicht verwirrend sein, zu finden, die die Koordinaten-Funktionen von π(r)=max(r,R) und π(θ)=θ. Dann, was wir Taten, war, sich zu integrieren π(r)^2 dθ/2 über die Grenze des Polygons.

Auf der anderen Seite, da π(θ)=θ, dies ist die gleiche wie die Integration von π(r)^2 dn(θ)/2 über die Grenze des Polygons.

Wird jetzt eine änderung der Variablen, finden wir, dass wir die gleiche Antwort erhalten, wenn wir integrierte r^2 dθ/2 über die Begrenzung von π(P), wobei π(P) ist das Bild von P unter π.

Mithilfe der Stokes-theorem noch einmal, wir wissen, dass die Integration von r^2 dθ/2 über die Begrenzung von π(P) gibt uns die Umgebung von π(P). In anderen Worten, es gibt die gleiche Antwort wie die Integration dxdy über π(P).

Durch eine änderung von Variablen wieder, die wir wissen, dass Integration dxdy über π(P) ist das gleiche wie Integration Jdxdy über P, wo J ist die Jacobi-π.

Nun wir teilen das integral der Jdxdy in zwei Bereiche: der Teil in der Kreis-und der Teil außerhalb des Kreises. Nun π lässt Punkte in den Kreis allein, so dass J=1 gibt, so dass der Beitrag von diesem Teil von P ist der Bereich, der Teil von P, der sich in den Kreis, d.h., der Bereich von der Kreuzung. Die zweite region ist die region außerhalb des Kreises. Es J=0, da π kollabiert dieses Teil nach unten, auf die Grenze des Kreises.

So, was wir berechnen, ist in der Tat der Bereich der Kreuzung.

Nun, wir sind relativ sicher, dass wir wissen, konzeptionell wie um den Bereich zu finden, sprechen wir genauer darüber, wie die Berechnung des Beitrags von einem einzigen segment. Lassen Sie uns beginnen, indem Sie sich ein segment in dem, was ich nennen das "standard-geometrie". Es ist unten dargestellt.

In standard-geometrie, die Kante geht horizontal von Links nach rechts. Es ist beschrieben durch drei zahlen: xi, x-Koordinate, wo der Rand beginnt, xf, x-Koordinate, wo der Rand endet, und y, der y-Koordinate der Kante.

Nun sehen wir, dass falls |y| < R, wie in der Abbildung, dann die Kante schneidet den Kreis in den Punkten (-xint,y) und (xint,y), wo xint = (R^2-y^2)^(1/2). Dann den Bereich, den wir brauchen, um zu berechnen, aufgeteilt in drei Stücke gekennzeichnet in der Abbildung. Um die Gebiete der Regionen 1 und 3, die wir verwenden können, arctan, um die Winkel der verschiedenen Punkte und dann gleichsetzen, der Bereich R^2 Δθ/2. So zum Beispiel würden wir θi = atan2(y,xi) und θl = atan2(y,-xint). Dann wird die Fläche der region ist R^2 (θl-θi)/2. Wir erhalten das Gebiet der region 3 ähnlich.

Bereich der region 2 ist die Fläche eines Dreiecks. Jedoch, wir müssen vorsichtig sein, über Zeichen. Wir wollen uns die Gegend gezeigt, positiv zu sein, so werden wir sagen, das Gebiet ist -(xint - (-xint))y/2.

Andere Sache im Auge zu behalten ist, dass, im Allgemeinen, xi-nicht weniger als-xint und xf nicht größer sein, als xint.

Den anderen Fall zu betrachten ist |y| > R. in Diesem Fall ist einfacher, denn es gibt nur ein Stück, das ähnlich wie in region 1 in der Abbildung.

Nun, dass wir wissen, wie zur Berechnung der Fläche von einer Kante in standard-geometrie, die einzige Sache Links zu tun ist, beschreiben Sie, wie Sie verwandeln jede Kante in standard-geometrie.

Aber dies nur eine einfache änderung der Koordinaten. Da einige mit den ersten Eckpunkt vi und final vertex vf, die neue x-TEN Einheitsvektor wird das Gerät zeigenden Vektor von vi zu vf. Dann ist xi ist nur die Verschiebung des vi aus der Mitte des Kreises, gepunktet in x-und xf ist nur xi plus die Distanz zwischen vi und vf. Unterdessen y ist gegeben durch das wedge-Produkt von x mit der Verschiebung von vi aus der Mitte des Kreises.

Code

Das vervollständigt die Beschreibung des Algorithmus, nun ist es Zeit, code zu schreiben. Ich verwende java.

First off, da wir mit Kreisen, wir sollten einen Kreis Klasse

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;
    }

}

Für Polygone, verwende ich java Shape Klasse. Shapes haben eine PathIterator dass ich verwenden können, um zu Durchlaufen und die Kanten des Polygons.

Nun für die eigentliche Arbeit. Ich werde trennen Sie die Logik des Durchlaufens der Kanten, setzen die Kanten in standard-geometrie etc, aus der Logik des computing der Bereich sobald dies geschehen ist. Der Grund dafür ist, dass Sie möglicherweise in der Zukunft berechnen möchten, etwas anderes neben oder zusätzlich zu Bereich und Sie wollen in der Lage sein, den code wiederverwenden zu müssen, befassen sich mit Durchlaufen der Kanten.

So habe ich eine generische Klasse, die berechnet werden, eine Eigenschaft der Klasse T über unsere polygon-Kreis-Schnittpunkt.

public abstract class CircleShapeIntersectionFinder<T> {

Es hat drei statische Methoden, die nur helfen, berechnen geometrie:

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];
}

Gibt es zwei Instanz-Felder, ein Circle die einfach immer eine Kopie der Kreis, und die currentSquareRadius hält eine Kopie von dem Quadrat des radius. Das mag jetzt seltsam klingen, aber die Klasse die ich verwende, ist eigentlich ausgestattet, um die Bereiche der eine ganze Sammlung von Kreis-polygon-Schnittpunkte. Deshalb beziehe ich mich auf einen der Kreise, die als "aktuell".

private Circle currentCircle;
private double currentSquareRadius;

Weiter geht die Methode für die Berechnung, was wir ausrechnen wollen:

public final T computeValue(Circle circle, Shape shape) {
    initialize();
    processCircleShape(circle, shape);
    return getValue();
}

initialize() und getValue() sind Abstrakt. initialize() würde die variable setzen, die insgesamt die Fläche auf null, und getValue() würde nur wieder das Gebiet. 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);
}

Werfen wir einen zweiten Blick auf initializeForNewCirclePrivate schnell. Diese Methode stellt nur die Instanz-Felder und ermöglicht es der abgeleiteten Klasse speichern keine Eigenschaft des Kreises. Seine definition ist

private void initializeForNewCirclePrivate(Circle circle) {
    currentCircle = circle;
    currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
    initializeForNewCircle(circle);
}

initializeForNewCircle ist Abstrakt und eine Umsetzung wäre für Sie zum speichern der Kreise radius zu vermeiden Quadratwurzeln. Eh wieder processCircleShape. Nach dem Aufruf initializeForNewCirclePrivate überprüfen wir, ob das polygon null (was ich interpretieren als ein leeres polygon), und wir kehren zurück, wenn es null. In diesem Fall ist der berechnete Bereich wäre null. Wenn das polygon nicht null dann erhalten wir die PathIterator des Polygons. Das argument der getPathIterator Methode, die ich nennen ist eine affine transformation, die angewendet werden können, um den Pfad. Ich will nicht zu bewerben, obwohl, so dass ich nur weitergeben null.

Nächstes erkläre ich den double[]s, die wird verfolgen die Eckpunkte. Ich muss daran denken, den ersten Eckpunkt, weil die PathIterator nur gibt mir jede Kante einmal, also ich habe zurück zu gehen, nachdem es mir das Letzte Scheitelpunkt, und bilden eine Kante mit diesem letzten Eckpunkt und dem ersten.

Den currentSegment Methode in der nächsten Zeile setzt den nächsten Eckpunkt in seiner Argumentation. Es gibt einen code, der Ihnen mitteilt, wenn es außerhalb der Scheitelpunkte. Dies ist der Grund, warum die Kontrolle Ausdruck für meine while-Schleife ist, was es ist.

Meisten der rest der code dieser Methode ist uninteressant Logik bezogen auf das Durchlaufen der Eckpunkte. Das wichtigste ist, dass einmal pro iteration der while-Schleife rufe ich processSegment und dann rufe ich processSegment wieder am Ende der Methode zur Verarbeitung des Kante verbindet, dass Sie den letzten Eckpunkt zu den ersten vertex.

Schauen wir uns den code für processSegment:

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);
}

In dieser Methode implementiere ich die Schritte, die zur Transformation einer Kante in der standard-geometrie, wie oben beschrieben. Zuerst berechne ich segmentDisplacement die Verschiebung von der ersten Ecke der abschließenden vertex. Dies definiert die x-Achse in der standard-geometrie. Ich mache eine baldige Rückkehr, wenn diese Verschiebung ist null.

Nächstes berechne ich die Länge der Verschiebung an, da diese notwendig ist, um den x-TEN Einheitsvektor. Sobald ich diese Informationen haben, berechne ich die Verschiebung aus der Mitte des Kreises, um den ersten Eckpunkt. Das Skalarprodukt dieser mit segmentDisplacement gibt mir leftX die ich hatte, wurden rufe xi. Dann rightX, die ich hatte, wurden rufe xf, ist nur leftX + segmentLength. Schließlich mache ich das wedge-Produkt zu bekommen y wie oben beschrieben.

Nun, dass ich umgewandelt haben, das problem in der standard-geometrie, wird es leicht sein, Angebot mit. Das ist das, was die processSegmentStandardGeometry Methode. Schauen wir uns den code

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);
    }
}

Den ersten if unterscheidet die Fälle, in denen y ist klein genug, dass der Rand möglicherweise schneiden Sie den Kreis. Wenn y ist groß und es gibt keine Möglichkeit der Kreuzung, dann rufe ich die Methode zu behandeln, der Fall. Ansonsten habe ich den Fall behandeln, wo die Kreuzung ist möglich.

Wenn Kreuzung ist möglich, ich berechne die x-Koordinate der Schnittpunkt intersectionX, und ich Teile die Kante in drei Teile, die den Regionen 1, 2 und 3 der standard-geometrie Abbildung oben. Ersten ich handle region 1.

Verarbeiten region 1, ich überprüfen, ob leftX ist in der Tat weniger als -intersectionX denn sonst würde es keine region 1. Wenn es eine region-1 -, dann muss ich wissen, Wann es endet. Es endet mit dem minimum von rightX und -intersectionX. Nachdem ich diese gefunden haben x-Koordinaten, beschäftige ich mich mit diesem non-intersection region.

Ich nicht eine ähnliche Sache zu behandeln, die region 3.

Für region 2, ich habe zu tun, etwas Logik, um zu überprüfen, dass leftX und rightX wirklich Halterung einer region zwischen -intersectionX und intersectionX. Nach der Feststellung der region, ich brauche nur die Länge der region und y, so dass ich übergeben Sie diese zwei zahlen auf einer abstrakten Methode, die Griffe der region 2.

Nun schauen wir uns den code für processNonIntersectingRegion

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);
}

Ich einfach verwenden atan2 zur Berechnung der Differenz im Winkel zwischen leftX und rightX. Dann ich fügen Sie code hinzu, den Umgang mit der Diskontinuität in atan2, aber dies ist wahrscheinlich unnötig, weil die Diskontinuität tritt auf, entweder bei 180 Grad oder 0 Grad. Dann gebe ich den Unterschied im Winkel auf einer abstrakten Methode. Schließlich, wir haben 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;
    }

}

Schauen wir uns jetzt an die Verlängerung der Klasse 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) {

}

}

Es hat ein Feld area zu verfolgen, das Gebiet. initialize sets-Bereich auf null, wie erwartet. Wenn wir eine nicht schneidende Kante, erhöhen wir den Bereich von R^2 Δθ/2 als wir zu dem Schluss wir sollten oben. Für eine schneidende Kante, wir Dekrementieren der Gegend von y*length/2. Das war so, dass negative Werte für y entsprechen positiven Bereiche, als wir beschlossen Sie sollte.

Nun ist die saubere Sache ist, wenn wir wollen, zu verfolgen, den Umfang, die wir nicht zu tun haben, dass viel mehr Arbeit. Für mich ein 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;
    }

}

und jetzt brauchen wir nur noch verlängern unsere abstrakte Klasse wieder mit AreaPerimeter als der Typ.

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);
    }

}

Haben wir eine variable perimeter zu verfolgen, den Umfang, wir erinnern uns an den Wert der radius zu vermeiden, rufen Sie Math.sqrt eine Menge, und wir delegieren die Berechnung der Fläche, um unsere CircleAreaFinder. Wir können sehen, dass die Formeln für den Umfang sind einfach.

Referenz hier ist der vollständige code der 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;
    }

Sowieso, das ist meine Beschreibung des Algorithmus. Ich denke, es ist schön, weil es genau ist und es sind nicht wirklich viele Fälle zu prüfen.

InformationsquelleAutor der Antwort Brian Moths

Vorausgesetzt, Sie reden integer-Pixel, die nicht real, die naive Implementierung würde, um eine Schleife durch jedes pixel des Dreiecks und prüfen Sie den Abstand von der Mitte des Kreises gegen seinen radius.

Ist es nicht eine nette Formel, oder besonders schnell, aber es tut den job zu erledigen.

InformationsquelleAutor der Antwort lc.

Wenn Sie eine GPU zur Verfügung, die Sie nutzen könnten diese Technik für den Erhalt einer Pixelzahl von der Kreuzung..

InformationsquelleAutor der Antwort codelogic

Da Ihre Formen, die konvex sind, können Sie mithilfe der Monte-Carlo-area-Schätzung.

Zeichnen Sie ein Rechteck um den Kreis und das Dreieck.

Wählen Sie zufällige Punkte in der box und halten Sie zählen, wie viele fallen in den Kreis, und wie viele fallen in den Kreis und das Dreieck.

Bereich der Kreuzung ≅ Gebiet von Kreis * # Punkte im Kreis und im Dreieck /# Punkte im Kreis

Stoppen der Auswahl Punkten, wenn die geschätzte Fläche ändert sich nicht durch mehr als einen bestimmten Betrag über eine bestimmte Anzahl von Runden, oder wählen Sie einfach eine Feste Anzahl von Punkten auf die Fläche der box. Der Bereich schätzen sollten konvergieren Recht schnell, es sei denn, eine Ihrer Formen, hat sehr wenig Fläche.

Hinweis: Hier ist, wie Sie bestimmen, ob ein Punkt in einem Dreieck: Barycentric coordinates

InformationsquelleAutor der Antwort Imran

Wenn nur eine der Dreiecks-Linie Segmente schneidet der Kreis, die rein mathematische Lösung ist nicht allzu schwer. Sobald Sie wissen, Wann die beiden Schnittpunkte sind, können Sie den Abstand Formel zu finden, die Sehnenlänge.

Laut diese Gleichungen:

ϑ = 2 sin⁻¹(0.5 c /r)
A = 0.5 r² (ϑ - sin(ϑ))

wobei c die Sehnenlänge, r der radius, ϑ wird der Winkel durch die Mitte, und A ist die Fläche. Beachten Sie, dass diese Lösung bricht, wenn mehr als die Hälfte der Kreis abgeschnitten wird.

Ist es wahrscheinlich nicht der Mühe Wert, wenn Sie nur eine Annäherung, denn es macht einige Annahmen über das, was die eigentliche Kreuzung aussieht.

InformationsquelleAutor der Antwort Nikhil Chelliah