Генерировать случайные точки, распределенные как города?

Question

Как можно генерировать, скажем, 1000 случайных точек с распределением, подобным города и города, например Огайо?
Боюсь, я не могу точно определить «распределены как города»; равномерно распределенные центры + маленькие гауссовы облака просты, но специальные.
Добавлено: должно быть семейство 2d дистрибутивов с параметром кластеризации, который можно варьировать в соответствии с заданным набором точек?

Answer 1

Может быть, вы можете взглянуть на Теорию центральных мест Уолтера Кристаллера . Я предполагаю, что где-то должен быть какой-то генератор, или вы можете приготовить свой собственный.

Answer 2

Начните с модели водных объектов в вашей целевой области (или составьте одну, если она для воображаемого места), затем группируйте города вблизи речных узлов, вдоль берегов озер, в местах соединения озер и рек. Затем проложите воображаемые шоссе, соединяющие эти крупные города. Теперь посыпьте несколько промежуточных городов вдоль этих автомагистралей на разумном расстоянии, предпочитая находиться вблизи перекрестков на автомагистралях. Теперь посыпьте несколько небольших городов через пустые места.

Answer 3

Гауссовы кластеры с пуассоновскими размерами кластеров работают довольно хорошо.

Проблема: генерировать случайные точки, которые группируются примерно как данные города, скажем, в США.

подзадачи:
а) описать кластеры с рядами чисел, так что «кластер A подобен кластеру B» упрощается до «кластерные числа (А), как« кластерные числа (В) ».
Выполнение N = 100, затем 1000 точек через fcluster ниже, с ncluster = 25, дает

N 100 ncluster 25: 22 + 3  r 117
sizes: av 4     10   9   8   7   6   6   5   5   4   4   4 ...
radii: av 117  202 198 140 134  64  62  28 197 144 148 132 ...

N 1000 cluster 25: 22 + 3  r 197
sizes: av 45  144 139 130  85  84  69  63  43  38  33  30  ...
radii: av 197  213 279 118 146 282 154 245 212 243 226 235 ...

б) найти комбинацию случайных генераторов с 2 или 3 параметрами которые можно варьировать для создания разных кластеров.
Гауссовы кластеры с размерами пуассоновских кластеров могут достаточно хорошо соответствовать кластеризации городов:

def randomclusters( N, ncluster=25,  radius=1, box=box ):
    """ -> N 2d points: Gaussian clusters, Poisson cluster sizes """
    pts = []
    lam = eval( str( N // ncluster ))
    clustersize = lambda: np.random.poisson(lam - 1) + 1
        # poisson 2:  14  27  27  18   9   4  %
        # poisson 3:   5  15  22  22  17  10  %
    while len(pts) < N:
        u = uniformrandom2(box)
        csize = clustersize()
        if csize == 1:
            pts.append( u )
        else:
            pts.extend( inbox( gauss2( u, radius, csize )))
    return pts[:N]


    # Utility functions --

import scipy.cluster.hierarchy as hier

def fcluster( pts, ncluster, method="average", criterion="maxclust" ):
    """ -> (pts, Y pdist, Z linkage, T fcluster, clusterlists)
        ncluster = n1 + n2 + ... (including n1 singletons)
        av cluster size = len(pts) / ncluster
    """
        # Clustering is pretty fast:
        # sort pdist, then like Kruskal's MST, O( N^2 ln N )
        # Many metrics and parameters are possible; these satisfice.
    pts = np.asarray(pts)
    Y = scipy.spatial.distance.pdist( pts )  # N*(N-1)/2
    Z = hier.linkage( Y, method )  # N-1, like mst
    T = hier.fcluster( Z, ncluster, criterion=criterion )
    clusters = clusterlists(T)
    return (pts, Y, Z, T, clusters)

def clusterlists(T):
    """ T = hier.fcluster( Z, t ) e.g. [a b a b c a]
        -> [ [0 2 5] [1 3] ] sorted by len, no singletons [4]
    """
    clists = [ [] for j in range( max(T) + 1 )]
    for j, c in enumerate(T):
        clists[c].append( j )
    clists.sort( key=len, reverse=True )
    n1 = np.searchsorted(  map( len, clists )[::-1], 2 )
    return clists[:-n1]

def radius( x ):
    """ rms |x - xmid| """
    return np.sqrt( np.mean( np.var( x, axis=0 )))
        # * 100  # 1 degree lat/long ~ 70 .. 111 km

Answer 4

В Java это обеспечивается через new Random().nextGaussian(). Поскольку исходный код Java доступен, вы можете посмотреть на него:

synchronized public double nextGaussian() {
    // See Knuth, ACP, Section 3.4.1 Algorithm C.
    if (haveNextNextGaussian) {
        haveNextNextGaussian = false;
        return nextNextGaussian;
    } else {
        double v1, v2, s;
        do {
            v1 = 2 * nextDouble() - 1; // between -1 and 1
            v2 = 2 * nextDouble() - 1; // between -1 and 1
            s = v1 * v1 + v2 * v2;
        } while (s >= 1 || s == 0);
        double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
        nextNextGaussian = v2 * multiplier;
        haveNextNextGaussian = true;
        return v1 * multiplier;
    }
}

Построение 30000 домов с использованием

x = r.nextGaussian() * rad/4 + rad;
y = r.nextGaussian() * rad/4 + rad;

дает этот красивый город: