Calcolare l'area di intersezione tra un cerchio e un triangolo?

Question

Come si calcolare l'area di intersezione tra un triangolo (specificata come tre coppie (X, Y)) e un cerchio (X, Y, R)? Ho fatto qualche ricerca senza alcun risultato. Questo è per il lavoro, non la scuola. :)

Si sarebbe simile a questo in 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)
{
 ...
}

Answer 1

Se si desidera una soluzione esatta (o almeno il più preciso come si può ottenere utilizzando aritmetica in virgola mobile), allora questo sta per coinvolgere un sacco di noia, perché ci sono tanti casi da prendere in considerazione.

io conto nove differenti casi (classificati in figura dal numero di vertici del triangolo all'interno del cerchio, e il numero di bordi del triangolo che si intersecano o sono contenuti nel cerchio):

(Tuttavia, questo tipo di enumerazione di casi geometriche è ben noto per essere difficile, e non mi sorprenderebbe affatto se ho perso uno o due!)

Quindi, l'approccio è:

1. Determinare per ogni vertice del triangolo se è all'interno del cerchio. Ho intenzione di assumere si sa come fare.

2. Determinare per ogni bordo del triangolo se interseca il cerchio. (Ho scritto un metodo href="http://garethrees.org/2009/02/17/physics/#section-4" qui , o vedo alcun libro di geometria computazionale .) Avrete bisogno di calcolare il punto oi punti di intersezione (se presente) per l'uso nella fase 4.

3. Determinare quale dei nove casi che avete.

4. calcolare l'area dell'intersezione. I casi 1, 2 e 9 sono facili. Nei rimanenti sei casi ho disegnato con linee tratteggiate per mostrare come dividere la zona di intersezione in triangoli e segmenti circolari basata sui vertici originali del triangolo, e sui punti di intersezione si calcolato al passaggio 2.

Questo algoritmo sta per essere piuttosto delicato e soggetto ad errori che interessano solo uno dei casi, in modo da assicurarsi di avere casi di test che coprono tutti i nove casi (e suggerisco permutando i vertici dei triangoli di prova troppo). Prestare particolare attenzione ai casi in cui uno dei vertici del triangolo è sul bordo del cerchio.

Se non avete bisogno di una soluzione esatta, quindi rasterizzazione le figure e contando i pixel nel punto di intersezione (come suggerito da un paio di altri intervistati) sembra un approccio molto più facile da codice, e di conseguenza meno soggetto a errori.

Answer 2

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

Guardiamo il caso di un triangolo, perché tutta la logica essenziale vi appare. Supponiamo che abbiamo un triangolo con vertici (X1, Y1), (X2, Y2), e (x3, Y3), come si va in giro per il triangolo in senso antiorario, come mostrato nella figura seguente:

È quindi possibile calcolare l'area con la formula

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

Per capire perché questa formula funziona, cerchiamo di riorganizzare in modo che è in forma

A = (x1 y2 - x2 y1) / 2 + (x2 Y3 - x3 y2) / 2 +. (X3 Y1 - x1y3) / 2

Ora il primo termine è il seguente zona, che è positiva nel nostro caso:

Se non è chiaro che l'area della regione verde è davvero (x1 y2 - x2 y1) / 2, allora continuate a leggere questo .

Il secondo termine è tale zona, che è di nuovo positivo:

E la terza area è mostrato nella figura seguente. Questa volta la zona è negativo

L'aggiunta di questi tre fino otteniamo la seguente immagine

Si vede che l'area verde che era al di fuori del triangolo viene annullato dal zona rossa, in modo che la superficie netta è solo l'area del triangolo, e questo dimostra il motivo per cui la nostra formula era vero in questo caso.

Quello che ho detto sopra è stata la spiegazione intuitiva sul perché la formula zona era corretta. Una spiegazione più rigoroso sarebbe quello di osservare che quando si calcola l'area da un bordo, l'area si ottiene è la stessa area che otterremmo dall'integrazione r ^ 2dθ / 2, in modo che siano effettivamente integrando r ^ 2dθ / 2 intorno al contorno del poligono, e teorema di stokes, questo dà lo stesso risultato integrando rdrdθ sopra la regione delimitata del poligono. Dal momento che l'integrazione rdrdθ sulla regione delimitata dal poligono dà l'area, concludiamo che la nostra procedura deve correttamente dare alla zona.

Area della intersezione di un cerchio con un poligono

Ora parliamo di come trovare l'area di intersezione di un cerchio di raggio R con un poligono come mostrato nella figura seguente:

Siamo interessati a trovare l'area della regione verde. Noi possiamo, proprio come nel caso del singolo poligono, rompere il nostro calcolo nel trovare uno spazio per ogni lato del poligono, e quindi aggiungere quelle aree in su.

La nostra prima area sarà simile:

La seconda area sarà simile

E la terza area sarà

Ancora una volta, i primi due settori sono positivi nel nostro caso, mentre il terzo sarà negativo. Speriamo che le cancellazioni si risolverà in modo che la superficie netta è infatti la zona che ci interessa. Vediamo.

In effetti, la somma delle aree sarà zona che ci interessa.

Ancora una volta, siamo in grado di dare una spiegazione più rigorosa del perché questo funziona. Sia I regione definita dall'intersezione e sia p il poligono. Poi dalla discussione precedente, sappiamo che vogliamo computer integrante del r ^ 2dθ /2 intorno al contorno di I. Tuttavia, questo difficile da fare perché è necessario trovare l'incrocio.

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

D'altra parte dato ¸ (θ) = θ, questo è lo stesso come l'integrazione π (r) ^ 2 dπ (θ) / 2 sul margine del poligono.

Ora facendo un cambio di variabili, troviamo che avremmo avuto la stessa risposta se abbiamo integrato r ^ 2 dO / 2 sopra il confine di π (P), dove π (P) è l'immagine di P sotto π.

Utilizzando Stokes teorema di nuovo noi sappiamo che l'integrazione r ^ 2 dO / 2 sopra il confine di π (P) ci dà l'area di π (P). In altre parole, dà la stessa risposta come l'integrazione dxdy sopra π (P).

Utilizzando un cambio di variabile ancora una volta, sappiamo che l'integrazione dxdy sopra π (P) è lo stesso di integrazione 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 punti nel cerchio sola e J = 1 lì, quindi il contributo da questa parte P è la zona della parte di P che si trova nel cerchio cioè l'area dell'intersezione. La seconda regione è la regione esterna al cerchio. Ci J = 0 poiché π crolla questa parte fino al confine del cerchio.

Quindi quello che noi calcoliamo è infatti l'area dell'intersezione.

Ora che siamo relativamente sicuri sappiamo concettualmente come trovare l'area, parliamo più specificamente su come calcolare il contributo di un singolo segmento. Cominciamo, cercando in un segmento in ciò che chiamerò "geometria standard". Si è mostrato di seguito.

In geometria standard, il bordo va orizzontalmente da sinistra a destra. Si è descritta da tre numeri: xi, l'ascissa cui il bordo inizia, xf, l'ascissa 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 essere attenti a segno. Vogliamo che l'area indicata per essere positivo in modo diremo la zona è - (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 superiore a Xint.

L'altro caso da considerare è | y | > R. Questo caso è più semplice, poiché v'è 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 bordo in geometria standard.

Ma questo solo un semplice cambiamento di coordinate. Dato un con vi vertice iniziale e finale vf vertice, il nuovo vettore unitario x sarà il versore punta da vi a vf. Poi xi è solo lo spostamento di vi dal centro del cerchio tratteggiato in x, ed è proprio xf xi più la distanza tra VI e VF. Nel frattempo y è dato dal prodotto del cuneo 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, dal momento che stiamo lavorando con i cerchi, dovremmo avere una classe cerchio

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ò classe Shape di Java. Shapes hanno un PathIterator che posso usare per scorrere i bordi del poligono.

Ora, per il lavoro effettivo. Io separare la logica di iterazione attraverso i bordi, mettendo i bordi in geometria standard, ecc, dalla logica di calcolare l'area una volta fatto questo. La ragione di questo è che si può desiderare in futuro per calcolare qualcos'altro oltre o in aggiunta alla zona e si vuole essere in grado di riutilizzare il codice avere a che fare con l'iterazione attraverso i bordi.

Così ho una classe generica che calcola alcune proprietà della classe T circa il nostro poligono cerchio intersezione.

public abstract class CircleShapeIntersectionFinder<T> {

Ha tre metodi statici che solo aiutano la geometria di calcolo:

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 istanza, una Circle che mantiene solo una copia del cerchio, e il currentSquareRadius, che mantiene una copia del raggio quadrato. Questo può sembrare strano, ma la classe che sto usando in realtà è attrezzato per trovare le aree di un'intera collezione di intersezioni cerchio-poligono. È per questo che mi riferisco a uno dei cerchi come "corrente".

private Circle currentCircle;
private double currentSquareRadius;

Poi viene il metodo per calcolare quello che vogliamo calcolare:

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

initialize() e getValue() sono astratti. initialize() avrebbe impostare la variabile che sta mantenendo un totale dell'area a zero, e getValue() sarebbe solo riportare l'area. La definizione di 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 guardare initializeForNewCirclePrivate rapidamente. Questo metodo solo imposta i campi di esemplare e consente la classe derivata per memorizzare qualsiasi proprietà del cerchio. La sua definizione è

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

initializeForNewCircle è astratta e un'implementazione sarebbe per esso per memorizzare il raggio cerchi per evitare di dover fare radici quadrate. Comunque, per ritornare processCircleShape. Dopo aver chiamato initializeForNewCirclePrivate, controlliamo se il poligono è null (che sto interpretando come un poligono vuoto), e torniamo se è null. In questo caso, la nostra area calcolata è pari a zero. Se il poligono non è null allora otteniamo la PathIterator del poligono. L'argomento al metodo getPathIterator chiamo è una trasformazione affine che può essere applicato al percorso. Non voglio applicare uno, però, quindi ho solo passo null.

Poi ho dichiarare le double[]s che terrà traccia dei vertici. Devo ricordarmi il primo vertice perché la PathIterator mi dà solo una volta ogni vertice, quindi devo tornare indietro dopo che mi ha dato l'ultimo vertice, e forma un bordo con questo ultimo vertice e il primo vertice.

Il metodo currentSegment sulla riga successiva mette il vertice successivo nella sua argomentazione. Esso restituisce un codice che ti dice quando si è fuori di vertici. Questo è il motivo per cui l'espressione di controllo per il mio ciclo while è quello che è.

La maggior parte del resto del codice di questo metodo è la logica priva di interesse relative al scorrendo i vertici. La cosa importante è che una volta per ogni iterazione del ciclo while chiamo processSegment e poi chiamo processSegment nuovo alla fine del metodo per elaborare il bordo che collega l'ultimo vertice al primo vertice.

Vediamo il 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. Prima a calcolare segmentDisplacement, lo spostamento dal vertice iniziale al vertice finale. Questo definisce l'asse x del standard geometry. Faccio un rapido ritorno se questo spostamento è pari a zero.

Dopo ho calcolare la lunghezza dello spostamento, perché questo è necessario per ottenere il vettore unitario x. Una volta che ho queste informazioni, calcolare lo spostamento dal centro del cerchio al vertice iniziale. Il prodotto scalare di questo con segmentDisplacement mi dà leftX cui ero stata chiamata xi. Poi rightX, che mi aveva chiamato XF, è solo leftX + segmentLength. Infine faccio prodotto cuneo per ottenere y come descritto sopra.

Ora che ho trasformato il problema in geometria standard, sarà facile da affrontare. Questo è ciò che il metodo processSegmentStandardGeometry fa. 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 piccola che il bordo può intersecare il cerchio. Se y è grande e non c'è possibilità di intersezione, quindi chiamo il metodo per gestire questo caso. Altrimenti gestire il caso in cui incrocio è possibile.

Se intersezione è possibile, a calcolare la coordinata x di intersezione, intersectionX, e divido il bordo in tre parti, che corrispondono alle regioni 1, 2 e 3 della figura geometria standard sopra. In primo luogo mi occupo regione 1.

Per gestire la regione 1, controllo se leftX è infatti inferiore a -intersectionX perché altrimenti non ci sarebbe regione 1. Se c'è una regione 1, quindi ho bisogno di sapere quando finisce. Si conclude al minimo rightX e -intersectionX. Dopo aver trovato questi ascisse, ho a che fare con questa regione non-intersezione.

che faccio una cosa simile per gestire regione 3.

Per la regione 2, devo fare un po 'di logica per controllare che leftX e rightX realtà non inquadrare qualche regione tra -intersectionX e intersectionX. Dopo aver trovato la regione, ho solo bisogno della lunghezza della regione e y, così mi passa questi due numeri a 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);
}

Ho semplicemente uso atan2 per calcolare la differenza in angolo tra leftX e rightX. Poi aggiungo il codice a che fare con la discontinuità in atan2, ma questo è probabilmente inutile, perché la discontinuità si verifica sia a 180 gradi o 0 gradi. Poi passo la differenza dell'angolo su un metodo astratto. Infine non ci resta che i metodi getter e astratti:

    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 classe che estende, 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) {

}

}

Ha un area campo per tenere traccia della zona. initialize imposta zona a zero, come previsto. Quando procediamo un bordo non intersecante, viene incrementato l'area da R ^ 2 Δθ / 2 come abbiamo concluso dovremmo sopra. Per un bordo di intersezione, si decrementa la zona in y*length/2. Questo è stato in modo che i valori negativi per y corrispondono ad aree positive, come abbiamo deciso che dovrebbero.

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

}

e ora abbiamo solo bisogno di estendere ancora una volta la nostra classe astratta utilizzando AreaPerimeter come tipo.

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

}

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

Per avere un riferimento qui è il codice pieno 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;
    }

In ogni caso, questa è la mia descrizione dell'algoritmo. Penso che sia bello perché èesatto e non ci sono poi così tanti casi da controllare.

Answer 3

Sono quasi un anno e mezzo di ritardo, ma ho pensato che forse la gente sarà interessato a il codice qui che ho scritto che penso fa questo in modo corretto. Guardate nella funzione IntersectionArea vicino al fondo. L'approccio generale è quello di scegliere il disegno del poligono convesso circoscritto dal cerchio, e poi trattare con i piccoli tappi circolari.

Answer 4

Supponendo che si sta parlando pixel interi, non reale, l'attuazione ingenuo sarebbe quello di scorrere ogni pixel del triangolo e controllare la distanza dal centro del cerchio contro il suo raggio.

Non è una formula carina, o particolarmente veloce, ma lo fa ottenere il lavoro fatto.

Answer 5

geometria computazionale

Nota: questo non è un problema banale, mi auguro che non è compito; -)

Answer 6

Se si dispone di una GPU a vostra disposizione, è possibile utilizzare questa tecnica per ottenere un numero di pixel del dell'intersezione ..

Answer 7

Credo che non si dovrebbe cerchio approssimativo come un insieme di triangoli, invece di che si può approssimare la sua forma con un poligono. L'algoritmo ingenuo può apparire come:

1. convertirvi cerchio per poligono con un numero desiderato di vertici.
2. Calcola l'intersezione di due poligoni (cerchio convertito e un triangolo).
3. Calcola quadrato di quell'incrocio.

È possibile ottimizzare questo algoritmo, combinando i passaggi 2 e 3 in un'unica funzione.

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

Answer 8

Dal momento che le forme sono convesse, è possibile utilizzare la stima dell'area di Monte Carlo.

Disegnare un riquadro attorno al cerchio e triangolo.

Scegli punti casuali nella scatola e tenere un conteggio di quanti si trovano nel cerchio, e quanti si trovano sia nel cerchio e triangolo.

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

Smettere di scelta punti quando la superficie stimata non varia di più di una certa quantità nel corso di un certo numero di giri, o semplicemente scegliere un numero fisso di punti sulla base della superficie della scatola. La stima area dovrebbe convergere piuttosto veloce a meno che una delle tue forme ha molto poco spazio.

Nota: Ecco come si determina se un punto è in un triangolo: baricentriche coordinate

Answer 9

Come esatto avete bisogno di essere? Se si può approssimare il cerchio con forme più semplici, è possibile semplificare il problema. Non sarebbe difficile da modellare un cerchio come un insieme di triangoli molto strette che soddisfano al centro, per esempio.

Answer 10

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

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. Si noti che questa soluzione si rompe se più della metà del cerchio è tagliato fuori.

E 'probabilmente non vale la pena se avete solo bisogno di un'approssimazione, dal momento che rende diverse ipotesi su ciò che l'intersezione attuale assomiglia.

Answer 11

Il mio primo istinto sarebbe quello di trasformare il tutto in modo che il cerchio è centrato su origine, trans sul triangolo a coordinate polari, e risolvere per l'intersezione (o encompassment) del triangolo con il cerchio. Non ho effettivamente lavorato attraverso su carta ma anche se così che è solo una supposizione.