La plupart des méthodes quasi aléatoires bidimensionnelles sont conçues pour l'échantillonnage au carré unitaire. Cependant, les triangles sont également très importants en infographie. Par conséquent, j'ai décrit une méthode de construction directe simple pour couvrir uniformément une séquence de points d'un triangle de forme arbitraire.


Figure 1. Une nouvelle méthode directe pour construire une séquence quasi-aléatoire ouverte (infinie) avec une faible divergence dans un triangle de forme et de taille arbitraires. La figure montre la distribution des points dans quinze triangles aléatoires pour les 150 premiers points.

Brève revue

Les séquences à faible écart qui échantillonnent / remplissent uniformément un carré sont activement étudiées depuis près de cent ans. La plupart de ces séquences quasi aléatoires peuvent être étendues à des rectangles par simple étirement, sans endommager de manière significative l'écart.

Cependant, dans ce post, nous considérerons une extension intéressante et importante des séquences avec une faible divergence dans un triangle arbitraire.

Pour autant que je puisse comprendre, très peu d'attention a été accordée à la construction d'ensembles de points et de séquences uniformément répartis dans un triangle. Les travaux remarquables de ces dernières années de Basu [2014] , Pillands [2005] et Brandolini [2013] représentent les principaux, sinon les seuls articles sur ce sujet.

Ces auteurs considèrent généralement ce problème sous un angle très théorique et analytique, et le résolvent presque toujours pour un seul triangle régulier. Contrairement à eux, mon poste est principalement destiné au développement de techniques pratiques de rendu graphique.

La publication décrit une méthode simple de construction directe, qui ne nécessite ni acceptation / exclusion, ni rejet ou récursivité; et surtout, il peut être appliqué à des triangles de taille et de forme arbitraires.

Le poste comprend quatre sections:

1. Séquences aléatoires au carré
2. Superposez un carré d'unité sur un triangle.
3. Réduction de la distorsion
4. Généralisations supplémentaires

1. Séquence quasi aléatoire de points

Vous pourriez penser que placer 100 points dans un carré afin que la distance minimale entre les points adjacents reste aussi grande que possible sera facile. Mais que faire si vous devez placer 13 points? 47? Qu'en est-il des points 2019?!

Il s'avère que des séquences de points à faible divergence fournissent un moyen systématique de résoudre ce problème. Il existe de nombreuses séquences quasi aléatoires avec une faible divergence, d'une simple séquence de Holton à une séquence de Sable plus complexe. Chacune de ces séquences a ses propres avantages et inconvénients. Par exemple, les séquences Holton s'avèrent plus utiles lors du placement d'objets dans une zone, car elles ont des métriques de distance locales bien optimisées telles que les voisins les plus proches. La séquence de sable est sujette à se former plus «encombrée», mais la distribution globale des points est très uniforme, donc elle a d'excellentes propriétés en quadrature.

Il y a une autre séquence que j'aime utiliser, avec d'excellentes propriétés locales et globales. Ceci est la séquence $$$R_2$décrit en détail dans mon post précédent "Efficacité inattendue des séquences quasi-aléatoires" .

En bref, nous définissons une séquence bidimensionnelle infinie $$$R_2$tel que

$$

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

$$

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

$$

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

En savoir plus sur cette signification particulière. $$$g$, souvent appelée «constante plastique», peut être lue sur Wikipédia ou Mathworld .

En conséquence, la figure 2 montre une comparaison de différentes séquences avec une faible divergence (et un échantillon aléatoire uniforme simple pour comparaison). Comme vous pouvez le voir, cet échantillon aléatoire montre l'accumulation de points. De plus, il contient des zones qui ne contiennent pas du tout de points («bruit blanc»), tandis qu'une séquence quasi-aléatoire avec une faible divergence est une méthode pour construire une séquence (infinie) de points de manière déterministe afin qu'à tout moment les points placés soient uniformément répartis sur l'ensemble l'espace.


Figure 2. Illustration des 150 premiers membres de diverses séquences quasi aléatoires à faible divergence. Notez qu'ils créent tous des points plus uniformément répartis dans l'espace qu'une simple distribution aléatoire uniforme (en bas à gauche).

2. L'imposition d'un carré d'unité sur un triangle

Il existe trois méthodes bien connues pour assurer un échantillonnage aléatoire uniforme à partir d'un triangle:

1. méthode du parallélogramme
2. La méthode de Kramer et
3. méthode de distribution de probabilité inverse.

Figure 3. Méthode de parallélogramme

La méthode du parallélogramme est la suivante.

Pour triangle $$$\ pmb {ABC}$envisager un parallélogramme $$$\ pmb {ABCA ’}$.

Pour un point d'un carré unitaire $$$(r_1, r_2)$définir un tel point $$$\ pmb {P}$ça $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$.

Ce point sera toujours à l'intérieur du parallélogramme. Cependant, s'il apparaît dans un triangle supplémentaire $$$\ pmb {ABC ’}$alors nous devons le retourner au triangle $$$\ pmb {ABC}$.

Autrement dit, si $$$r_1 + r_2 <1$alors $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$mais si $$$r_1 + r_2> 1$alors $$$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$.

Cependant, il est très important de comprendre que même si ces méthodes fournissent un échantillonnage uniforme à partir du triangle, cela ne signifie pas qu'une telle transformation préservera l'arrangement spatial uniforme (c'est-à-dire une faible divergence) de nos distributions ponctuelles quasi aléatoires.

Par exemple, dans le cas de la méthode du parallélogramme, la réflexion peut souvent conduire à un point très proche d'un autre point existant. Évidemment, cela détruit la structure à faible divergence et apparaît sous forme de distorsion / bande.

De même, la méthode de distribution de probabilité inverse applique une distorsion non linéaire aux points. Dans les séquences Holton et Sable, cela signifie que deux points se rapprochent très souvent l'un de l'autre.

La figure 4 montre à quel point le faible écart est maintenu dans chacune des différentes séquences quasi-aléatoires lors de la transformation d'une région d'un carré unitaire en triangle en utilisant la méthode du parallélogramme.


Figure 4. Comparaison de la transformation de diverses séquences quasi aléatoires dans un triangle. Au-dessus se trouve la séquence Holton, au milieu se trouve la séquence Sable, en dessous se trouve la séquence $$$R_2$. On peut voir qu'un encombrement important des points se produit dans la séquence Holton et une formation significative de bandes dans la séquence Sobol. Par rapport à eux, en séquence $$$R_2$les points sont distribués de manière très uniforme et il n'y a presque pas de foule ou de rayures visibles.

Des trois méthodes de triangulation différentes et de nombreuses séquences quasi-aléatoires différentes, la méthode du parallélogramme appliquée à la méthode de la séquence $$$R_2$est la seule combinaison qui crée constamment des résultats acceptables en termes de maintien d'une faible variance sans distorsion.

Les excellents résultats de cette combinaison peuvent être examinés plus en détail dans la figure 5.


Figure 5. Vous pouvez voir que la séquence convertie $$$R_2$fournit un moyen très simple mais efficace de répartir uniformément un grand nombre de $$$N$points dans le triangle. Il fonctionne avec des triangles à angle aigu et à angle obtus. (La couleur indique l'arrangement).

3. Autres aspects

Distorsion

La méthode du parallélogramme nécessite le choix de deux côtés du triangle comme vecteurs de base.

Si les sommets sont marqués dans un ordre aléatoire, les motifs des points ressemblent généralement à ceux illustrés à la figure 6.


Figure 6. Modèles de points obtenus en choisissant au hasard l'ordre des sommets. Notez que dans la plupart des cas, la distorsion est clairement perceptible.

Cependant, il s'avère qu'avec un choix soigneux de l'ordre des sommets, les distorsions peuvent être considérablement réduites. Plus particulièrement, si vous étiquetez le triangle de sorte que $$$A$est le plus grand angle (c'est-à-dire que le plus grand côté est contre lui), puis les côtés $$$\ pmb {AB}$et $$$\ pmb {AC}$sont utilisés comme deux côtés d'un parallélogramme.

Si nous prenons cet ordre, nous obtenons alors les modèles de points montrés ci-dessus dans les figures 1, 4 et 5.

Cependant, même avec un certain ordre de sommets, dans certains cas, les effets de distorsion sont toujours perceptibles. Ils sont plus visibles lorsque l'un des angles des triangles est très petit. Dans le cas des triangles obtus, lorsque le plus petit angle est inférieur à 30 degrés, une distorsion est perceptible, et dans le cas des triangles à angle aigu, lorsque le plus petit angle est inférieur à 20 degrés, la distorsion devient visible. (Si les triangles échantillonnés font partie du maillage de Delaunay, ces problèmes de distorsion peuvent être minimes, car la triangulation de Delaunay est spécifiquement conçue pour minimiser le nombre de triangles avec de petits angles.)

Autres formes

Malheureusement, la technique du parallélogramme ne peut pas être utilisée pour d'autres formes, car elle utilise la symétrie triangulaire. Pour certains chiffres, de bons résultats peuvent être obtenus en utilisant la méthode de distribution de probabilité inverse. Ce qui suit est un exemple de la façon dont la séquence $$$R_2R_2$avec une faible divergence, vous pouvez convertir en une région délimitée par une courbe gaussienne tout en maintenant une distance uniforme entre les points.