Encontrar el área de superposición de dos triángulos

Question

Supongamos que tenemos dos triángulos $ABC$$DEF$. Podemos asumir nada acerca de ellos, otros que están en el mismo plano. Los triángulos pueden o no pueden superponerse. Quiero algorítmicamente determinar el área (posiblemente $0$) de su superposición; llamarlo $T_{common}$.

Tenemos una multitud de maneras de determinar las zonas de $ABC$$DEF$; entre los "mejores" son los Heronian fórmula, que es en términos de las longitudes de los lados solo, y

$T = \frac{1}{2} \left| \det\begin{pmatrix}x_A & x_B & x_C \\ y_A & y_B & y_C \\ 1 & 1 & 1\end{pmatrix} \right| = \frac{1}{2} \big| x_A y_B - x_A y_C + x_B y_C - x_B y_A + x_C y_A - x_C y_B \big|$

que es, en términos de las coordenadas solo.

Obviamente, no existe una función de$A,B,C,D,E,F$$T_{common}$, pero mi pregunta es: ¿hay una "buena" (o no-"agradable"), la expresión para $T_{common}$ en términos de la $x$ $y$ coordenadas de $A,B,C,D,E,F$?

He dibujado en el papel, lo que yo creo que son casos distintos, pero mis problemas con este enfoque son: la identificación de los casos es un trabajo en sí mismo, que no puedo ver fácilmente cómo algorithmise ("basta con ver una imagen de" no trabajo para un equipo); incluso dentro de cada caso, el álgebra es complejo y propenso a errores; y tengo poca confianza que he enumerado todos los casos posibles y se metió los cálculos de la derecha!

En mi imaginación no es un buen enfoque el uso de las ideas de análisis (el tratamiento de los triángulos como funciones de $\mathbb{R}^2$ $\{0,1\}$y... la multiplicación de ellos????) pero no tengo idea de si eso es sólo una fantasía o algo viable.

Answer 1

Aquí es un enfoque que no requiere ningún análisis ingenio o caso. Utilizar el algoritmo Sutherland Hodgman para recortar un triángulo contra el otro, cediendo un polígono (posiblemente degenerado) representando a la región de superposición, a continuación, calcular su área.

Answer 2

Lo siento por el comentario ... me pulsar la tecla de retorno antes de tiempo.

Esto no es realmente una respuesta (excepto en el sentido negativo).

El común (solapamiento) área es una función de las coordenadas de los 6 puntos, por lo que es una asignación de $R^{12}$ a $R$. Pensar acerca de uno de los puntos de moverse, mientras que los otros 5 son fijos. Cuando el punto en movimiento pasa a (o de) el otro triángulo, algunas de las derivadas parciales de la función del área será discontinua (esto parece intuitivamente claro ... la prueba está a la izquierda para alguien que tiene más habilidad y paciencia que yo). De todos modos, si me crees, esto significa que la función del área no es suave. Por lo tanto, no puede ser algo simple fórmula como fórmula de Herón que da a la zona (porque esta simple fórmula sería dar una función suave).

Answer 3

Aquí es un comienzo. Degenerados de los casos no será tratado.

Vamos ${\bf a}_i$ $\,(i=0,1,2)$ ser los vértices de la primera, llamada $A$-triángulo, y lo mismo vamos ${\bf b}_k$ $\,(k=0,1,2)$ ser los vértices de la $B$-triángulo. Podría ayudar a suponer que los dos triángulos son de orientación positiva, es decir, $({\bf a}_1-{\bf a_0})\wedge({\bf a}_2-{\bf a_0})>0$, y lo mismo para las ${\bf b}_k$.

Luego de la prolongada lados de la $A$-triángulo está dada por $$g_i:\quad s\mapsto (1-s){\bf a}_{i-1}+ s\,{\bf a}_i\qquad(-\infty<s<\infty)\ ,$$ y del mismo modo que la prolongación de los lados de la $B$-triángulo está dada por $$h_k:\quad t\mapsto (1-t){\bf b}_{k-1}+ t\,{\bf b}_k\qquad(-\infty<t<\infty)\ .$$

Tenga en cuenta que la intersección de los dos triángulos que se podría tener de $0$ $6$vértices. Por lo tanto, no es demasiado trabajo para determinar los valores de los parámetros $(s_{ik},t_{ik})$ de los nueve puntos de intersección ${\bf z}_{ik}:=g_i\wedge h_k$.

Ahora viene la parte difícil: Dejar $I:=[0,1]$. Un punto de ${\bf z}_{ik}$ es un punto de intersección de una $A$-lado con un $B$-lado iff $(s_{ik},t_{ik})\in I\times I$. Por el dibujo de unas cuantas figuras debe ser posible encontrar un algoritmo que decide si (i) uno de los triángulos está contenida en la otra, o (ii) no son más que mentiras aparte, o (iii) se intersecan en un polígono convexo $P$. En el último caso, debe ser posible obtener automáticamente las direcciones $(i_r,k_r)$ $\,(1\leq r\leq n)$ de $P$'s de los vértices en sentido contrario de la orden.

Cuando estamos tan lejos podemos poner $${\bf z}_r:=\bigl(1-s_{i_r k_r}\bigr){\bf a}_{i_r-1}+s_{i_r k_r}{\bf a}_{i_r}\qquad(1\leq r\leq n)$$ y el uso de la bien conocida fórmula (derivado del Verde del área de fórmula) para el área de $P={\rm conv}({\bf z}_,\ldots,{\bf z}_n)$.

Answer 4

He aquí una manera de pensar acerca del problema que podría ayudar.

Cada lado de un triángulo se define una línea infinita, y esta línea divide el plano en dos mitades (llamado "la mitad de los espacios"). Así, por ejemplo, el lado de la $AB$ define una línea de $L_{AB}$ con la ecuación de $L_{AB}(x,y) = 0$. Los dos correspondientes a la mitad en los espacios de se $L_{AB}(x,y) \le 0$$L_{AB}(x,y) \ge 0$. Usted puede multiplicar la línea de la ecuación de $-1$, si es necesario, y de esta manera organizar que el triángulo en realidad se encuentra en la mitad de espacio -$L_{AB}(x,y) \ge 0$.

Entonces, el triángulo $ABC$ es la intersección de las tres de la mitad de los espacios de: $L_{AB}(x,y) \ge 0$, $L_{BC}(x,y) \ge 0$, $L_{CA}(x,y) \ge 0$.

La intersección de los dos triángulos es la intersección de las 6 de la mitad de los espacios.

O, dicho en otra forma, la intersección es el conjunto de puntos de $(x,y)$ para que todos los seis de $L_{AB}(x,y)$ a través de $L_{DF}(x,y)$ son positivos. Por lo tanto, si definimos $f(x,y) = \min\{L_{AB}(x,y), \ldots, L_{DF}(x,y)\}$, entonces el triángulo es el conjunto $\{(x,y) : f(x,y) \ge 0\}$.

No creo que nada de esto es muy útil computacionalmente. Pero, proporciona una manera de enumerar los casos, y que convierte el problema en una "función" basada en uno, tal como lo sugiere su vuelo de la fantasía.