Calculer la zone d'intersection entre un cercle et un triangle?
https://stackoverflow.com/questions/540014
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Comment peut-on calculer la zone d'intersection entre un triangle (comme spécifié trois (X, Y) paires) et un cercle (X, Y, R)? Je l'ai fait quelques recherches en vain. Ceci est pour le travail, pas à l'école. :)
Il ressemblerait à quelque chose comme ça en C #:
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)
{
...
}
La solution
Si vous voulez une solution exacte (ou au moins aussi précis que vous pouvez obtenir en utilisant l'arithmétique à virgule flottante), cela va impliquer beaucoup de travail sur le terrain, parce qu'il ya tant de cas à considérer.
Je compte neuf cas différents (classés dans la figure ci-dessous par le nombre de sommets du triangle à l'intérieur du cercle, et le nombre d'arêtes du triangle qui se croisent ou sont contenus dans le cercle):
(Cependant, ce genre d'énumération des cas géométriques est bien connu pour être difficile, et il ne me surprendrait pas du tout si je manqué un ou deux!)
Ainsi, l'approche est:
-
Déterminer pour chaque sommet du triangle si elle est à l'intérieur du cercle. Je vais supposer que vous savez comment faire.
-
Déterminer pour chaque arête du triangle si elle coupe le cercle. (J'ai écrit une méthode , ou voir un livre de géométrie algorithmique .) Vous devez calculer le ou les points d'intersection (le cas échéant) pour une utilisation à l'étape 4.
-
Déterminer lequel des neuf cas que vous avez.
-
Calculer la zone de l'intersection. Cas 1, 2 et 9 sont faciles. Dans les six autres cas, j'ai tracé des lignes pointillées pour montrer comment partitionner la zone d'intersection en triangles et segments circulaires sur la base des sommets d'origine du triangle, et sur les points d'intersection vous calculée à l'étape 2.
Cet algorithme va être assez délicate et sujette à des erreurs qui affectent seulement l'un des cas, alors assurez-vous que vous avez des cas de test qui couvrent l'ensemble des neuf cas (et je suggère permutant les sommets des triangles de test aussi). Portez une attention particulière aux cas où l'un des sommets du triangle est sur le bord du cercle.
Si vous n'avez pas besoin d'une solution exacte, puis pixelliser les chiffres et le comptage des pixels dans l'intersection (comme suggéré par deux autres répondants) semble être une approche de code, et en conséquence moins sujettes à des erreurs beaucoup plus facile.
Autres conseils
D'abord, je vais nous rappeler comment trouver la surface d'un polygone. Une fois que nous l'avons fait, l'algorithme pour trouver l'intersection entre un polygone et un cercle devrait être facile à comprendre.
Comment trouver la surface d'un polygone
Regardons le cas d'un triangle, parce que toute la logique essentielle y apparaît. Supposons que nous avons un triangle dont les sommets (x1, y1), (x2, y2) et (x3, y3) que vous allez dans le triangle dans le sens antihoraire, comme le montre la figure ci-dessous:
Ensuite, vous pouvez calculer la zone par la formule
A = (x1 + x2 y2 y3 + x3 y1 - y2 x2y1- x3 - x1y3). / 2
Pour voir pourquoi cette formule fonctionne, nous allons réarranger il est donc sous la forme
A = (x1 y2 - y1 x2) / 2 + (y3 x2 - x3 y2) / 2 +. (X3 y1 - x1y3) / 2
Maintenant, le premier terme est la zone suivante, ce qui est positif dans notre cas:
Si on ne sait pas que la zone de la région verte est en effet (x1 y2 - x2 y1) / 2, puis lire cette .
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 la zone est négatif
L'ajout de ces trois jusqu'à nous obtenons l'image suivante
On voit que la zone verte qui était en dehors du triangle est annulé par la zone rouge, de sorte que la superficie nette est juste la zone du triangle, ce qui montre pourquoi notre formule était vrai dans ce cas.
Ce que j'ai dit ci-dessus l'explication intuitive pour expliquer pourquoi la formule de la zone était correcte. Une explication plus rigoureuse serait d'observer que lorsque l'on calcule la zone 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 efficacement r ^ 2dθ / 2 autour de la limite du polygone, et 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. Depuis l'intégration rdrdθ sur la région délimitée par le polygone donne la région, nous concluons que notre procédure doit donner correctement la zone.
Région de l'intersection d'un cercle avec un polygone
Maintenant, nous allons discuter de la façon de trouver la zone de l'intersection d'un cercle de rayon R avec un polygone comme indiqué dans la figure suivante:
Nous sommes intéressés à trouver la zone de la région verte. On peut, comme dans le cas du polygone unique, briser nos calculs en vue de trouver une zone pour chaque côté du polygone, puis ajoutez ces zones vers le haut.
Notre première zone ressemblera:
La seconde zone ressemblera
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. Espérons que les annulations fonctionnent de telle sorte que la surface nette est en effet la région 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 des raisons pour lesquelles cela fonctionne. Soit I la région définie par l'intersection et P le polygone. Puis de la discussion précédente, nous savons que nous voulons à l'ordinateur l'intégrale de r ^ 2dθ /2 autour de la limite de I. Cependant, cela difficile à faire, car 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 ^ dO / 2 par rapport à la limite du polygone. Pour voir pourquoi cela donne la bonne réponse, nous allons définir une fonction π qui prend un point en coordonnées polaires (r, θ) au point (max (r, R), θ). Il ne devrait pas être source de confusion pour faire référence aux fonctions de coordonnées de π (r) = max (r, R) et π (θ) = θ. Alors que nous avons fait était d'intégrer π (r) ^ 2 dO / 2 sur la limite du polygone.
D'autre part, depuis tc (thetav) = θ, c'est le même que l'intégration π (r) ^ 2 dn (θ) / 2 sur la limite du polygone.
en ce moment un changement de variable, nous constatons que nous obtiendrions la même réponse si nous avons intégré r ^ 2 dO / 2 sur la limite de π (P), où π (P) est l'image de P sous π.
En utilisant le théorème de Stokes à nouveau, nous savons que l'intégration r ^ 2 dO / 2 sur la limite de π (P) nous donne la zone de π (P). En d'autres termes, il donne la même réponse que l'intégration dxdy sur π (P).
L'utilisation d'un changement de variable à nouveau, nous savons que l'intégration dxdy sur π (P) est le même que l'intégration 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 points dans le cercle seul si J = 1 y, de sorte que la contribution de cette partie de P est la zone de la partie de P qui se trouve dans le cercle à-dire la zone de l'intersection. La deuxième région est la région à l'extérieur du cercle. Il J = 0 puisque π affaisse 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ûr que nous savons sur le plan conceptuel comment trouver la région, nous allons parler plus précisément sur la façon de calculer la contribution d'un seul segment. Commençons par regarder un segment dans ce que je vais appeler la « géométrie standard ». Il est indiqué ci-dessous.
Dans la géométrie standard, le bord passe horizontalement de gauche à droite. Il est décrit par trois nombres: xi, la coordonnée x où le bord commence, xf, la coordonnée x où le bord se termine, et y, la coordonnée y du bord.
Maintenant, nous voyons que si | y | La surface de la zone 2 se trouve à la surface d'un triangle. Cependant, il faut faire attention à signe. Nous voulons que la zone indiquée soit positive pour nous dire la région est - (xint - (-Xint)). Y / 2 Une autre chose à garder à l'esprit est que, en général, xi ne doit pas être inférieure à -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'y a qu'une seule pièce qui est similaire à la région 1 dans la figure. Maintenant que nous savons comment calculer la surface d'un bord en géométrie standard, la seule chose à faire est de décrire comment transformer une arête en géométrie standard. Mais ce juste un simple changement de coordonnées. Compte tenu de certaines avec vi sommet initial et sommet final vf, le nouveau vecteur d'unité x sera le vecteur unitaire pointant de vi à Vf. Alors xi est juste le déplacement de vi du centre du cercle en pointillés en x et xf est juste xi plus la distance entre vi et vf. Pendant ce temps y est donnée par le produit en forme de coin de x avec le déplacement de vi à partir du centre du cercle. Voilà qui complète la description de l'algorithme, maintenant il est temps d'écrire un code. Je vais utiliser java. Tout d'abord, puisque nous travaillons avec des cercles, nous devrions avoir une classe de cercle Pour les polygones, je vais utiliser la classe Maintenant, pour le travail réel. Je vais séparer la logique d'itération par les bords, en mettant les bords en géométrie standard, etc., à partir de la logique de calcul de la zone une fois que cela est fait. La raison est que vous pouvez à l'avenir vouloir calculer quelque chose d'autre en plus ou en plus de la région et vous voulez être en mesure de réutiliser le code avoir à traiter avec itérer les bords. J'ai une classe générique qui calcule une propriété de classe Il dispose de trois méthodes statiques qui qu'aider calcul la géométrie: Il y a deux champs d'instance, un Vient ensuite la méthode de calcul de ce que nous voulons calculer: Prenons une seconde pour regarder Ensuite, je déclare les La méthode La plupart du reste du code de cette méthode est logique sans intérêt lié à itérer les sommets. L'important est qu'une fois par itération de la boucle pendant que j'appelle Regardons le code pour Dans ce procédé, je mettre en œuvre les étapes consistant à transformer une arête dans la géométrie standard comme décrit ci-dessus. Je calcule d'abord Ensuite, je calcule la longueur du déplacement, parce que cela est nécessaire pour obtenir l'unité x vecteur. Une fois que j'ai ces informations, je calcule le déplacement du centre du cercle au sommet initial. Le produit scalaire de cela avec Maintenant que je l'ai transformé le problème dans la géométrie standard, il sera facile à traiter. C'est ce que la méthode La première Si intersection est possible, je calcule la coordonnée x d'intersection, Pour gérer la région 1, je vérifie si Je fais une chose semblable à gérer la région 3. Pour la région 2, je dois faire une certaine logique pour vérifier que Maintenant, regardons le code pour J'utilise simplement Maintenant, regardons la classe d'extension, } Il a une Maintenant, la chose est propre si nous voulons garder une trace du périmètre que nous ne devons pas faire beaucoup plus de travail. J'ai défini une classe et maintenant nous avons juste besoin d'étendre notre classe abstraite à nouveau en utilisant Nous avons une Pour référence est ici le code complet de Quoi qu'il en soit, c'est ma description de l'algorithme. Je pense qu'il est agréable car il estexacte et il n'y a pas vraiment que de nombreux cas à vérifier. 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 de java. Shapes ont une PathIterator que je peux utiliser pour itérer sur les bords du polygone. T sur notre intersection du cercle de polygone. 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 qui maintient juste une copie du cercle, et le currentSquareRadius, qui conserve une copie du rayon carré. Cela peut sembler étrange, mais la classe j'utilise est en fait équipé pour trouver les zones de toute une collection d'intersections de polygones de cercle. Voilà pourquoi je me réfère à l'un des cercles comme « courant ». private Circle currentCircle;
private double currentSquareRadius;
public final T computeValue(Circle circle, Shape shape) {
initialize();
processCircleShape(circle, shape);
return getValue();
}
initialize() et getValue() sont abstraites. initialize() fixerait la variable qui maintient un total de la zone à zéro, et getValue() serait tout simplement retourner la région. 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);
}
initializeForNewCirclePrivate rapidement. Cette méthode permet de définir simplement les champs d'instance et permet à la classe dérivée de stocker toute propriété du cercle. Sa définition est private void initializeForNewCirclePrivate(Circle circle) {
currentCircle = circle;
currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
initializeForNewCircle(circle);
}
initializeForNewCircle est abstraite et une mise en œuvre serait pour elle de stocker le rayon des cercles pour éviter d'avoir à faire des racines carrées. Quoi qu'il en soit de retour à processCircleShape. Après avoir appelé initializeForNewCirclePrivate, nous vérifions si le polygone est null (que je suis interprète comme un polygone vide), et nous reviendrons si elle est null. Dans ce cas, notre zone calculée serait égale à zéro. Si le polygone est null pas alors nous obtenons la PathIterator du polygone. L'argument de la méthode de getPathIterator La parole est une transformation affine qui peut être appliquée à la trajectoire. Je ne veux pas d'appliquer un, donc je passe juste null. double[]s qui gardera la trace des sommets. Je dois rappeler le premier sommet parce que le PathIterator ne me donne que chaque sommet une fois, donc je dois revenir en arrière après m'a donné le dernier sommet, et former un bord avec ce dernier sommet et le premier sommet. currentSegment sur la ligne suivante met le sommet suivant dans son argumentation. Il renvoie un code qui vous indique quand il est hors de sommets. Voilà pourquoi l'expression de contrôle pour ma boucle while est ce qu'il est. processSegment puis j'appelle processSegment à nouveau à la fin de la méthode pour traiter le bord qui relie le dernier sommet au premier sommet. 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);
}
segmentDisplacement, le déplacement à partir du sommet initial vers le sommet final. Ceci définit l'axe x de la norme geometry. Je fais un retour rapide si ce déplacement est nul. segmentDisplacement me donne leftX que j'avais appelle xi. Alors rightX, que j'avais appelle xf, est juste leftX + segmentLength. Enfin, je fais le produit de coin pour obtenir y comme décrit ci-dessus. processSegmentStandardGeometry fait. 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);
}
}
if distingue les cas où y est assez petit pour que le bord peut recouper le cercle. Si y est grand et il n'y a aucune possibilité d'intersection, j'appelle la méthode pour traiter ce cas. Sinon, je gérer le cas où l'intersection est possible. intersectionX, et je divise le bord en trois parties, qui correspondent aux régions 1, 2 et 3 de la figure de géométrie standard ci-dessus. Tout d'abord je gérer la région 1. leftX est en effet moins de -intersectionX sinon il n'y aurait pas de région 1. S'il y a une région 1, alors je dois savoir quand elle se termine. Elle se termine au minimum rightX et -intersectionX. Après avoir trouvé ces coordonnées x, je traite cette région non-intersection. leftX et rightX ne fait une région entre crochets entre -intersectionX et intersectionX. Après avoir trouvé la région, je ne ai besoin de la longueur de la région et y, donc je passe ces deux chiffres à une méthode abstraite qui gère la région 2. 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);
}
atan2 pour calculer la différence d'angle entre leftX et rightX. Puis ajouter le code pour faire face à la discontinuité dans atan2, mais cela est sans doute inutile, car la discontinuité se produit soit à 180 degrés ou 0 degrés. Ensuite, je passe la différence d'angle sur une méthode abstraite. Enfin, nous avons juste des méthodes abstraites et 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;
}
}
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 de terrain pour garder une trace de la région. initialize définit la zone à zéro, comme prévu. Lorsque nous traitons un bord non d'intersection, on incrémente la zone par R ^ 2 Δθ / 2 comme nous avons conclu que nous devrions ci-dessus. Pour un bord d'intersection, nous décrémentons la région par y*length/2. Il en était ainsi que les valeurs négatives pour y correspondent à des zones positives, comme nous avons décidé qu'ils devraient. 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;
}
}
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);
}
}
perimeter variable pour garder la trace du périmètre, nous nous souvenons de la valeur du radius pour éviter doivent appeler Math.sqrt beaucoup, et nous déléguer le calcul de la zone à notre CircleAreaFinder. Nous pouvons voir que les formules pour le périmètre sont faciles. 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;
}
Je suis presque un an et demi de retard, mais je pensais que les gens seront intéressés par
En supposant que vous parlez pixels entiers, pas réel, la mise en œuvre naïve serait de boucle à travers chaque pixel du triangle et vérifier la distance du centre du cercle contre son rayon. Il est pas une formule mignon, ou particulièrement rapide, mais il ne faire le travail.
Remarque: ce n'est pas un problème trivial, j'espère que ce n'est pas devoir; -)
Si vous avez un processeur graphique à votre disposition, vous pouvez utiliser cette technique pour obtenir un nombre de pixels de l'intersection ..
Je pense que vous ne devriez pas le cercle approximatif comme un certain ensemble de triangles, au lieu de cela, vous pouvez rapprocher sa forme avec un polygone. L'algorithme naïf peut ressembler à:
- Convertir vous cercle polygone avec un nombre désiré de sommets.
- Calculer l'intersection de deux polygones (cercle converti et un triangle).
- Calculer carré de cette intersection.
Vous pouvez optimiser cet algorithme en combinant les étapes 2 et 3 en fonction unique.
Lire ce lien: Étant donné que vos formes sont convexes, vous pouvez utiliser l'estimation de la zone Monte Carlo. Dessiner une zone autour du cercle et le triangle. Choisissez des points aléatoires dans la boîte et de garder un compte de combien tombent dans le cercle, et combien tombent à la fois le cercle et le triangle. zone d'intersection ≅ zone du cercle * # points en cercle et triangle / points dans le cercle # Arrêtez le choix des points lorsque la zone estimée ne change pas de plus d'un certain montant sur un certain nombre de tours, ou il suffit de choisir un nombre fixe de points en fonction de la zone de la boîte. L'estimation de la zone devrait converger assez rapidement à moins que l'une de vos formes a très peu de zone. Note: Voici comment déterminer si un point est dans un triangle: coordonnées barycentriques
Zone de polygone convexe
Comment exacte que vous devez être? Si vous pouvez approcher le cercle avec des formes plus simples, vous pouvez simplifier le problème. Il ne serait pas difficile de modéliser un cercle comme un ensemble de triangles très étroits réunis au centre, par exemple.
Si seulement l'un des segments de ligne du triangle coupe le cercle, la solution pure mathématique est pas trop dur. Une fois que vous savez quand les deux points d'intersection sont, vous pouvez utiliser la formule de distance pour trouver la longueur de la corde.
Selon ces équations :
ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))
où c est la longueur de la corde, r est le rayon, θ devient l'angle au centre, et A est la surface. Notez que cette solution se brise si plus de la moitié du cercle est coupé.
Il est sans doute pas la peine 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 de telle sorte que le cercle est centré sur l'origine, le triangle trans en coordonnées polaires, et résoudre l'intersection (ou englobement) du triangle avec le cercle. Je ne l'ai pas réellement travaillé par encore sur le papier mais si c'est seulement une intuition.
