J'essaie de générer un ensemble de points qui ne tombent pas à portée les uns des autres dans une zone fixe. Mon approche est donnée ci-dessous:

import collections
from random import uniform

X = 100.0
Y = 100.0
points = 10
radius = 10

def in_circle(c_x, c_y, radius, x, y):
    dist_squared = (c_x - x)**2 + (c_y - y)**2
    return dist_squared <= radius ** 2

current = collections.defaultdict(lambda: [])

threshold = 0    

for point in range(1, points+1):
    cX = uniform(1.0, X)
    cY = uniform(1.0, Y)

    for cur in current:
        while in_circle(current[cur][0], current[cur][1], 2*radius, cX, cY):
          cX = uniform(1.0, X)
          cY = uniform(1.0, X)

          threshold += 1
          if threshold >= 1e+05:
              print "Cannot satisfy constraints"
              sys.exit(1)

    threshold = 0

    current[point] = [cX, cY]
    print cX, cY

Existe-t-il un bon moyen de terminer cet algorithme sans le faire entrer dans une boucle infinie? J'ai un contrôle de seuil, mais existe-t-il de meilleures façons de le faire?

2
Legend 28 oct. 2011 à 14:43

3 réponses

Meilleure réponse

Cet article sur l'échantillonnage de disques de poisson peut vous intéresser. L'auteur explique une stratégie pour sélectionner des points qui ne sont pas trop proches les uns des autres, et fournit même des exemples de code dans quelques langues, y compris Python.

Le problème avec la stratégie que vous avez décrite est, comme vous l'avez noté, que si vous voulez sélectionner beaucoup de points, ou si vous voulez que les points soient assez éloignés, les performances peuvent devenir atroces. Le schéma de disque de poisson a de meilleures caractéristiques de performance, je crois.

3
Matt Fenwick 28 oct. 2011 à 11:13

Pouvez-vous subdiviser la zone en carrés avec side> = distance minimale autorisée entre les points , puis en choisir quelques-uns au hasard?

Par exemple, ce sont vos carrés de délimitation de points, "numérotés" de 0 à j:

0 1 2 3 4
5 6 7 8 9
a b c d e
f g h i j

Ensuite, vous créez un tableau des indices carrés (0 à j dans cet exemple), au hasard mélangez-le, pour finir par, disons, bc4j25e1670dfgh89ai3, et prenez depuis le début autant d'indices que nécessaire, par exemple 5: bc4j2. Ensuite, vous placez vos points au centre (ou peut-être dans le coin supérieur gauche) des carrés choisis:

0 1 * 3 *
5 6 7 8 9
a * * d e
f g h i *
2
Alexey Frunze 28 oct. 2011 à 11:11

Cette classe de problème est appelée emballage circulaire. L'article sur mathworld indique que les emballages connus les plus denses pour le carré unitaire sont connus (et ce problème peut être transformé en celui-ci en mettant à l'échelle x et y). Les images de cet article montrent deux emballages sphériques denses (carré et hexagonal).

Quant à savoir si vous pouvez insérer un nouveau cercle, un diagramme voronoi peut être utile en tant que mesure de la superficie maximale non échantillonnée restante. D'autres méthodes approximatives d'évaluation de la zone inoccupée comme les arbres quadruples ou le hachage spatial peuvent également être suffisantes dans certains cas

2
Andrew Walker 28 oct. 2011 à 11:15
7928204