Calcola l’area di intersezione tra un cerchio e un triangolo?

Come si calcola l’area di intersezione tra un triangolo (specificato come tre (X, Y) coppie e un cerchio (X, Y, R)? Ho fatto qualche ricerca senza successo. Questo è per il lavoro, non per la scuola. 🙂

Sembrerebbe qualcosa del genere in C #:

struct { PointF vert[3]; } Triangle; struct { PointF center; float radius; } Circle; // returns the area of intersection, eg: // 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) { ... } 

Se si desidera una soluzione esatta (o almeno esatta come si può ottenere usando l’aritmetica a virgola mobile), questo richiederà molto tempo, perché ci sono così tanti casi da considerare.

Conto nove casi diversi (categorizzati nella figura seguente per il numero di vertici del triangolo all’interno del cerchio e il numero di bordi del triangolo che si intersecano o sono contenuti nel cerchio):

Nove casi per l'intersezione: 1, 2. nessun vertice, nessun bordo; 3. nessun vertice, un bordo; 4. nessun vertice, due bordi; 5. nessun vertice, tre bordi; 6. un vertice, due bordi; 7. un vertice, tre bordi; 8. due vertici, tre bordi; 9. tre vertici, tre bordi.

(Tuttavia, questo tipo di enumerazione di casi geometrici è ben noto per essere difficile, e non mi sorprende affatto se ne manchi uno o due!)

Quindi l’approccio è:

  1. Determina per ogni vertice del triangolo se è all’interno del cerchio. Immagino che tu sappia come farlo.

  2. Determina per ciascun lato del triangolo se interseca il cerchio. (Ho scritto un metodo qui , o vedere qualsiasi libro di geometria computazionale.) Dovrai calcolare il punto oi punti di intersezione (se ce ne sono) per l’uso nel passaggio 4.

  3. Determina quale dei nove casi hai.

  4. Calcola l’area dell’intersezione. I casi 1, 2 e 9 sono facili. Nei restanti sei casi ho tracciato linee tratteggiate per mostrare come suddividere l’area di intersezione in triangoli e segmenti circolari in base ai vertici originali del triangolo e sui punti di intersezione calcolati nel passaggio 2.

Questo algoritmo sarà piuttosto delicato e sobject a errori che riguardano solo uno dei casi, quindi assicurati di avere casi di test che coprano tutti i nove casi (e ti suggerisco di permutare anche i vertici dei triangoli di test). Presta particolare attenzione ai casi in cui uno dei vertici del triangolo si trova sul bordo del cerchio.

Se non hai bisogno di una soluzione esatta, rasterizzare le figure e contare i pixel nell’intersezione (come suggerito da un paio di altri intervistati) sembra un approccio al codice molto più semplice, e corrispondentemente meno incline agli errori.

Per prima cosa ci ricorderò come trovare l’area di un poligono. Una volta che abbiamo fatto questo, l’algoritmo per trovare l’intersezione tra un poligono e un cerchio dovrebbe essere facile da capire.

Come trovare l’area di un poligono

Diamo un’occhiata al caso di un triangolo, perché lì appare tutta la logica essenziale. Supponiamo di avere un triangolo con vertici (x1, y1), (x2, y2) e (x3, y3) mentre girate il triangolo in senso antiorario, come mostrato nella seguente figura: triangleFigure

Quindi puoi calcolare l’area in base alla formula

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

Per capire perché questa formula funziona, riorganizziamola in modo che sia nella forma

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

Ora il primo termine è la seguente area, che è positiva nel nostro caso: inserisci la descrizione dell'immagine qui

Se non è chiaro che l’area della regione verde sia effettivamente (x1 y2 – x2 y1) / 2, leggi questo .

Il secondo termine è quest’area, che è di nuovo positiva:

inserisci la descrizione dell'immagine qui

E la terza area è mostrata nella figura seguente. Questa volta l’area è negativa

inserisci la descrizione dell'immagine qui

Aggiungendo questi tre si ottiene la seguente immagine

inserisci la descrizione dell'immagine qui

Vediamo che l’area verde al di fuori del triangolo è cancellata dall’area rossa, in modo che l’area netta sia solo l’area del triangolo, e questo mostra perché la nostra formula era vera in questo caso.

Quello che ho detto sopra è stata la spiegazione intuitiva del motivo per cui la formula dell’area era corretta. Una spiegazione più rigorosa sarebbe osservare che quando calcoliamo l’area da un bordo, l’area che otteniamo è la stessa area che otterremmo dall’integrazione r ^ 2dθ / 2, quindi stiamo integrando efficacemente r ^ 2dθ / 2 attorno al limite del poligono, e dal teorema di stokes, questo dà lo stesso risultato dell’integrazione di rdrdθ sulla regione delimitata dal poligono. Poiché l’integrazione di rdrdθ sulla regione delimitata dal poligono fornisce l’area, concludiamo che la nostra procedura deve fornire correttamente l’area.

Area dell’intersezione di un cerchio con un poligono

Ora discutiamo come trovare l’area dell’intersezione di un cerchio di raggio R con un poligono come mostrato nella figura seguente:

inserisci la descrizione dell'immagine qui

Siamo interessati a trovare l’area della regione verde. Possiamo, come nel caso del singolo poligono, rompere il nostro calcolo per trovare un’area per ciascun lato del poligono, e quindi aggiungere quelle aree in alto.

La nostra prima area sarà simile a: inserisci la descrizione dell'immagine qui

La seconda area sarà simile inserisci la descrizione dell'immagine qui

E la terza area sarà inserisci la descrizione dell'immagine qui

Ancora una volta, le prime due aree sono positive nel nostro caso mentre la terza sarà negativa. Speriamo che le cancellazioni funzionino in modo tale che l’area netta sia effettivamente l’area a cui siamo interessati. Vediamo.

inserisci la descrizione dell'immagine qui

In effetti la sum delle aree sarà l’area a cui siamo interessati.

Di nuovo, possiamo dare una spiegazione più rigorosa del perché questo funziona. Sia I la regione definita dall’intersezione e sia P il poligono. Quindi, dalla discussione precedente, sappiamo che vogliamo integrare l’integrale di r ^ 2dθ / 2 attorno al limite di I. Tuttavia, questo è difficile da fare perché è necessario trovare l’intersezione.

Invece abbiamo fatto un integrale sul poligono. Abbiamo integrato max (r, R) ^ 2 dθ / 2 oltre il limite del poligono. Per capire perché questo dà la risposta giusta, definiamo una funzione π che prende un punto in coordinate polari (r, θ) nel punto (max (r, R), θ). Non dovrebbe essere fonte di confusione riferirsi alle funzioni coordinate di π (r) = max (r, R) e π (θ) = θ. Quindi quello che abbiamo fatto è stato integrare π (r) ^ 2 dθ / 2 sul limite del poligono.

D’altra parte poiché π (θ) = θ, questo è lo stesso di integrare π (r) ^ 2 dπ (θ) / 2 oltre il limite del poligono.

Ora facendo un cambiamento di variabile, troviamo che otterremmo la stessa risposta se abbiamo integrato r ^ 2 dθ / 2 sul limite di π (P), dove π (P) è l’immagine di P sotto π.

Usando nuovamente il teorema di Stokes, sappiamo che l’integrazione di r ^ 2 dθ / 2 sul confine di π (P) ci dà l’area di π (P). In altre parole, dà la stessa risposta dell’integrazione di dxdy su π (P).

Usando di nuovo un cambiamento di variabile, sappiamo che l’integrazione di dxdy su π (P) equivale all’integrazione di Jdxdy su P, dove J è il jacobiano di π.

Ora possiamo dividere l’integrale di Jdxdy in due regioni: la parte nel cerchio e la parte al di fuori del cerchio. Ora π lascia i punti nel cerchio da solo, quindi J = 1 lì, quindi il contributo da questa parte di P è l’area della parte di P che si trova nel cerchio cioè l’area dell’intersezione. La seconda regione è la regione al di fuori del cerchio. Ci J = 0 poiché π collassa questa parte fino al limite del cerchio.

Quindi ciò che calcoliamo è davvero l’area dell’intersezione.

Ora che siamo relativamente sicuri di sapere concettualmente come trovare l’area, parliamo in modo più specifico di come calcolare il contributo di un singolo segmento. Iniziamo guardando un segmento in quella che chiamerò “geometria standard”. È mostrato sotto.

inserisci la descrizione dell'immagine qui

Nella geometria standard, il bordo va in orizzontale da sinistra a destra. È descritto da tre numeri: xi, la coordinata x dove inizia il bordo, xf, la coordinata x dove finisce il bordo e y, la coordinata y del bordo.

Ora vediamo che se | y |

L’area della regione 2 è solo l’area di un triangolo. Tuttavia, dobbiamo fare attenzione al segno. Vogliamo che l’area mostrata sia positiva, quindi diremo che l’area è – (xint – (-xint)) y / 2.

Un’altra cosa da tenere a mente è che, in generale, xi non deve essere inferiore a -xint e xf non deve essere maggiore di xint.

L’altro caso da considerare è | y | > R. Questo caso è più semplice, perché c’è un solo pezzo che è simile alla regione 1 nella figura.

Ora che sappiamo come calcolare l’area da un bordo in geometria standard, l’unica cosa che resta da fare è descrivere come trasformare qualsiasi spigolo in geometria standard.

Ma questo è solo un semplice cambio di coordinate. Dati alcuni con il vertice iniziale vi e il vertice finale vf, il nuovo vettore di unità x sarà il vettore unitario che punta da vi a vf. Quindi xi è solo lo spostamento di vi dal centro del cerchio punteggiato in x, e xf è solo xi più la distanza tra vi e vf. Nel frattempo y è dato dal prodotto di cuneo di x con lo spostamento di vi dal centro del cerchio.

Codice

Questo completa la descrizione dell’algoritmo, ora è il momento di scrivere del codice. Userò java.

Prima di tutto, dato che stiamo lavorando con le cerchie, dovremmo avere una class circolare

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

Per i poligoni, userò la class Shape di java. Shape s ha un PathIterator che posso usare per scorrere i bordi del poligono.

Ora per il lavoro effettivo. Separerò la logica dell’iterazione attraverso i bordi, mettendo i bordi nella geometria standard, ecc., Dalla logica di calcolo dell’area una volta eseguita questa operazione. La ragione di questo è che in futuro potresti voler calcolare qualcos’altro oltre o in aggiunta all’area e vuoi essere in grado di riutilizzare il codice avendo a che fare con l’iterazione attraverso i bordi.

Quindi ho una class generica che calcola alcune proprietà della class T sulla nostra intersezione del cerchio poligonale.

public abstract class CircleShapeIntersectionFinder {

Ha tre metodi statici che aiutano solo a calcolare la geometria:

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

Ci sono due campi di istanze, un Circle che conserva solo una copia del cerchio e la currentSquareRadius , che conserva una copia del raggio del quadrato. Questo può sembrare strano, ma la class che sto usando è in realtà equipaggiata per trovare le aree di un’intera collezione di intersezioni tra poligoni e cerchi. Questo è il motivo per cui mi riferisco a uno dei cerchi come “attuale”.

 private Circle currentCircle; private double currentSquareRadius; 

Poi viene il metodo per calcolare ciò che vogliamo calcolare:

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

initialize() e getValue() sono astratti. initialize() imposta la variabile che mantiene un totale dell’area a zero e getValue() restituisce solo l’area. La definizione per processCircleShape è

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

Diamo un secondo per vedere initializeForNewCirclePrivate rapidamente. Questo metodo imposta solo i campi di istanza e consente alla class derivata di memorizzare qualsiasi proprietà della cerchia. La sua definizione è

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

initializeForNewCircle è astratto e una implementazione sarebbe quella di memorizzare il raggio dei cerchi per evitare di dover fare radici quadrate. Comunque torniamo a processCircleShape . Dopo aver chiamato initializeForNewCirclePrivate , controlliamo se il poligono è null (che sto interpretando come poligono vuoto) e restituiamo se è null . In questo caso, la nostra area calcasting sarebbe zero. Se il poligono non è null , otteniamo il PathIterator del poligono. L’argomento del metodo getPathIterator che chiamo è una trasformazione affine che può essere applicata al percorso. Non voglio applicarne uno, quindi passo semplicemente null .

Quindi dichiaro il double[] s che terrà traccia dei vertici. Devo ricordare il primo vertice perché il PathIterator mi fornisce ogni vertice una volta sola, quindi devo tornare indietro dopo che mi ha dato l’ultimo vertice e formare un bordo con quest’ultimo vertice e il primo vertice.

Il metodo currentSegment nella riga successiva pone il prossimo vertice nel suo argomento. Restituisce un codice che ti dice quando è fuori dai vertici. Questo è il motivo per cui l’espressione di controllo per il mio ciclo while è quella che è.

La maggior parte del resto del codice di questo metodo è una logica non interessante correlata all’iterazione attraverso i vertici. L’importante è che una volta per iterazione del ciclo while chiamo processSegment e poi chiamo processSegment nuovamente alla fine del metodo per elaborare il bordo che collega l’ultimo vertice al primo vertice.

Diamo un’occhiata al codice per 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 questo metodo implemento i passaggi per trasformare un bordo nella geometria standard come descritto sopra. Per prima cosa calcola segmentDisplacement , lo spostamento dal vertice iniziale al vertice finale. Questo definisce l’asse x della geometria standard. Faccio un ritorno anticipato se questo spostamento è zero.

Successivamente, calcolo la lunghezza dello spostamento, poiché ciò è necessario per ottenere il vettore dell’unità x. Una volta che ho questa informazione, calcolo lo spostamento dal centro del cerchio al vertice iniziale. Il prodotto punto di questo con segmentDisplacement mi dà leftX che avevo chiamato xi. Quindi rightX , che stavo chiamando xf, è solo leftX + segmentLength . Finalmente faccio il prodotto wedge per ottenere y come descritto sopra.

Ora che ho trasformato il problema nella geometria standard, sarà facile da gestire. Questo è ciò che fa il metodo processSegmentStandardGeometry . Diamo un’occhiata al codice

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

Il primo if distingue i casi in cui y è abbastanza piccolo da poter intersecare il cerchio con il bordo. Se y è grande e non c'è possibilità di intersezione, allora chiamo il metodo per gestire quel caso. Altrimenti gestisco il caso in cui è ansible l'intersezione.

Se l'intersezione è ansible, calcolo la coordinata x dell'intersezione, intersectionX X e divido il bordo in tre parti, che corrispondono alle regioni 1, 2 e 3 della figura geometrica standard sopra. Per prima cosa gestisco la regione 1.

Per gestire la regione 1, controllo se leftX è effettivamente inferiore a -intersectionX altrimenti non ci sarebbe alcuna regione 1. Se c'è una regione 1, allora ho bisogno di sapere quando finisce. Finisce al minimo di rightX e -intersectionX . Dopo aver trovato queste coordinate x, mi occupo di questa regione non intersezionale.

Faccio una cosa simile per gestire la regione 3.

Per la regione 2, devo fare un po 'di logica per verificare che leftX e rightX effettivamente qualche area tra -intersectionX e intersectionX . Dopo aver trovato la regione, ho solo bisogno della lunghezza della regione e y , quindi passo questi due numeri su un metodo astratto che gestisce la regione 2.

Ora diamo un'occhiata al codice per 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); } 

Semplicemente uso atan2 per calcolare la differenza di angolo tra leftX e rightX . Quindi aggiungo il codice per gestire la discontinuità di atan2 , ma probabilmente non è necessario, perché la discontinuità si verifica a 180 gradi o 0 gradi. Poi passo la differenza di angolo su un metodo astratto. Infine, abbiamo solo metodi astratti e 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; } } 

Ora diamo un'occhiata alla class che si estende, CircleAreaFinder

 public class CircleAreaFinder extends CircleShapeIntersectionFinder { 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) { } 

}

Ha un'area di campo per tenere traccia dell'area. initialize area degli insiemi su zero, come previsto. Quando elaboriamo un arco non intersecante, incrementiamo l'area di R ^ 2 Δθ / 2 poiché abbiamo concluso che dovremmo sopra. Per un bordo intersecante, decrementiamo l'area di y*length/2 . Questo è stato così che i valori negativi per y corrispondono alle aree positive, come abbiamo deciso che dovrebbero.

Ora la cosa buona è che se vogliamo tenere traccia del perimetro non dobbiamo fare molto più lavoro. Ho definito una class 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; } } 

e ora abbiamo solo bisogno di estendere di nuovo la nostra class astratta usando AreaPerimeter come tipo.

 public class CircleAreaPerimeterFinder extends CircleShapeIntersectionFinder { 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); } } 

Abbiamo un perimeter variabile per tenere traccia del perimetro, ricordiamo il valore del radius per evitare di dover chiamare Math.sqrt molto e deleghiamo il calcolo dell'area al nostro CircleAreaFinder . Possiamo vedere che le formule per il perimetro sono facili.

Per riferimento qui è il codice completo di 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; } 

Ad ogni modo, questa è la mia descrizione dell'algoritmo. Penso che sia bello perché è esatto e non ci sono molti casi da controllare.

Ho quasi un anno e mezzo di ritardo, ma ho pensato che forse la gente sarebbe interessata al codice qui che ho scritto che penso faccia correttamente. Guarda in funzione IntersectionArea vicino al fondo. L’approccio generale è quello di prelevare il poligono convesso circoscritto dal cerchio e quindi gestire i piccoli cappucci circolari.

Supponendo che stai parlando di pixel interi, non reali, l’implementazione ingenua sarebbe quella di scorrere ogni pixel del triangolo e controllare la distanza dal centro del cerchio rispetto al suo raggio.

Non è una formula carina, o particolarmente veloce, ma svolge il suo compito.

prova la geometria computazionale

Nota: questo non è un problema banale, spero che non sia compito a casa 😉

Se hai una GPU a tua disposizione, puoi usare questa tecnica per ottenere un conteggio dei pixel dell’intersezione.

Penso che non dovresti approssimare il cerchio come un insieme di triangoli, invece di quello puoi approssimarlo con un poligono. L’algoritmo ingenuo può essere simile a:

  1. Converti cerchio in poligono con il numero desiderato di vertici.
  2. Calcola l’intersezione di due poligoni (cerchio convertito e triangolo).
  3. Calcola il quadrato di quell’intersezione.

È ansible ottimizzare questo algoritmo combinando il passaggio 2 e il passaggio 3 in una singola funzione.

Leggi questo link:
Area del poligono convesso
Intersezione di poligoni convessi

Poiché le tue forms sono convesse, puoi utilizzare la stima dell’area Monte Carlo.

Disegna una scatola attorno al cerchio e al triangolo.

Scegli i punti casuali nella casella e tieni un conteggio di quanti cadono nel cerchio e quanti ne cadono sia nel cerchio che nel triangolo.

Area di intersezione ≅ Area del cerchio * # punti in cerchio e triangolo / punti in cerchio

Smetti di scegliere i punti quando l’area stimata non cambia di più di una certa quantità per un certo numero di round, o semplicemente scegli un numero fisso di punti in base all’area della casella. La stima dell’area dovrebbe convergere piuttosto velocemente a meno che una delle tue forms abbia un’area molto piccola.

Nota: ecco come determinare se un punto si trova in un triangolo: coordinate baricentriche

Quanto esatto hai bisogno di essere? Se puoi approssimare il cerchio con forms più semplici, puoi semplificare il problema. Per esempio, non sarebbe difficile modellare un cerchio come un insieme di triangoli molto stretti che si incontrano al centro.

Se solo uno dei segmenti di linea del triangolo interseca il cerchio, la pura soluzione matematica non è troppo difficile. Una volta che sai quando sono i due punti di intersezione, puoi usare la formula della distanza per trovare la lunghezza della corda.

Secondo queste equazioni :

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

dove c è la lunghezza della corda, r è il raggio, θ diventa l’angolo attraverso il centro, e A è l’area. Note that this solution breaks if more than half the circle is cut off.

It’s probably not worth the effort if you just need an approximation, since it makes several assumptions about what the actual intersection looks like.

My first instinct would be to transform everything so that the circle is centered on origin, trans the triangle to polar coordinates, and solve for the intersection (or encompassment) of the triangle with the circle. I haven’t actually worked it through on paper yet though so that’s only a hunch.