Aparte de la observación de que los dos métodos parecen ser (o más bien debería ser equivalente,
el uso de la triangulación de Delaunay, sin el desvío de Voronoi, parece ser el más sencillo.
Además es más conveniente determinar primero la integral sobre
uno (Delaunay) triángulo y luego simplemente la suma sobre todos los triángulos;
nada se gana con la recopilación de los triángulos en el mismo vértice, por la razón de que la suma de los números pueden estar en cualquier orden.
Formulación precisa para un triángulo $\Delta$ con vértices $(x_1,y_1),(x_2,y_2),(x_3,y_3)$
y los valores de la función $(f_1,f_2,f_3)$ en estos vértices (en caso de que no lo saben ya):
$$
\iint_{\Delta} f(x,y)\,dx\,dy = \frac{1}{2}
\det\begin{bmatrix} (x_2-x_1) & (x_3-x_1) \\ (y_2-y_1) & (y_3-y_1) \end{bmatrix}
\frac{f_1+f_2+f_3}{3}
$$
A continuación, suma sobre todos los triángulos en el dominio de / malla $\Omega$ :
$$
\iint_{\Omega} f(x,y)\,dx\,dy = \sum_{\Delta} \iint_{\Delta} f(x,y)\,dx\,dy
$$
Y eso es todo. Así que me gustaría votar por su enfoque, aparte de pequeños detalles.
Hacia los lados de la nota. En realidad, triángulos de Delaunay y regiones de Voronoi son
doble el uno al otro.
El antiguo concepto es el más favorito de los Métodos de elementos Finitos, mientras que el segundo concepto es el más favorito con Diferencia Finita/Volumen métodos. Mi sesgo personal es la unificación de ambos;
Las regiones de Voronoi son, en la página 13 en la siguiente referencia :
2-D De Primaria De Las Subestructuras .
Delaunay y regiones de Voronoi.
![enter image description here]()
- Imagen de la izquierda: (Delaunay) triángulo con medias
y regiones tentativamente llamado Delaunay regiones
(con la esperanza de que esta nomenclatura no ha sido reclamado ya en algún sitio)
- La imagen de la derecha: el mismo triángulo con la perpendicular
bisectrices y las regiones de Voronoi
Es fácil mostrar que el área de un Delaunay región es $1/3 \times$
el área de la (Delaunay) del triángulo.
Prueba. Sin pérdida de generalidad,
vamos $A = (0,0)$ , $B = (x_B,y_B)$ , $C = (x_C,y_C)$ , a continuación, el
área de, por ejemplo, los Delaunay región $APZQ$ es:
$$
\frac{1}{2} \det\begin{bmatrix} x_B/2 & (x_B+x_C)/3 \\ y_B/2 & (y_B+y_C)/3 \end{bmatrix} +
\frac{1}{2} \det\begin{bmatrix} (x_B+x_C)/3 & x_C/2 \\ (y_B+y_C)/3 & y_C/2 \end{bmatrix} =
\frac{1}{3} \times \frac{1}{2} \det\begin{bmatrix} x_B & x_C \\ y_B & y_C \end{bmatrix}
$$
Así que podemos concluir con seguridad que el procedimiento de integración numérica
como se propone en esta respuesta es equivalente con la integración numérica
más de Delaunay regiones (reunido alrededor de un vértice).
Hallar el área de una región de Voronoi es mucho más complicado (creo).
Es claro a partir de las imágenes, sin embargo, que la función de ponderación
los valores con Delaunay regiones es, al menos, diferentesde
la ponderación de los valores de la función con las regiones de Voronoi (excepto para los triángulos equiláteros).
La ACTUALIZACIÓN. Sin pérdida de generalidad, de nuevo, vamos a $A = (0,0)$ , $B = (x_B,y_B)$ , $C = (x_C,y_C)$ , a continuación, el
área de, por ejemplo, la región de Voronoi $APMQ$ es:
$$
V = \frac{\left[(x_B^2+y_B^2) - (x_B x_C + y_B y_C)\right]\left[x_C^2+y_C^2\right]}
{8(x_B y_C - y_B x_C)} +
\frac{\left[(x_C^2+y_C^2) - (x_B x_C + y_B y_C)\right]\left[x_B^2+y_B^2\right]}
{8(x_B y_C - y_B x_C)}
$$
Un código un poco (Delphi) programa en Pascal - la llamada a la función $V(A,B,C)$ es para memorizar:
programa de Voronoi;
tipo de
punto = record
x,y : doble;
end;
la función V(a,B,C : punto) : doble;
{
Área de la Región de Voronoi
en Delaunay triángulo
}
var
O1,O2 : doble;
p,q : punto;
comenzar
p.x := B. x A. x; p.y := B. y A. y;
q.x := C. x A. x; q.y := C. y A. y;
O1 := (-q.y*p.y+p.x*p.x+p.y*p.y-p.x*q.x)*(q.x*q.x+q.y*q.y)
/ (p.x*q.y-p.y*q.x)/8;
O2 := (-q.y*p.y+q.x*q.x+q.y*q.y-p.x*q.x)*(p.x*p.x+p.y*p.y)
/ (p.x*q.y-p.y*q.x)/8;
V := O1+O2;
end;
procedimiento de la prueba;
{
Suma de Voronoi áreas debe ser
Área de Delaunay triángulo
}
var
A,B,C,p,q : punto;
comenzar
Azar, Al Azar;
p.x := Aleatorio; p.y := Aleatorio;
q.x := Aleatorio; q.y := Aleatorio;
A. x := 0; A. y := 0;
B. x := p.x; B) y := p.y;
C. x := q.x; C. y := q.y;
Writeln(V(A,B,C) + V(B,C,A) + V(C,A,B),
'=',(p.x*q.y-p.y*q.x)/2);
end;
comenzar
de la prueba;
final.
Por lo tanto, muy en general, la integración numérica de procedimiento es el siguiente:
$$
\iint_{\Delta} f(x,y)\,dx\,dy = w_1 f_1 + w_2 f_2 + w_3 f_3 \qquad ; \qquad
\iint_{\Omega} f(x,y)\,dx\,dy = \sum_{\Delta} \iint_{\Delta} f(x,y)\,dx\,dy
$$
Donde:
- $w_1=w_2=w_3=1/3 \times$ área del triángulo , para la Delaunay regiones enfoque
- $w_1 = V(A,B,C)\, , w_2 = V(B,C,A)\, , w_3 = V(C,A,B)$ , para las regiones de Voronoi enfoque
Considerar todos los Delaunay / regiones de Voronoi alrededor de un vértice. Por simplicidad, suponga que
el asociado triángulos forman un regular polígono con $N$ bordes,
de tal manera que cada ángulo superior de un triángulo es $\phi=2\pi/N$ . Todos
los triángulos son isoceles, por lo tanto $\;x_B^2+y_B^2=x_C^2+y_C^2=L^2\;$ y podemos
determinar fácilmente la relación ( área de un Delaunay región ) / ( área de Voronoi de la región ) ,
con el coseno de la regla para el interior del producto y la regla del seno de un determinante:
$$
\frac{L^2\sin(\phi)/2/3}{2\left[L^2-L^2\cos(\phi)\right]L^2/\left[8L^2\sin(\phi)\right]} =
\frac{2}{3}\frac{\sin^2(\phi)}{1-\cos(\phi)} \quad \Longrightarrow \\
\frac{\mbox{Delaunay}}{\mbox{Voronoi}} = \frac{2}{3}\left[\,1+\cos(\phi)\,\right]
$$
De ello se desprende que Delaunay = Voronoi para $\,1+\cos(\phi) = 3/2\,$ por lo tanto $\,\phi=\pi/3$ ,
como se esperaba (triángulos equiláteros) . Además Delaunay > Voronoi para $\,\phi<\pi/3\,$
y de Voronoi > Delaunay para $\,\phi>\pi/3$ . Especialmente para obtuso triángulos (negativo coseno) la relación de
puede llegar a ser casi cero, lo que significa que las regiones de Voronoi puede llegar a ser mucho
más grande que el Delaunay regiones, dando así una aparentemente irracional de alto peso
a asociado un valor de la función.
Deje $\;a=\sqrt{x_B^2+y_B^2}\;$$\;b=\sqrt{x_C^2+y_C^2}\;$ . A continuación, para aquellos que quieren los de arriba WLOG :
$$
\frac{\mbox{Delaunay}}{\mbox{Voronoi}} =
\frac{4/3\,^2b^2\left[1-\cos^2(\phi)\right]}{2a^2b^2-ab(a^2+b^2)\cos(\phi)}
$$
La solución para los tres casos $\;<1,=1,>1\;$ es equivalente a la solución de una ecuación cuadrática
para $<0,=0,>0$ , es decir, cuando la siguiente parábola es positivo o cero o negativo, con $\;x=\cos(\phi)$ :
$$
y = x^2-\frac{3}{4}\frac{a^2+b^2}{ab}x+\frac{1}{2}
$$
, Las líneas azules son Delaunay, Rojo de Voronoi, Amarillo que tiene todos los pesos establece a 1.0, y el Verde de ellos se ha establecido en forma aleatoria a los valores de 0-1.
