Python: s'assurer que chaque distance par paire est >= une distance minimale

Question

J'ai un tableau 2D d'environ 200 000 points et je souhaite "jitter" ces points de sorte que la distance entre chaque point et son voisin le plus proche soit >= une certaine valeur minimale.

Avant d'écrire cet algorithme à partir de zéro, je voulais demander : Y a-t-il des approches canoniques ou des algorithmes souvent utilisés pour implémenter ce comportement ? Je pensais qu'il serait judicieux de commencer par examiner ces algorithmes avant de me lancer là-dedans.

Toute suggestion que d'autres peuvent offrir sur cette question serait grandement appréciée.

Answer 1

J'ai fini par utiliser une technique appelée "itération de Lloyd" pour résoudre ce problème. L'idée derrière l'algorithme est assez simple; pour exécuter une itération de Lloyd sur un ensemble de points, nous :

1. Construisons un diagramme de Voronoi des points
2. Recentrons chaque point dans sa cellule de Voronoi
3. Répétons jusqu'à ce que les points soient suffisamment séparés

Cette encapsulation contient un peu de code d'exemple (avec des visualisations) :

from lloyd import Field
from scipy.spatial import voronoi_plot_2d
import matplotlib.pyplot as plt
import numpy as np
import umap, os

def plot(vor, name, e=0.3):
  '''Trace la carte de Voronoi du tableau numpy 2D X'''
  plot = voronoi_plot_2d(vor, show_vertices=False, line_colors='y', line_alpha=0.5, point_size=5)
  plot.set_figheight(14)
  plot.set_figwidth(20)
  plt.axis([field.bb[0]-e, field.bb[1]+e, field.bb[2]-e, field.bb[3]+e])
  if not os.path.exists('plots'): os.makedirs('plots')
  if len(str(name)) < 2: name = '0' + str(name)
  plot.savefig( 'plots/' + str(name) + '.png' )

# obtenir 1000 observations en deux dimensions et tracer leur carte de Voronoi
np.random.seed(1144392507)
X = np.random.rand(1000, 4)
X = umap.UMAP().fit_transform(X)

# exécuter 20 itérations de l'algorithme de Lloyd
field = Field(X)
for i in range(20):
  print(' * exécution de l\'itération', i)
  plot(field.voronoi, i)
  field.relax()

Le point clé est que les points se déplacent exactement comme dans le gif suivant :

NB : Le gif ci-dessus montre l'itération de Lloyd non contrainte, où le domaine de sortie peut être très grand. Pour une discussion et du code pour construire des itérations de Lloyd contraintes en Python, j'ai écrit un petit article de blog.

Answer 2

Votre problème est assez similaire à la construction de graphiques à bulles ( exemples): placer N sphères de rayon spécifié dans un graphique de telle sorte que :

• elles ne se chevauchent pas
• le graphique total soit le plus petit possible

Je ne suis pas très compétent dans ce domaine, je ne peux donc pas dresser une liste exhaustive des algorithmes pour ce problème. Je vais présenter le seul que je connais dans ce post, et comment vous pourriez l'adapter à votre problème.

Une approche courante utilisée par les bibliothèques de graphiques JavaScript semble être basée sur la physique (exemple : d3.js force clusters). En gros (de ce que je comprends), ils :

1. donnent initialement une position aléatoire (ou avec une heuristique) aux sphères.
2. exécutent une petite simulation physique en considérant les sphères comme des objets, en appliquant les forces suivantes :
   • Gravité pour attirer chaque sphère.
   • Collision pour séparer les sphères qui se chevauchent.
   • Friction "fluide" : ralentir tout objet qui a une vitesse. Cela garantit que la simulation s'arrête à un moment donné (éviter les oscillations).

Cela pourrait être adapté pour résoudre votre problème : considérez chaque point comme le centre d'une sphère de diamètre D (D étant la distance minimale que vous souhaitez entre chaque point). Toutes les sphères ont la même masse (vous pouvez simplement ignorer la masse et travailler directement avec les accélérations au lieu des forces).

1. La position initiale de vos sphères est donnée par vos données d'entrée.
2. Physique : il suffit d'ignorer la gravité, car vous ne voulez/pas besoin de "packer" les points.

Comme je l'ai dit, je ne suis pas très familier avec les graphiques à bulles. Il pourrait être intéressant de rechercher des algorithmes alternatifs sur ce sujet et de voir s'ils conviennent à votre cas.

Answer 3

1. calculer les distances par paires entre tous les points - sklearn.metrics.pairwise.euclidean_distances
2. calculer le minimum de toutes les distances par paires
3. si le minimum est assez petit, sortir
4. calculer les vecteurs par paires entre chaque deux points de sorte qu'ils pointent à l'opposé l'un de l'autre
5. diviser par les distances par paires pour qu'ils soient des vecteurs unitaires
6. pour chaque point, calculer la distance à déplacer comme la somme des autres points de : vecteur par paire / distance par paire au carré * une certaine constante (la force - la constante doit être réglée de sorte que lorsque les points sont à la distance minimale, la force soit faible mais pas infinitésimale)
7. déplacer tous les points de la valeur calculée en 6. Il faudrait également limiter la distance de déplacement peut-être à minimum/10, donc si 2 points se retrouvent au même endroit, ils ne seront pas déplacés à une distance infinie l'un de l'autre
8. répéter jusqu'à ce que le minimum soit assez petit

Devrait converger dans tous les cas mais va agrandir le canevas si nécessaire. C'est aussi intensif en mémoire et en calcul par exemple pour 200 000 points, mais une matrice creuse qui ignore les grands vecteurs/les petites forces le rend plus abordable.