Calcule a área de intersecção entre um círculo e um triângulo?

Como se calcula a área de intersecção entre um triângulo (especificado como três pares (X, Y)) e um círculo (X, Y, R)? Eu fiz algumas pesquisas sem sucesso. Isto é para o trabalho, não para a escola. 🙂

Seria algo parecido com isso em 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 você quiser uma solução exata (ou pelo menos tão exata quanto puder usando a aritmética de ponto flutuante), isso envolverá muito trabalho de campo, porque há muitos casos a serem considerados.

Eu conto nove casos diferentes (categorizados na figura abaixo pelo número de vértices do triângulo dentro do círculo, e o número de arestas do triângulo que se cruzam ou estão contidos no círculo):

Nove casos para intersecção: 1, 2. sem vértices, sem arestas; 3. sem vértices, uma borda; 4. sem vértices, duas arestas; 5. sem vértices, três arestas; 6. um vértice, duas arestas; 7. um vértice, três arestas; 8. dois vértices, três arestas; 9. três vértices, três arestas.

(No entanto, esse tipo de enumeração de casos geométricos é bem conhecido por ser complicado, e não me surpreenderia se eu perdesse um ou dois!)

Então a abordagem é:

  1. Determine para cada vértice do triângulo se ele está dentro do círculo. Eu vou assumir que você sabe como fazer isso.

  2. Determine para cada aresta do triângulo se ele cruzar o círculo. (Escrevi um método aqui ou consulte qualquer livro de geometry computacional.) Você precisará calcular o ponto ou pontos de interseção (se houver) para usar na etapa 4.

  3. Determine qual dos nove casos você tem.

  4. Calcule a área da interseção. Os casos 1, 2 e 9 são fáceis. Nos seis casos restantes, desenhei linhas tracejadas para mostrar como particionar a área de interseção em triângulos e segmentos circulares com base nos vértices originais do triângulo e nos pontos de interseção computados na etapa 2.

Esse algoritmo será bastante delicado e propenso a erros que afetam apenas um dos casos, portanto, certifique-se de ter casos de teste que cubram todos os nove casos (e sugiro que também sejam permutados os vértices dos triângulos de teste). Preste especial atenção aos casos em que um dos vértices do triângulo está na borda do círculo.

Se você não precisa de uma solução exata, então rasterizar as figuras e contar os pixels na interseção (como sugerido por um par de outros entrevistados) parece ser uma abordagem muito mais fácil de codificar, e correspondentemente menos propensa a erros.

Primeiro, vou nos lembrar como encontrar a área de um polígono. Uma vez feito isso, o algoritmo para encontrar a interseção entre um polígono e um círculo deve ser fácil de entender.

Como encontrar a área de um polígono

Vejamos o caso de um triângulo, porque toda a lógica essencial aparece lá. Vamos supor que temos um triângulo com vértices (x1, y1), (x2, y2) e (x3, y3) conforme você passa pelo triângulo no sentido anti-horário, como mostra a figura a seguir: triangleFigure

Então você pode calcular a área pela fórmula

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

Para ver por que essa fórmula funciona, vamos reorganizá-la para que fique na forma

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

Agora o primeiro termo é a seguinte área, o que é positivo no nosso caso: insira a descrição da imagem aqui

Se não está claro que a área da região verde é de fato (x1 y2 – x2 y1) / 2, então leia isto .

O segundo termo é essa área, que é novamente positiva:

insira a descrição da imagem aqui

E a terceira área é mostrada na figura a seguir. Desta vez a área é negativa

insira a descrição da imagem aqui

Adicionando estes três nós obtemos a seguinte imagem

insira a descrição da imagem aqui

Vemos que a área verde que estava fora do triângulo é cancelada pela área vermelha, de modo que a área da rede é apenas a área do triângulo, e isso mostra por que nossa fórmula era verdadeira neste caso.

O que eu disse acima foi a explicação intuitiva de por que a fórmula da área estava correta. Uma explicação mais rigorosa seria observar que quando calculamos a área a partir de uma aresta, a área que obtemos é a mesma área que obteríamos da integração r ^ 2dθ / 2, então estamos efetivamente integrando r ^ 2dθ / 2 ao redor da fronteira. do polígono, e pelo teorema stokes, isso dá o mesmo resultado que integrar rdrdθ sobre a região delimitada pelo polígono. Como a integração de rdrdθ sobre a região delimitada pelo polígono dá a área, concluímos que nosso procedimento deve dar corretamente a área.

Área da intersecção de um círculo com um polígono

Agora vamos discutir como encontrar a área da interseção de um círculo de raio R com um polígono, como mostra a figura a seguir:

insira a descrição da imagem aqui

Estamos interessados ​​em encontrar a área da região verde. Podemos, assim como no caso do polígono único, dividir nosso cálculo em encontrar uma área para cada lado do polígono e depois adicionar essas áreas.

Nossa primeira área será parecida com: insira a descrição da imagem aqui

A segunda área será semelhante insira a descrição da imagem aqui

E a terceira área será insira a descrição da imagem aqui

Novamente, as duas primeiras áreas são positivas no nosso caso, enquanto a terceira será negativa. Espero que os cancelamentos funcionem para que a área líquida seja de fato a área em que estamos interessados. Vamos ver.

insira a descrição da imagem aqui

De fato, a sum das áreas será a área em que estamos interessados.

Mais uma vez, podemos dar uma explicação mais rigorosa do porquê isso funciona. Seja a região definida pela interseção e seja P o polígono. Então, a partir da discussão anterior, sabemos que queremos computar a integral de r ^ 2dθ / 2 ao redor do limite de I. No entanto, isso é difícil, porque requer encontrar a interseção.

Em vez disso, fizemos uma integral sobre o polígono. Nós integramos max (r, R) ^ 2 dθ / 2 sobre o limite do polígono. Para ver por que isso dá a resposta correta, vamos definir uma function que toma um ponto em coordenadas polares (r, θ) até o ponto (max (r, R), θ). Não deve ser confuso referir-se às funções de coordenadas de π (r) = max (r, R) e π (θ) = θ. Então o que fizemos foi integrar π (r) ^ 2 dθ / 2 sobre o limite do polígono.

Por outro lado, como π (θ) = θ, isso é o mesmo que integrar π (r) ^ 2 dπ (θ) / 2 sobre o limite do polígono.

Agora, fazendo uma mudança de variável, descobrimos que obteríamos a mesma resposta se integramos r ^ 2 dθ / 2 sobre o limite de π (P), onde π (P) é a imagem de P sob π.

Usando novamente o teorema de Stokes, sabemos que a integração de r ^ 2 dθ / 2 sobre o limite de π (P) nos dá a área de π (P). Em outras palavras, dá a mesma resposta que integrar dxdy sobre π (P).

Usando uma mudança de variável novamente, sabemos que integrar dxdy sobre π (P) é o mesmo que integrar Jdxdy sobre P, onde J é o jacobiano de π.

Agora podemos dividir a integral de Jdxdy em duas regiões: a parte no círculo e a parte fora do círculo. Agora, π deixa pontos no círculo sozinho, de modo que J = 1 ali, então a contribuição dessa parte de P é a área da parte de P que está no círculo, isto é, a área da interseção. A segunda região é a região fora do círculo. Há J = 0, já que π recolhe essa parte até o limite do círculo.

Assim, o que calculamos é de fato a área da interseção.

Agora que estamos relativamente certos de que sabemos conceitualmente como encontrar a área, vamos falar mais especificamente sobre como calcular a contribuição de um único segmento. Vamos começar olhando para um segmento no que chamarei de “geometry padrão”. É mostrado abaixo.

insira a descrição da imagem aqui

Na geometry padrão, a borda vai horizontalmente da esquerda para a direita. É descrito por três números: xi, a coordenada x onde a aresta começa, xf, a coordenada x onde a aresta termina e y, a coordenada y da aresta.

Agora vemos que se | y |

A área da região 2 é apenas a área de um triângulo. No entanto, devemos ter cuidado com o sinal. Queremos que a área mostrada seja positiva, então diremos que a área é – (xint – (-xint)) y / 2.

Outra coisa a ter em mente é que, em geral, o xi não precisa ser menor que -xint e o xf não precisa ser maior que xint.

O outro caso a considerar é | y | > R. Este caso é mais simples, porque existe apenas uma peça que é semelhante à região 1 na figura.

Agora que sabemos como calcular a área a partir de uma aresta na geometry padrão, a única coisa que resta a fazer é descrever como transformar qualquer aresta em geometry padrão.

Mas isso é apenas uma simples mudança de coordenadas. Dados alguns com vértice inicial vi e vértice final vf, o novo vetor unitário x será o vetor unitário apontando de vi para vf. Então xi é apenas o deslocamento de vi do centro do círculo pontilhado em x, e xf é apenas xi mais a distância entre vi e vf. Enquanto isso, y é dado pelo produto de cunha de x com o deslocamento de vi do centro do círculo.

Código

Isso completa a descrição do algoritmo, agora é hora de escrever algum código. Vou usar java.

Primeiramente, como estamos trabalhando com círculos, devemos ter uma turma de círculos

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

Para polígonos, usarei a class Shape do java. Shape s tem um PathIterator que eu posso usar para percorrer as bordas do polígono.

Agora para o trabalho real. Vou separar a lógica de iterar pelas bordas, colocando as bordas na geometry padrão, etc., a partir da lógica de computação da área, uma vez que isso seja feito. A razão para isso é que você pode no futuro querer computar outra coisa além ou além da área e você deseja poder reutilizar o código tendo que lidar com a iteração pelas bordas.

Então, eu tenho uma class genérica que calcula alguma propriedade da class T sobre nossa interseção de polígonos.

public abstract class CircleShapeIntersectionFinder {

Tem três methods estáticos que apenas ajudam a calcular a geometry:

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

Existem dois campos de instância, um Circle que apenas mantém uma cópia do círculo e o currentSquareRadius , que mantém uma cópia do raio quadrado. Isso pode parecer estranho, mas a class que estou usando está realmente equipada para encontrar as áreas de uma coleção inteira de interseções círculo-polígono. É por isso que estou me referindo a um dos círculos como “atual”.

 private Circle currentCircle; private double currentSquareRadius; 

Em seguida vem o método para calcular o que queremos computar:

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

initialize() e getValue() são abstratos. initialize() definiria a variável que mantém um total da área como zero e getValue() retornaria a área. A definição de 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); } 

Vamos dar um segundo para ver o initializeForNewCirclePrivate rapidamente. Esse método apenas define os campos de instância e permite que a class derivada armazene qualquer propriedade do círculo. Sua definição é

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

initializeForNewCircle é abstrato e uma implementação seria armazenar o raio dos círculos para evitar ter raízes quadradas. De qualquer forma de volta ao processCircleShape . Depois de chamar initializeForNewCirclePrivate , verificamos se o polígono é null (o qual estou interpretando como um polígono vazio) e retornamos se é null . Nesse caso, nossa área computada seria zero. Se o polígono não for null , obtemos o PathIterator do polígono. O argumento para o método getPathIterator que eu chamo é uma transformação afim que pode ser aplicada ao caminho. Eu não quero aplicar um, então eu apenas passo null .

Em seguida eu declaro o double[] s que irá acompanhar os vértices. Eu devo lembrar o primeiro vértice porque o PathIterator só me dá cada vértice uma vez, então eu tenho que voltar depois que ele me deu o último vértice, e formar uma aresta com este último vértice e o primeiro vértice.

O método currentSegment na próxima linha coloca o próximo vértice em seu argumento. Ele retorna um código que informa quando ele está fora dos vértices. É por isso que a expressão de controle para o meu loop while é o que é.

A maior parte do restante do código desse método é uma lógica desinteressante relacionada à iteração pelos vértices. O importante é que, uma vez por iteração do loop while, chamo processSegment e, em seguida, chamo processSegment novamente no final do método para processar a aresta que conecta o último vértice ao primeiro vértice.

Vamos ver o código do 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); } 

Neste método, eu implemento as etapas para transformar uma aresta na geometry padrão, conforme descrito acima. Primeiro eu calculo segmentDisplacement , o deslocamento do vértice inicial para o vértice final. Isso define o eixo x da geometry padrão. Eu faço um retorno antecipado se esse deslocamento for zero.

Em seguida, calculo o comprimento do deslocamento, porque isso é necessário para obter o vetor unitário x. Uma vez que eu tenha essa informação, eu calculo o deslocamento do centro do círculo para o vértice inicial. O produto de ponto disto com segmentDisplacement me dá leftX que eu estava chamando de xi. Então rightX , que eu estava chamando de xf, é apenas leftX + segmentLength . Finalmente eu faço o produto de cunha para obter y como descrito acima.

Agora que eu transformei o problema na geometry padrão, será fácil lidar com ele. Isso é o que o método processSegmentStandardGeometry faz. Vamos olhar o código

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

O primeiro if distingue dos casos em que y é pequeno o suficiente para que a borda possa cruzar o círculo. Se y for grande e não houver possibilidade de interseção, chamo o método para lidar com esse caso. Caso contrário, eu lido com o caso em que a interseção é possível.

Se a interseção for possível, calculo a coordenada x da interseção, intersectionX X, e divido a aresta em três partes, que correspondem às regiões 1, 2 e 3 da figura da geometry padrão acima. Primeiro eu manejo a região 1.

Para lidar com a região 1, eu verifico se leftX é de fato menor que -intersectionX caso contrário, não haveria região 1. Se houver uma região 1, preciso saber quando ela termina. Ele termina no mínimo de rightX e -intersectionX . Depois de encontrar essas coordenadas x, eu lido com essa região sem interseção.

Eu faço uma coisa semelhante para lidar com a região 3.

Para a região 2, eu tenho que fazer alguma lógica para verificar se leftX e rightX realmente fazem o bracket em alguma região entre -intersectionX e intersectionX . Depois de encontrar a região, eu só preciso do comprimento da região y , então eu passo esses dois números para um método abstrato que lida com a região 2.

Agora vamos olhar o código para 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); } 

Eu simplesmente uso o atan2 para calcular a diferença no ângulo entre o leftX e o rightX . Então eu adiciono código para lidar com a descontinuidade em atan2 , mas isso é provavelmente desnecessário, porque a descontinuidade ocorre a 180 graus ou 0 graus. Então eu passo a diferença no ângulo em um método abstrato. Por fim, temos apenas methods abstratos e 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; } } 

Agora vamos ver a class de extensão, 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) { } 

}

Tem uma area campo para acompanhar a área. initialize área de conjuntos para zero, conforme esperado. Quando processamos uma aresta não intersectada, incrementamos a área por R ^ 2 Δθ / 2 conforme concluímos que deveríamos acima. Para uma borda de interseção, diminuímos a área por y*length/2 . Isto foi assim que valores negativos para y correspondem a áreas positivas, como decidimos que deveriam.

Agora, o melhor é que, se quisermos acompanhar o perímetro, não precisamos fazer muito mais trabalho. Eu defini uma 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 agora só precisamos estender nossa class abstrata novamente usando AreaPerimeter como o 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); } } 

Temos um perimeter variável para manter o controle do perímetro, lembramos o valor do radius para evitar ter que chamar muito o Math.sqrt e delegamos o cálculo da área ao nosso CircleAreaFinder . Podemos ver que as fórmulas para o perímetro são fáceis.

Para referência, aqui está o código completo de CircleShapeIntersectionFinder

 private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) { return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]}; } private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) { return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0]; } static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) { return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1]; } private Circle currentCircle; private double currentSquareRadius; public final T computeValue(Circle circle, Shape shape) { initialize(); processCircleShape(circle, shape); return getValue(); } private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) { initializeForNewCirclePrivate(circle); if (cellBoundaryPolygon == null) { return; } PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null); double[] firstVertex = new double[2]; double[] oldVertex = new double[2]; double[] newVertex = new double[2]; int segmentType = boundaryPathIterator.currentSegment(firstVertex); if (segmentType != PathIterator.SEG_MOVETO) { throw new AssertionError(); } System.arraycopy(firstVertex, 0, newVertex, 0, 2); boundaryPathIterator.next(); System.arraycopy(newVertex, 0, oldVertex, 0, 2); segmentType = boundaryPathIterator.currentSegment(newVertex); while (segmentType != PathIterator.SEG_CLOSE) { processSegment(oldVertex, newVertex); boundaryPathIterator.next(); System.arraycopy(newVertex, 0, oldVertex, 0, 2); segmentType = boundaryPathIterator.currentSegment(newVertex); } processSegment(newVertex, firstVertex); } private void initializeForNewCirclePrivate(Circle circle) { currentCircle = circle; currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius(); initializeForNewCircle(circle); } private void processSegment(double[] initialVertex, double[] finalVertex) { double[] segmentDisplacement = displacment2D(initialVertex, finalVertex); if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) { return; } double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement)); double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()}; final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength; final double rightX = leftX + segmentLength; final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength; processSegmentStandardGeometry(leftX, rightX, y); } private void processSegmentStandardGeometry(double leftX, double rightX, double y) { if (y * y > getCurrentSquareRadius()) { processNonIntersectingRegion(leftX, rightX, y); } else { final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y); if (leftX < -intersectionX) { final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX); processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y); } if (intersectionX < rightX) { final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX); processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y); } final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX); final double middleRegionRightEndpoint = Math.min(intersectionX, rightX); final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0); processIntersectingRegion(middleRegionLength, y); } } private void processNonIntersectingRegion(double leftX, double rightX, double y) { final double initialTheta = Math.atan2(y, leftX); final double finalTheta = Math.atan2(y, rightX); double deltaTheta = finalTheta - initialTheta; if (deltaTheta < -Math.PI) { deltaTheta += 2 * Math.PI; } else if (deltaTheta > Math.PI) { deltaTheta -= 2 * Math.PI; } processNonIntersectingRegion(deltaTheta); } protected abstract void initialize(); protected abstract void initializeForNewCircle(Circle circle); protected abstract void processNonIntersectingRegion(double deltaTheta); protected abstract void processIntersectingRegion(double length, double y); protected abstract T getValue(); protected final Circle getCurrentCircle() { return currentCircle; } protected final double getCurrentSquareRadius() { return currentSquareRadius; } 

De qualquer forma, essa é a minha descrição do algoritmo. Eu acho que é legal porque é exato e não há muitos casos para checar.

Estou quase um ano e meio atrasado, mas achei que talvez as pessoas estivessem interessadas em código aqui que escrevi, o que acho que faz isso corretamente. Olhe na function IntersectionArea na parte inferior. A abordagem geral é retirar o polígono convexo circunscrito pelo círculo e depois lidar com as pequenas tampas circulares.

Supondo que você esteja falando de pixels inteiros, não reais, a implementação ingênua seria percorrer cada pixel do triângulo e verificar a distância do centro do círculo em relação ao seu raio.

Não é uma fórmula fofa ou particularmente rápida, mas faz o trabalho.

tente geometry computacional

Nota: este não é um problema trivial, espero que não seja dever de casa 😉

Se você tiver uma GPU à sua disposição, você pode usar essa técnica para obter uma contagem de pixels da interseção.

Acho que você não deve aproximar o círculo como um conjunto de triângulos, em vez de poder aproximar sua forma com um polígono. O algoritmo ingênuo pode se parecer com:

  1. Converta seu círculo em polígono com um número desejado de vértices.
  2. Calcule a interseção de dois polígonos (círculo convertido e um triângulo).
  3. Calcule o quadrado desse cruzamento.

Você pode otimizar esse algoritmo combinando a etapa 2 e a etapa 3 em uma única function.

Leia os links abaixo:
Área do polígono convexo
Intersecção de polígonos convexos

Como suas formas são convexas, você pode usar a estimativa de área de Monte Carlo.

Desenhe uma checkbox ao redor do círculo e triângulo.

Escolha pontos randoms na checkbox e mantenha uma contagem de quantos caem no círculo e quantos caem no círculo e no triângulo.

Área de interseção ≅ Área do círculo * # pontos no círculo e triângulo / # pontos no círculo

Pare de escolher pontos quando a área estimada não mudar em mais do que uma certa quantia em um certo número de rodadas, ou apenas escolha um número fixo de pontos baseado na área da checkbox. A estimativa da área deve convergir rapidamente, a menos que uma de suas formas tenha uma área muito pequena.

Nota: Veja como você determina se um ponto está em um triângulo: Coordenadas baricêntricas

Quão exata você precisa ser? Se você puder aproximar o círculo com formas mais simples, poderá simplificar o problema. Não seria difícil modelar um círculo como um conjunto de triângulos muito estreitos que se encontram no centro, por exemplo.

Se apenas um dos segmentos de linha do triângulo cruzar o círculo, a solução matemática pura não é muito difícil. Depois de saber quando os dois pontos de interseção estão, você pode usar a fórmula de distância para encontrar o comprimento do acorde.

De acordo com estas equações :

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

where c is the chord length, r is the radius, ϑ becomes the angle through the center, and A is the 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.