Un problème qui me trotte dans la tête depuis quelque temps concerne un jeu avec un rondel comme celui montré ici. Je veux que ces jetons soient centrés uniformément dans chaque secteur d’un polygone régulier à 13 côtés (triskaidécagone). J’ai aussi rencontré ce problème en optimisant l’espace racinaire de plantes dans une parcelle de jardin de forme irrégulière. J’ai empaqueté mon approche sous le nom de pointille, une petite bibliothèque TypeScript sur npm.

Nommé d’après le motif décoratif utilisé en bijouterie, pointillé.

Installation

npm install pointille

Utilisation de base

pointille prend un polygone sous forme de tableau de sommets [x, y] et un compte, et renvoie autant de points répartis à l’intérieur du polygone.

import { pointille } from 'pointille'

const carreUnitaire = [
  [0, 0],
  [1, 0],
  [1, 1],
  [0, 1],
] as const

const points = pointille(carreUnitaire, 25)
// => [
//   ...
//   [ 0.4973001454916204, 0.5078269245431213 ],
//   [ 0.902819350372445, 0.9059261510512003 ],
//   [ 0.13364467572889838, 0.25595086132355166 ],
//   [ 0.5177439763083426, 0.7246545345081363 ]
// ]

La fonction est pure et déterministe : le même polygone et le même n vous renverront toujours le même ensemble de points. Cela facilite son utilisation dans les tests, dans le rendu de snapshots, et partout où vous préférez éviter l’état caché.

Polygones concaves

L’algorithme rogne les cellules de Voronoï contre le polygone d’entrée, donc les formes concaves fonctionnent aussi. Voici une forme en L :

const formeL = [
  [0, 0],
  [2, 0],
  [2, 1],
  [1, 1],
  [1, 2],
  [0, 2],
] as const

const points = pointille(formeL, 40)

Aucun point ne s’échappera dans le coin manquant, et la densité le long des deux bras du L reste à peu près égale.

Options

Deux paramètres optionnels valent la peine d’être connus :

pointille(polygone, n, { iterations: 30, seed: 1 })
  • iterations — le nombre d’étapes de relaxation de Lloyd à exécuter. La valeur par défaut de 30 suffit généralement pour que les points se stabilisent, mais en regardant de près la fin de la mantisse, vous pourriez repérer une asymétrie. Plus bas est plus rapide, plus haut vous rapproche d’une tessellation de Voronoï centroïdale parfaite.
  • seed — l’indice de départ dans la séquence de Halton utilisée pour le placement initial des points. Le modifier vous donne une disposition différente (mais toujours déterministe). Utile quand vous voulez de la variété entre, disons, plusieurs tuiles rendues, sans compromettre la reproductibilité.
const a = pointille(carreUnitaire, 25, { seed: 1 })
const b = pointille(carreUnitaire, 25, { seed: 2 })
// a et b sont tous deux uniformément répartis, mais différents l'un de l'autre.
// Relancer l'un ou l'autre appel renvoie un tableau équivalent.

Comment ça marche

Il y a trois pièces :

  1. Séquence de Halton — une séquence quasi-aléatoire à faible discrépance est utilisée pour initialiser les positions des points à l’intérieur de la boîte englobante du polygone, en rejetant tout point qui tombe à l’extérieur. Comparée à Math.random(), cette disposition de départ présente déjà beaucoup moins d’agrégats, donc vous partez d’un meilleur point.
  2. Masquage de Voronoï — chaque itération calcule la tessellation de Voronoï des points actuels, puis rogne chaque cellule contre le polygone afin que les cellules aux bords ne dépassent pas les limites.
  3. Algorithme de Lloyd — chaque point est déplacé vers le centroïde de sa cellule de Voronoï rognée. Répétez. Les points s’éloignent les uns des autres et tendent vers un espacement uniforme.

Le résultat est ce qu’on appelle une tessellation de Voronoï centroïdale (CVT) : un pavage où chaque point se situe au centre de masse de sa propre cellule. C’est un point fixe du processus de relaxation, et une fois qu’on en est proche, les points cessent de bouger.

Pourquoi pas l’échantillonnage Poisson-disque ?

L’échantillonnage Poisson-disque est la référence habituelle pour des points « répartis uniformément mais non en grille ». C’est un algorithme bien plus rapide qui produit un motif organique et naturel. Si vous vouliez un espacement plus intentionnel, avec une qualité plus cristalline, je pense que celui-ci serait préférable.

Source

Le paquet est disponible sur npm sous le nom pointille, et le code source se trouve sur github.com/philihp/pointille.

Essayez-le