La mayoría de los métodos cuasialeatorios bidimensionales están diseñados para el muestreo unitario cuadrado. Sin embargo, los triángulos también son muy importantes en los gráficos por computadora. Por lo tanto, describí un método simple de construcción directa para cubrir uniformemente una secuencia de puntos de un triángulo de forma arbitraria.


Figura 1. Un nuevo método directo para construir una secuencia cuasialeatoria abierta (infinita) con una divergencia baja en un triángulo de forma y tamaño arbitrarios. La figura muestra la distribución de puntos en quince triángulos aleatorios para los primeros 150 puntos.

Breve reseña

Las secuencias de baja discrepancia que muestrean / rellenan uniformemente un cuadrado se han estudiado activamente durante casi cien años. La mayoría de estas secuencias cuasialeatorias pueden expandirse a rectángulos por simple estiramiento, sin dañar significativamente la discrepancia.

Sin embargo, en esta publicación consideraremos una extensión interesante e importante de secuencias con una divergencia baja en un triángulo arbitrario.

Por lo que pude entender, se prestó muy poca atención a la construcción de conjuntos de puntos y secuencias distribuidos uniformemente en un triángulo. Los trabajos notables de los últimos años de Basu [2014] , Pillands [2005] y Brandolini [2013] representan los principales, si no los únicos artículos sobre este tema.

Estos autores generalmente consideran este problema desde un ángulo muy teórico y analítico, y casi siempre lo resuelven para un solo triángulo regular. En contraste con ellos, mi publicación está destinada principalmente al desarrollo de técnicas prácticas en la representación gráfica.

La publicación describe un método simple de construcción directa, que no requiere aceptación / exclusión, descarte o recursión; y lo más importante, se puede aplicar a triángulos de tamaño y forma arbitrarios.

La publicación consta de cuatro secciones:

1. Secuencias aleatorias cuadradas
2. Superponer un cuadrado de unidad en un triángulo.
3. Reducción de la distorsión
4. Otras generalizaciones

1. Secuencia cuasialeatoria de puntos

Puede pensar que colocar 100 puntos en un cuadrado para que la distancia mínima entre puntos adyacentes sea lo más grande posible será fácil. Pero, ¿qué pasa si necesitas colocar 13 puntos? 47? ¿Qué pasa con los puntos 2019?

Resulta que las secuencias de puntos con poca divergencia proporcionan una forma sistemática de resolver este problema. Hay muchas secuencias cuasialeatorias con una divergencia baja, desde una secuencia simple de Holton hasta una secuencia Sable más compleja. Cada una de estas secuencias tiene sus propias ventajas y desventajas. Por ejemplo, las secuencias de Holton resultan ser más útiles cuando se colocan objetos en un área, porque tiene métricas de distancia locales bien optimizadas como las vecinas más cercanas. La secuencia de Sable es propensa a formar más "abarrotada", pero la distribución global de puntos es muy uniforme, por lo que tiene excelentes propiedades de cuadratura.

Hay otra secuencia que me gusta usar, con excelentes propiedades locales y globales. Esta es la secuencia $$$R_2$descrito en detalle en mi publicación anterior "Eficiencia inesperada de secuencias cuasialeatorias" .

En resumen, definimos una secuencia bidimensional infinita $$$R_2$tal que

$$

$$\ pmb {t} _n = \ left \ {n \ pmb {\ alpha} \ right \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ left \ {n \ pmb {\ alfa} \ right \} \ quad n = 1,2,3, ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = \ left (\ frac {1} {g}, \ frac {1} {g ^ 2} \ right),$$

$$

$$\ textrm {y} \; g \ simeq 1.32471795572 \ tag {1}$$

Lea más sobre este significado especial. $$$g$, que a menudo se llama una "constante plástica", se puede leer en Wikipedia o Mathworld .

Como resultado, la Figura 2 muestra una comparación de diferentes secuencias con una divergencia baja (y una muestra aleatoria uniforme simple para comparación). Como puede ver, esta muestra aleatoria demuestra la acumulación de puntos. Además, contiene áreas que no contienen puntos en absoluto ("ruido blanco"), mientras que una secuencia cuasialeatoria con poca divergencia es un método para construir una secuencia (infinita) de puntos de una manera determinista, de modo que en cualquier etapa los puntos colocados se distribuyan uniformemente en todas partes espacio


Figura 2. Ilustración de los primeros 150 miembros de varias secuencias cuasialeativas de baja divergencia. Tenga en cuenta que todos crean puntos distribuidos más uniformemente en el espacio que una distribución aleatoria uniforme simple (abajo a la izquierda).

2. La imposición de una unidad cuadrada en un triángulo

Existen tres métodos bien conocidos para garantizar un muestreo aleatorio uniforme de un triángulo:

1. método de paralelogramo
2. Método de Kramer y
3. método de distribución de probabilidad inversa.

Figura 3. Método de paralelogramo

El método del paralelogramo es el siguiente.

Para triangulo $$$\ pmb {ABC}$considerar un paralelogramo $$$\ pmb {ABCA ’}$.

Para un punto de una unidad cuadrada $$$(r_1, r_2)$establecer tal punto $$$\ pmb {P}$eso $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$.

Este punto siempre estará dentro del paralelogramo. Sin embargo, si aparece en un triángulo adicional $$$\ pmb {ABC ’}$entonces necesitamos voltearlo al triángulo $$$\ pmb {ABC}$.

Es decir, si $$$r_1 + r_2 <1$entonces $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$pero si $$$r_1 + r_2> 1$entonces $$$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$.

Sin embargo, es muy importante comprender que, aunque estos métodos proporcionan un muestreo uniforme del triángulo, esto no significa que dicha transformación preservará la disposición espacial uniforme (es decir, baja divergencia) de nuestras distribuciones de puntos cuasialeatorios.

Por ejemplo, en el caso del método de paralelogramo, la reflexión a menudo puede dar como resultado que un punto esté muy cerca de otro punto existente. Obviamente, esto destruye la estructura de baja divergencia y aparece como distorsión / tira.

Del mismo modo, el método de distribución de probabilidad inversa aplica distorsión no lineal a los puntos. En las secuencias de Holton y Sable, esto significa que dos puntos se empujan muy a menudo muy juntos.

La Figura 4 muestra qué tan bien se mantiene la baja discrepancia en cada una de las diversas secuencias cuasialeativas al transformar una región de un cuadrado unitario a un triángulo utilizando el método de paralelogramo.


Figura 4. Comparación de la transformación de varias secuencias cuasialeatorias en un triángulo. Arriba está la secuencia de Holton, en el medio está la secuencia de Sable, debajo está la secuencia $$$R_2$. Se puede ver que se produce una acumulación significativa de puntos en la secuencia de Holton y una formación de banda significativa en la secuencia de Sobol. En comparación con ellos, en secuencia $$$R_2$los puntos se distribuyen de manera muy uniforme, y casi no hay aglomeraciones o rayas notables.

De los tres métodos de triangulación diferentes y muchas secuencias cuasialeativas diferentes, el método de paralelogramo aplicado al método de secuencia $$$R_2$es la única combinación que crea constantemente resultados que son aceptables en términos de mantener una baja varianza sin distorsión.

Los excelentes resultados de esta combinación se pueden examinar con más detalle en la Figura 5.


Figura 5. Puede ver que la secuencia convertida $$$R_2$proporciona una manera muy simple pero efectiva de distribuir uniformemente muchos de $$$N$puntos en el triángulo Funciona con triángulos agudos y obtusos. (El color indica el arreglo).

3. Otros aspectos

Distorsión

El método del paralelogramo requiere la elección de dos lados del triángulo como vectores de base.

Si los vértices están marcados en orden aleatorio, los patrones de puntos generalmente se parecen a los que se muestran en la Figura 6.


Figura 6. Patrones de puntos obtenidos al elegir aleatoriamente el orden de los vértices. Tenga en cuenta que en la mayoría de los casos, la distorsión es claramente notable.

Sin embargo, resulta que con una elección cuidadosa del orden de los vértices, las distorsiones pueden reducirse significativamente. En particular, si etiqueta el triángulo para que $$$A$es el ángulo más grande (es decir, el lado más grande está contra él), luego los lados $$$\ pmb {AB}$y $$$\ pmb {AC}$se usan como dos lados de un paralelogramo.

Si tomamos este orden, obtenemos los patrones de puntos que se muestran arriba en las Figuras 1, 4 y 5.

Sin embargo, incluso con un cierto orden de vértices, en algunos casos, los efectos de distorsión aún son notables. Son más notables cuando uno de los ángulos en los triángulos es muy pequeño. En el caso de triángulos obtusos, cuando el ángulo más pequeño es inferior a 30 grados, se nota cierta distorsión, y en el caso de triángulos de ángulo agudo, cuando el ángulo más pequeño es inferior a 20 grados, la distorsión se hace visible. (Si los triángulos muestreados son parte de la malla de Delaunay, entonces tales problemas de distorsión pueden ser mínimos, porque la triangulación de Delaunay está específicamente diseñada para minimizar el número de triángulos con ángulos pequeños).

Otras formas

Desafortunadamente, la técnica de paralelogramo no se puede usar para otras formas, porque usa simetría triangular. Para algunas cifras, se pueden obtener buenos resultados utilizando el método de distribución de probabilidad inversa. El siguiente es un ejemplo de cómo la secuencia $$$R_2R_2$con una divergencia baja, puede convertir a una región limitada por una curva gaussiana mientras mantiene una distancia uniforme entre los puntos.