Verteilen von Punkten über eine Fläche innerhalb von Grenzen

Question

Ich interessiere mich für einen Weg (Algorithmus) der Verteilung einer vordefinierten Anzahl von Punkten über eine 4-seitige Oberfläche wie ein Quadrat.

Das Hauptproblem ist, dass jeder Punkt eine minimale und maximale Nähe zueinander haben muss (zufällig zwischen zwei vordefinierten Werten). Grundsätzlich sollte die Entfernung von zwei Punkten nicht näher als 2 sein, und eine weitere als 3.

Mein Code wird in Ruby implementiert (die Punkte sind Orte, die Oberfläche ist eine Karte), aber keine Ideen oder Schnipsel sind definitiv willkommen, da all meine Ideen eine gehörige Portion roher Gewalt beinhalten.

Answer 1

Versuchen Sie this paper. Es hat einen schönen, intuitiven Algorithmus, der das tut, was Sie brauchen.

In unserer Modellbildung haben wir ein anderes Modell übernommen: Wir betrachten jedes Zentrum als eine repulsive Kette, die mit allen seinen Nachbarn in Beziehung steht.

Zu Beginn der Simulation sind die Zentren zufällig verteilt, ebenso die Stärken der Strings. Wir wählen zufällig ein Zentrum; dann berechnen wir die resultierende Kraft, die von allen Nachbarn des gegebenen Zentrums verursacht wird, und wir berechnen die Verschiebung, die proportional und orientiert im Sinne der resultierenden Kraft ist.

Nach einer bestimmten Anzahl von Iterationen (die von der Anzahl der Zentren und dem Grad der anfänglichen Zufälligkeit abhängt) wird das System stabil.

Falls aus den Abbildungen nicht ersichtlich ist, erzeugt dieser Ansatz gleichmäßig verteilte Punkte. Sie können stattdessen eine Kraft verwenden, die innerhalb Ihrer Grenzen Null ist (z. B. zwischen 2 und 3) und nicht Null (sonst abstoßend, wenn die Punkte zu nahe liegen, attraktiv, wenn zu weit).

Dies ist meine Python-Implementierung (sorry, ich weiß nicht Ruby). Importieren Sie dies einfach und rufen Sie uniform() auf, um eine Liste von Punkten zu erhalten.

import numpy as np 
from numpy.linalg import norm 
import pylab as pl 

# find the nearest neighbors (brute force) 
def neighbors(x, X, n=10): 
    dX = X - x 
    d = dX[:,0]**2 + dX[:,1]**2 
    idx = np.argsort(d) 
    return X[idx[1:11]] 

# repulsion force, normalized to 1 when d == rmin 
def repulsion(neib, x, d, rmin): 
    if d == 0: 
    return np.array([1,-1]) 

    return 2*(x - neib)*rmin/(d*(d + rmin)) 

def attraction(neib, x, d, rmax): 
    return rmax*(neib - x)/(d**2) 

def uniform(n=25, rmin=0.1, rmax=0.15): 
    # Generate randomly distributed points 
    X = np.random.random_sample((n, 2)) 

    # Constants 
    # step is how much each point is allowed to move 
    # set to a lower value when you have more points 
    step = 1./50. 

    # maxk is the maximum number of iterations 
    # if step is too low, then maxk will need to increase 
    maxk = 100 

    k = 0 

    # Force applied to the points 
    F = np.zeros(X.shape) 

    # Repeat for maxk iterations or until all forces are zero 
    maxf = 1. 
    while maxf > 0 and k < maxk: 
    maxf = 0 
    for i in xrange(n): 
     # Force calculation for the i-th point 
     x = X[i] 
     f = np.zeros(x.shape) 

     # Interact with at most 10 neighbors 
     Neib = neighbors(x, X, 10) 

     # dmin is the distance to the nearest neighbor 
     dmin = norm(Neib[0] - x) 

     for neib in Neib: 
     d = norm(neib - x) 
     if d < rmin: 
      # feel repulsion from points that are too near 
      f += repulsion(neib, x, d, rmin) 
     elif dmin > rmax: 
      # feel attraction if there are no neighbors closer than rmax 
      f += attraction(neib, x, d, rmax) 

     # save all forces and the maximum force to normalize later 
     F[i] = f 
     if norm(f) <> 0: 
     maxf = max(maxf, norm(f)) 

    # update all positions using the forces 
    if maxf > 0: 
     X += (F/maxf)*step 

    k += 1 

    if k == maxk: 
    print "warning: iteration limit reached" 

    return X 

Answer 2

Ich nehme an, dass einer Ihrer Brute-Force-Ideen enthält nur immer wieder Punkte zufällig zu erzeugen und zu überprüfen, ob die Einschränkungen satisified geschehen sein. Eine andere Möglichkeit besteht darin, eine Konfiguration zu wählen, die die Beschränkungen erfüllt und einen kleinen Teil davon zufällig stört - zum Beispiel einen einzelnen Punkt verschieben -, um sich zu einer zufällig ausgewählten nahegelegenen Konfiguration zu bewegen. Wenn Sie dies oft genug tun, sollten Sie zu einer zufälligen Konfiguration wechseln, die fast unabhängig vom Startpunkt ist. Dies könnte unter http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm oder http://en.wikipedia.org/wiki/Gibbs_sampling gerechtfertigt sein.

Answer 3

Ich könnte versuchen, es nur zufällig zu tun, dann gehen und Punkte fallen, die zu anderen Punkten zu schließen sind. Sie können das Quadrat der Entfernung vergleichen, um etwas Rechenzeit zu sparen.

Oder erstellen Sie Zellen mit Rahmen und platzieren Sie jeweils einen Punkt. Weniger zufällig, es hängt davon ab, ob das ein "nur für's Ding" ist oder nicht. Aber es könnte sehr schnell gehen.

Answer 4

Ich machte einen Kompromiss und endete mit der Poisson Disk Sampling Methode.

Das Ergebnis war ziemlich nah an dem, was ich brauchte, vor allem mit einer geringeren Anzahl von Versuchen (was auch die Kosten drastisch reduziert).