je vais d'Abord vous nous rappeler comment trouver l'aire d'un polygone. Une fois que nous l'avons fait, l'algorithme pour trouver l'intersection entre un polygone ou un cercle doit être facile à comprendre.

comment trouver la zone d'un polygone

regardons le cas d'un triangle, parce que l'essentiel de la logique apparaît. Supposons que nous ayons un triangle avec des sommets (x1, y1), (x2, y2), et (x3,y3) alors que vous contournez le triangle dans le sens inverse des aiguilles d'une montre., comme le montre la figure suivante:

alors vous pouvez calculer la zone par la formule

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

pour voir pourquoi cette formule fonctionne, réarrangeons-la comme elle est dans la forme

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

maintenant le premier terme est le domaine suivant, qui est positif dans notre cas:

S'il n'est pas clair que la zone de la région verte est effectivement (x1 y2 - x2 y1)/2, alors lire ce .

le deuxième terme est ce domaine, qui est à nouveau positif:

et la troisième zone est représentée dans la figure suivante. Cette fois, l'aire est négative

en ajoutant ces trois nous obtenons l'image suivante

Nous voyons que l'espace vert qui était à l'extérieur du triangle est annulée par la zone rouge, alors que la zone nette est juste l'aire du triangle, et cela montre pourquoi notre formule est vraie dans ce cas.

ce que j'ai dit ci-dessus était l'explication intuitive quant à la raison pour laquelle la formule de la zone était correcte. Un une explication plus rigoureuse serait d'observer que lorsque nous calculons la zone à partir d'un bord, la zone que nous obtenons est la même zone que nous obtiendrions de l'intégration R^2dθ/2, donc nous intégrons effectivement r^2dθ/2 autour de la limite du polygone, et par le théorème de stokes, cela donne le même résultat que l'intégration rdrdθ sur la région délimitée du polygone. Puisque l'intégration de rdrdθ sur la région délimitée par le polygone donne l'aire, nous concluons que notre procédure doit donner correctement l'aire.

aire de l'intersection d'un cercle avec un polygone

maintenant, nous allons discuter comment trouver la zone de l'intersection d'un cercle de rayon R avec un polygone comme le montre la figure suivante:

nous sommes intéressés à trouver la zone de la région verte. Nous pouvons, tout comme dans le cas du polygone unique briser notre calcul en trouver un espace de chaque côté de le polygone, puis ajouter ces domaines.

Notre première zone sera:

La deuxième zone sera

Et la troisième zone sera

encore une fois, les deux premiers domaines sont positifs dans notre cas tandis que le troisième sera négatif. Si tout va bien les annulations vont fonctionner de sorte que la surface nette est en effet, le domaine qui nous intéresse. Voyons voir.

en effet, la somme des zones sera la zone qui nous intéresse.

encore une fois, nous pouvons donner une explication plus rigoureuse de pourquoi cela fonctionne. Que je sois la région définie par l'intersection et que P soit le polygone. Puis de la discussion précédente, nous savons que nous voulons informatiser l'intégrale de R^2dθ / 2 autour de la limite de I. Cependant, c'est difficile à faire parce qu'il faut trouver l'intersection.

au lieu de cela nous avons fait une intégrale sur le polygone. Nous avons intégré max (r,R)^2 dθ / 2 au-dessus de la limite du polygone. Pour voir pourquoi cela donne la bonne réponse, définissons une fonction π qui prend un point en coordonnées polaires (R, θ) au point (max(r,R), θ). Il ne devrait pas être déroutant de se référer aux fonctions de coordonnées de π(r)=max(r,R) et π(θ)=θ. Ce que nous avons fait ensuite, c'est d'intégrer π(r)^2 dθ/2 sur le limite du polygone.

, d'autre part, puisque π(θ)=θ, c'est le même que l'intégration de π(r)^2 dn(θ)/2 sur le périmètre du polygone.

faisant maintenant un changement de variable, nous trouvons que nous obtiendrions la même réponse si nous intégrions r^2 dθ/2 au-dessus de la limite de π(P), Où π(P) est l'image de P sous π.

en utilisant de nouveau le théorème de Stokes nous savons que l'intégration R^2 dθ / 2 au-dessus de la limite de π(P) nous donne l'aire of π (P). En d'autres termes, il donne la même réponse que l'intégration de dxdy Sur π(P).

en utilisant un changement de variable encore une fois, nous savons que l'intégration de dxdy Sur π(P) est la même que l'intégration de Jdxdy sur P, où J est le Jacobien de π.

maintenant nous pouvons diviser l'intégrale de Jdxdy en deux régions: la partie dans le cercle et la partie en dehors du cercle. Maintenant π laisse des points dans le cercle seul donc J=1 là, donc la contribution de cette partie de P est la zone de la partie de P qui se trouve dans le cercle c'est à dire, l'aire de l'intersection. La deuxième région est la région en dehors du cercle. Il J=0 puisque π s'effondre cette partie jusqu'à la limite du cercle.

ainsi, ce que nous calculons est en effet la zone de l'intersection.

maintenant que nous sommes relativement sûrs que nous savons conceptuellement comment trouver la zone, parlons plus spécifiquement de la façon de calculer la contribution d'un seul segment. Nous allons commencez par regarder un segment dans ce que j'appelle la "géométrie standard". Il est illustré ci-dessous.

en géométrie standard, le bord va horizontalement de gauche à droite. Il est décrit par trois nombres: xi, la coordonnée x où commence le bord, xf, la coordonnée x où finit le bord, et y, la coordonnée y du bord.

maintenant nous voyons que si / y / < R, comme dans la figure, alors le bord coupe le cercle aux points (-xint,y) et (xint,y) où xint = (R^2-y^2)^(1/2). Ensuite, la zone que nous devons calculer est divisée en trois parties étiquetées dans la figure. Pour obtenir les zones des Régions 1 et 3, Nous pouvons utiliser arctan pour obtenir les angles des différents points et ensuite assimiler la zone à R^2 Δθ/2. Ainsi,par exemple, nous définirions θi = atan2(y, xi) et θl = atan2(y,-xint). La zone de la première région est alors R ^ 2 (θl-θi) / 2. Nous pouvons obtenir la zone de la région 3 de la même façon.

La zone de la région 2 est juste l'aire d'un triangle. Cependant, nous devons faire attention au signe. Nous voulons que la zone soit positive donc nous dirons que la zone est -(xint - (-xint))y/2.

une Autre chose à garder à l'esprit est que, en général, xi ne doit pas être inférieur à xint et xf ne doit pas être supérieure à xint.

L'autre cas à considérer est |y| > R. Ce cas est plus simple, car il n'existe qu'une seule pièce qui est similaire Région 1 de la figure.

maintenant que nous savons calculer la zone à partir d'un bord en géométrie standard, la seule chose qui reste à faire est de décrire comment transformer n'importe quel bord en géométrie standard.

mais ce n'est qu'un simple changement de coordonnées. Avec vertex vi initial et vertex final vf, le nouveau vecteur unité x sera le vecteur unité pointant de vi à vf. Alors xi est juste le déplacement de vi du centre du cercle pointillé en x, et xf est juste xi plus la distance entre vi et vf. Pendant ce temps y est donné par le produit de coin de x avec le déplacement de vi du centre du cercle.

Code

Qui complète la description de l'algorithme, il est maintenant temps d'écrire un peu de code. Je vais utiliser java.

tout d'abord, puisque nous travaillons avec des cercles, nous devrions avoir une classe de cercle

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

}

pour les polygones, I utilisera la classe Shape de java. Shape ont un PathIterator que je peux utiliser pour itérer sur les bords du polygone.

Maintenant, pour le travail réel. Je vais séparer la logique d'itération à travers les bords, en mettant les bords dans la géométrie standard, etc, de la logique de calcul de la zone Une fois que cela est fait. La raison en est que vous pouvez à l'avenir vouloir calculer autre chose en dehors ou en plus de la zone et vous voulez être en mesure de réutiliser le code qui doit gérer les itérations à travers les bords.

donc j'ai une classe générique qui calcule une propriété de la classe T à propos de notre intersection avec polygon circle.

public abstract class CircleShapeIntersectionFinder<T> {

il a trois méthodes statiques qui aident juste à calculer la géométrie:

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

il y a deux champs d'instance, un Circle qui garde juste une copie du cercle, et le currentSquareRadius , qui conserve une copie du carré du rayon. Cela peut sembler étrange, mais la classe que j'utilise est en fait équipée pour trouver les zones de toute une série d'intersections cercle-polygone. C'est pourquoi je me réfère à l'un des cercles comme "active".

private Circle currentCircle;
private double currentSquareRadius;

vient Ensuite la méthode pour calculer ce que nous voulons calculer:

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

initialize() et getValue() sont abstraites. initialize() définirait la variable qui maintient une total de la zone à zéro, et getValue() serait tout simplement retourner la zone. La définition de processCircleShape est

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

prenons une seconde pour regarder initializeForNewCirclePrivate rapidement. Cette méthode définit les champs d'instance et permet à la classe dérivée de stocker n'importe quelle propriété du cercle. Sa définition est

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

initializeForNewCircle est abstrait et une implémentation serait qu'il stocke le rayon des cercles pour éviter d'avoir à faire des racines carrées. Revenons à processCircleShape . Après avoir appelé initializeForNewCirclePrivate , nous vérifions si le polygone est null (que j'interprète comme un polygone vide), et nous retournons s'il est null . Dans ce cas, notre superficie calculée serait égale à zéro. Si le polygone n'est pas null alors nous obtenons le PathIterator du polygone. L'argument de la méthode getPathIterator que j'appelle est une transformation affine qui peut être appliquée au chemin. Je ne veux pas en appliquer un, donc je passe null .

ensuite je déclare les double[] s qui garderont la trace des sommets. Je dois me souvenir du premier vertex parce que le PathIterator ne me donne chaque vertex qu'une seule fois, donc je dois y retourner après qu'il m'ait donné le dernier vertex, et former un bord avec ce dernier vertex et le premier vertex.

la méthode currentSegment sur la ligne suivante met le vertex suivant dans son argument. Il renvoie un code qui vous dit quand il est vertex. C'est pourquoi l'expression de contrôle pour ma boucle while Est ce qu'elle est.

la Plupart du reste du code de cette méthode est inintéressant logique liée à l'itération sur les sommets. L'important, c'est qu'une fois par itération de la boucle while j'appelle processSegment et puis j'appelle processSegment de nouveau à la fin de la méthode pour traiter l'arête qui relie le dernier sommet de la premier sommet.

regardons le code pour 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);
}

dans cette méthode je mets en œuvre les étapes pour transformer un bord dans la géométrie standard comme décrit ci-dessus. D'abord je calcule segmentDisplacement , le déplacement du sommet initial au sommet final. Cela définit l'axe x de la géométrie standard. Je fais un retour anticipé si ce déplacement est zéro.

ensuite je calcule la longueur du déplacement, parce que c'est nécessaire pour obtenir le vecteur de l'unité X. Une Fois Que J'Ai avoir cette information, je calcule le déplacement du centre du cercle au sommet initial. Le produit dot de ceci avec segmentDisplacement me donne leftX que j'avais appelé xi. Puis rightX , que j'appelais xf, est juste leftX + segmentLength . Enfin je fais le produit de coin pour obtenir y comme décrit ci-dessus.

maintenant que j'ai transformé le problème en géométrie standard, il sera facile à traiter. C'est ce que l' processSegmentStandardGeometry méthode does. Regardons le 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);
    }
}

le premier if distingue les cas où y est suffisamment petit pour que le bord puisse croiser le cercle. Si y est grand et qu'il n'y a aucune possibilité d'intersection, alors j'appelle la méthode pour gérer cette affaire. Sinon, je m'occupe du cas où l'intersection est possible.

si l'intersection est possible, je calcule la coordonnée x de l'intersection, intersectionX , et je divise le bord vers le haut en trois parties, qui correspondent aux régions 1, 2, et 3 de la géométrie standard figure ci-dessus. D'abord j'ai la poignée de la région 1.

pour gérer la Région 1, je vérifie si leftX est effectivement inférieur à -intersectionX car autrement il n'y aurait pas de Région 1. S'il y a une Région 1, alors j'ai besoin de savoir quand elle se termine. Il se termine au minimum de rightX et -intersectionX . Après avoir trouvé ces coordonnées x, je m'occupe de ça. non-intersection de la région.

je fais la même chose pour la Région 3.

pour la Région 2, je dois faire un peu de logique pour vérifier que leftX et rightX se situent effectivement entre -intersectionX et intersectionX . Après avoir trouvé la région, je n'ai besoin que de la longueur de la région et y , donc je passe ces deux nombres à une méthode abstraite qui gère la Région 2.

maintenant, regardons au code pour 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);
}

j'utilise simplement atan2 pour calculer la différence d'angle entre leftX et rightX . Puis j'ajoute du code pour traiter de la discontinuité dans atan2 , mais cela est probablement inutile, parce que la discontinuité se produit soit à 180 degrés ou 0 degrés. Puis je passe la différence d'angle sur une méthode abstraite. Enfin, nous n'avons que des méthodes abstraites et des getters:

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

}

regardons maintenant la classe étendue, 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) {

}

}

il a un champ area pour garder une trace de la zone. initialize met la zone à zéro, comme prévu. Lorsque nous traitons une arête ne se croisant pas, nous incrémentons la surface par R^2 Δθ/2 comme nous concluons que nous devrions au-dessus. Pour un bord d'intersection, nous décrémentons la zone par y*length/2 . C'est ainsi que les valeurs négatives pour y correspondent à positif domaines, que nous avons décidé qu'ils devraient.

Maintenant, la chose intéressante est que, si nous voulons garder une trace du périmètre de ne pas avoir à faire beaucoup plus de travail. J'ai défini une classe AreaPerimeter :

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

}

et maintenant nous avons juste besoin d'étendre notre classe abstraite à nouveau en utilisant AreaPerimeter comme type.

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

}

nous avons une variable perimeter pour suivre le périmètre, nous nous rappelons la valeur de la radius à évitez d'appeler Math.sqrt beaucoup, et nous déléguons le calcul de la zone à notre CircleAreaFinder . Nous pouvons voir que les formules du périmètre sont faciles.

pour référence voici le code complet de 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;
    }

de toute façon, c'est ma description de l'algorithme. Je pense que c'est bon parce que c'est exact et il n'y a pas vraiment beaucoup de cas à vérifier.

j'ai presque un an et demi de retard, mais j'ai pensé que peut-être les gens seront intéressés par code ici que j'ai écrit qui je pense fait cela correctement. Regarder dans la fonction IntersectionArea près du fond. L'approche générale consiste à enlever le polygone convexe circonscrit par le cercle, puis à s'occuper des petits capuchons circulaires.

en supposant que vous parlez des pixels entiers, pas réel, l'implémentation naïve serait de boucler chaque pixel du triangle et de vérifier la distance du centre du cercle par rapport à son rayon.

ce n'est pas une formule mignonne, ou particulièrement rapide, mais il ne fait le travail.

try computational geometry

Note: Ce n'est pas un problème insignifiant, j'espère que ce ne sont pas des devoirs ;-)

si vous avez un GPU à votre disposition, vous pouvez utiliser cette technique pour obtenir un nombre de pixels de l'intersection..

je pense que vous ne devriez pas approximer le cercle comme un ensemble de triangles, au lieu de cela vous pouvez approximer sa forme avec un polygone. L'algorithme naïf peut ressembler à:

1. Convertissez-vous en polygone avec le nombre désiré de Sommets.
2. calculez l'intersection de deux polygones (cercle converti et triangle).
3. calculez le carré de cette intersection.

Vous pouvez optimiser cet algorithme en combinant l'étape 2 et l'étape 3 dans une seule fonction.

lire ces liens:

surface du polygone convexe

Intersection des polygones convexes

comme vos formes sont convexes, vous pouvez utiliser L'estimation Monte Carlo.

dessinez une boîte autour du cercle et du triangle.

choisissez des points aléatoires dans la boîte et gardez un compte de combien tombent dans le cercle, et combien tombent à la fois dans le cercle et le triangle.

zone D'intersection zone de cercle * # points dans le cercle et triangle / # points dans le cercle

arrêter de choisir des points lorsque le la surface estimée ne change pas de plus d'une certaine quantité sur un certain nombre de tours, ou choisissez simplement un nombre fixe de points basés sur la surface de la boîte. L'estimation de la surface devrait converger assez rapidement à moins que l'une de vos formes ait très peu de surface.

Note: Voici comment déterminer si un point est dans un triangle: coordonnées barycentriques

Comment voulez-vous être? Si vous pouvez vous rapprocher le cercle avec des formes simples, vous pouvez simplifier le problème. Il ne serait pas difficile de modéliser un cercle très étroit des triangles de réunion au centre, par exemple.

si seulement un des segments de ligne du triangle croise le cercle, la solution mathématique pure n'est pas trop difficile. Une fois que vous savez quand les deux points d'intersection sont, vous pouvez utiliser la formule de distance pour trouver la longueur d'accord.

selon ces équations :

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

où c est la longueur de l'accord, r est le rayon, P devient l'angle à travers le centre, et A est la zone. Notez que cette solution casse si plus de la moitié du cercle est coupé.

il est probablement pas la peine de l'effort si vous avez juste besoin d'une approximation, car il fait plusieurs hypothèses sur ce que l'intersection réelle ressemble.

mon premier instinct serait de tout transformer pour que le cercle soit centré sur l'origine, de passer du triangle aux coordonnées polaires, et de résoudre pour l'intersection (ou encombrement) du triangle avec le cercle. Je n'ai pas encore travaillé sur le papier, donc ce n'est qu'une intuition.