área de intersección de dos triángulos, o un conjunto de medios planos, o área de un conjunto de puntos convexos

Necesito calcular el área de la región de superposición entre dos triángulos en el plano 2D. Curiosamente, he escritocódigo Para elproblema triángulo-círculo, y eso funciona bastante bien y de manera robusta, pero tengo problemas con el problema triángulo-triángulo.

Ya compruebo primero para ver si uno contiene el otro por completo, o si el otro contiene el primero, así como obtener todos los puntos de intersección en el borde. Estos puntos de intersección (hasta 6, como en la estrella de David), combinados con los vértices del triángulo que están contenidos dentro del otro triángulo, son los vértices de la región de intersección. Estos puntos deben formar un polígono convexo.

La solución que busco es la respuesta a cualquiera de estas preguntas:

Dado un conjunto de puntos conocidos portodas Acuéstese en el casco convexo del conjunto de puntos, calcule el área del casco convexo. Tenga en cuenta que están en orden aleatorio.Dado un conjunto de semiplanos, determine el área de intersección. Esto es equivalente a describir ambos triángulos como la intersección de tres semiplanos y calcular la solución como la intersección directa de esta descripción.

He considerado la pregunta 1 simplemente sumando todas las áreas de todos los triángulos posibles, y luego dividiendo por la multiplicidad en el conteo, pero eso parece tonto, y no estoy seguro de si es correcto. Siento que hay algún tipo de algoritmo de línea de barrido que haría el truco. Sin embargo, la solución también debe ser relativamente robusta numéricamente.

Simplemente no tengo idea de cómo resolver la pregunta 2, pero una respuesta general sería muy útil, y proporcionar código me alegraría el día. Esto permitiría el cálculo directo de las áreas de intersección de polígonos convexos en lugar de tener que realizar una descomposición triangular en ellos.

Editar: Estoy consciente deEste artículo que describe el caso general para encontrar el polígono de intersección de dos polígonos convexos. Parece bastante complicado solo para triángulos, y además, realmente no necesito el polígono resultante. Entonces, tal vez esta pregunta se haga con pereza en este momento.