Preciso calcular a área da região de sobreposição entre dois triângulos no plano 2D. Estranhamente, eu escrevicódigo para oproblema do triângulo-círculo, e isso funciona muito bem e com robustez, mas tenho problemas com o problema triângulo-triângulo.

Eu já verifico primeiro se um contém totalmente o outro, ou se o outro contém o primeiro, bem como obtenho todos os pontos de interseção em arestas. Esses pontos de interseção (até 6, como na estrela de David), combinados com os vértices do triângulo contidos no outro triângulo, são os vértices da região de interseção. Esses pontos devem formar um polígono convexo.

A solução que eu procuro é a resposta para uma dessas perguntas:

Dado um conjunto de pontos conhecidos portudo deitada no casco convexo do conjunto de pontos, calcule a área do casco convexo. Observe que eles estão em ordem aleatória.Dado um conjunto de semiplanos, determine a área de interseção. Isso equivale a descrever os dois triângulos como a interseção de três semiplanos e computar a solução como a interseção direta dessa descrição.

Eu considerei para a questão 1 simplesmente somar todas as áreas de todos os triângulos possíveis e depois dividir pela multiplicidade na contagem, mas isso parece idiota, e não tenho certeza se está correto. Sinto que existe algum tipo de algoritmo de varredura que faria o truque. No entanto, a solução também deve ser relativamente numericamente robusta.

Eu simplesmente não tenho idéia de como resolver a questão 2, mas uma resposta geral seria muito útil e fornecer código faria o meu dia. Isso permitiria o cálculo direto de áreas de interseção de polígonos convexos em vez de ter que realizar uma decomposição de triângulo neles.

Editar: Estou cienteEste artigo que descreve o caso geral para encontrar o polígono de interseção de dois polígonos convexos. Parece bastante envolvido por apenas triângulos e, além disso, eu realmente não preciso do polígono resultante. Talvez essa pergunta seja feita apenas com preguiça neste momento.