境界内のサーフェス上に点を配置する

Question

私は正方形のように4面のサーフェスにあらかじめ定義された数の点を分配する方法（アルゴリズム）に興味があります。

主な問題点は、各ポイントが互いに近接して最小限と最大限の近接性を持たなければならないことです（事前定義された2つの値の間でランダム）。基本的に任意の2つのポイントの距離は、2というよりも3より遠いはずはありません。

私のコードはルビーで実装されます（ポイントは場所です、サーフェスはマップです）。私のすべてのアイデアにはかなりの量のブルートフォースが含まれているので、スニペットは間違いなく歓迎されます。

Answer 1

Try this paperそれは、あなたが必要とするものを行う素晴らしい、直感的なアルゴリズムを持っています。

私たちのモデル化では、私たちは別のモデルを採用しました。各中心はすべての近隣に関連しているとみなされます。

シミュレーションの開始時に、センターは無作為に分散され、文字列 の強さもランダムに分散されます。 1つの中心をランダムに移動するように選択します。与えられた中心のすべての 隣人によって引き起こされた結果の力を計算し、結果としての力の意味で、比例して方向付けされた変位を計算する。 。

一定数の反復（ の中心の数および初期ランダム度に依存する）の後、システムは安定する。

図から明らかでない場合は、このアプローチは一様に分布する点を生成します。例えば、範囲内で0の力（2と3の間）と、それ以外の場合は0以外の力を使用することができます（ポイントが近すぎると反発し、遠すぎると魅力的です）。

これは私のPythonの実装です（申し訳ありませんが、私はルビーを知らない）。これをインポートしてuniform（）を呼び出し、ポイントのリストを取得してください。

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

私はあなたのブルートフォースのアイデアの一つがちょうど繰り返し、ランダムな点を生成し、制約がsatisifiedすることが起こるかどうかをチェックする含まれていることを推測。

もう1つの方法は、制約を満たし、ランダムに選択された小さな部分を繰り返し摂動することです。たとえば、1つの点を移動して、ランダムに選択された近くの構成に移動します。これを頻繁に行う場合は、開始点からほとんど独立したランダムな設定に移行する必要があります。これはhttp://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithmまたはhttp://en.wikipedia.org/wiki/Gibbs_samplingの下で正当化することができます。

Answer 3

ランダムに実行してから、他のポイントに近いポイントを通過して削除することを試みることがあります。数学の時間を節約するために距離の2乗を比較することができます。

境界線のあるセルを作成し、それぞれにポイントを配置します。無作為ではなく、これが「見た目だけのもの」であるかどうかによって異なります。しかし、それは非常に速くなる可能性があります。

Answer 4

私は妥協し、ポアソンディスクサンプリング法を使用しました。

結果は私が必要としていたものにかなり近く、特に試行回数が少ないほど（コストも大幅に削減されます）。