Равномерно распределяя n точек по сфере - PullRequest
Новая
       133

Равномерно распределяя n точек по сфере

99 голосов
/ 07 марта 2012

Мне нужен алгоритм, который может дать мне позиции вокруг сферы для N точек (вероятно, меньше 20), которые расплывчато распределяют их. Нет необходимости в «совершенстве», но мне просто нужно, чтобы ни один из них не был сгруппирован вместе.

  • Этот вопрос предоставил хороший код, но я не смог найти способ сделать эту униформу, так как это казалось на 100% рандомизированным.
  • В этом посте рекомендуется два способа, позволяющих вводить количество точек на сфере, но алгоритм Saff и Kuijlaars точно соответствует psuedocode, который я мог бы транскрибировать, и Пример кода Я обнаружил, что в нем содержится "узел [k]", который я не смог понять, объяснил и разрушил эту возможность. Второй пример блога - «Спираль золотого сечения», которая дала мне странные, сгруппированные результаты без четкого способа определения постоянного радиуса.
  • Этот алгоритм из этот вопрос может показаться, что он может сработать, но я не могу собрать воедино то, что на этой странице, в psuedocode или что-то в этом роде.

Несколько других вопросов, с которыми я сталкивался, говорили о рандомизированном равномерном распределении, что добавляет уровень сложности, который меня не беспокоит. Я прошу прощения за то, что это такой глупый вопрос, но я хотел показать, что я действительно выглядел суровым и все еще терпел неудачу.

Итак, я ищу простой псевдокод для равномерного распределения N точек вокруг единичной сферы, который возвращается в сферических или декартовых координатах. Еще лучше, если он может даже распределяться с небольшой долей случайности (подумайте о планетах вокруг звезды, прилично раскинувшихся, но с достаточной свободой).

Ответы [ 14 ]

1 голос
/ 07 марта 2012

с небольшим количеством очков вы можете запустить симуляцию: 

from random import random,randint
r = 10
n = 20
best_closest_d = 0
best_points = []
points = [(r,0,0) for i in range(n)]
for simulation in range(10000):
    x = random()*r
    y = random()*r
    z = r-(x**2+y**2)**0.5
    if randint(0,1):
        x = -x
    if randint(0,1):
        y = -y
    if randint(0,1):
        z = -z
    closest_dist = (2*r)**2
    closest_index = None
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            p1,p2 = points[i],points[j]
            x1,y1,z1 = p1
            x2,y2,z2 = p2
            d = (x1-x2)**2+(y1-y2)**2+(z1-z2)**2
            if d < closest_dist:
                closest_dist = d
                closest_index = i
    if simulation % 100 == 0:
        print simulation,closest_dist
    if closest_dist > best_closest_d:
        best_closest_d = closest_dist
        best_points = points[:]
    points[closest_index]=(x,y,z)


print best_points
>>> best_points
[(9.921692138442777, -9.930808529773849, 4.037839326088124),
 (5.141893371460546, 1.7274947332807744, -4.575674650522637),
 (-4.917695758662436, -1.090127967097737, -4.9629263893193745),
 (3.6164803265540666, 7.004158551438312, -2.1172868271109184),
 (-9.550655088997003, -9.580386054762917, 3.5277052594769422),
 (-0.062238110294250415, 6.803105171979587, 3.1966101417463655),
 (-9.600996012203195, 9.488067284474834, -3.498242301168819),
 (-8.601522086624803, 4.519484132245867, -0.2834204048792728),
 (-1.1198210500791472, -2.2916581379035694, 7.44937337008726),
 (7.981831370440529, 8.539378431788634, 1.6889099589074377),
 (0.513546008372332, -2.974333486904779, -6.981657873262494),
 (-4.13615438946178, -6.707488383678717, 2.1197605651446807),
 (2.2859494919024326, -8.14336582650039, 1.5418694699275672),
 (-7.241410895247996, 9.907335206038226, 2.271647103735541),
 (-9.433349952523232, -7.999106443463781, -2.3682575660694347),
 (3.704772125650199, 1.0526567864085812, 6.148581714099761),
 (-3.5710511242327048, 5.512552040316693, -3.4318468250897647),
 (-7.483466337225052, -1.506434920354559, 2.36641535124918),
 (7.73363824231576, -8.460241422163824, -1.4623228616326003),
 (10, 0, 0)]
1 голос
/ 07 марта 2012

Возьмите два самых больших фактора из вашего N, если N==20, то два самых больших фактора - {5,4}, или, в более общем смысле, {a,b}. Рассчитать 

dlat  = 180/(a+1)
dlong = 360/(b+1})

Поставьте свою первую точку на {90-dlat/2,(dlong/2)-180}, свою вторую на {90-dlat/2,(3*dlong/2)-180}, свою третью на {90-dlat/2,(5*dlong/2)-180}, пока вы не совершите кругосветное путешествие один раз, и к этому времени вы достигнете {75,150}, когда вы перейти к {90-3*dlat/2,(dlong/2)-180}.

Очевидно, я работаю над этим в градусах на поверхности сферической земли, с обычными соглашениями для перевода +/- в N / S или E / W. И, очевидно, это дает вам совершенно неслучайное распределение, но оно равномерно и точки не сгруппированы вместе.

Чтобы добавить некоторую степень случайности, вы можете сгенерировать 2 нормально распределенных (со средним 0 и стандартным отклонением {dlat / 3, dlong / 3} соответственно) и добавить их к вашим равномерно распределенным точкам.

0 голосов
/ 04 января 2013

Это работает, и это смертельно просто.Столько очков, сколько вы хотите: 

    private function moveTweets():void {


        var newScale:Number=Scale(meshes.length,50,500,6,2);
        trace("new scale:"+newScale);


        var l:Number=this.meshes.length;
        var tweetMeshInstance:TweetMesh;
        var destx:Number;
        var desty:Number;
        var destz:Number;
        for (var i:Number=0;i<this.meshes.length;i++){

            tweetMeshInstance=meshes[i];

            var phi:Number = Math.acos( -1 + ( 2 * i ) / l );
            var theta:Number = Math.sqrt( l * Math.PI ) * phi;

            tweetMeshInstance.origX = (sphereRadius+5) * Math.cos( theta ) * Math.sin( phi );
            tweetMeshInstance.origY= (sphereRadius+5) * Math.sin( theta ) * Math.sin( phi );
            tweetMeshInstance.origZ = (sphereRadius+5) * Math.cos( phi );

            destx=sphereRadius * Math.cos( theta ) * Math.sin( phi );
            desty=sphereRadius * Math.sin( theta ) * Math.sin( phi );
            destz=sphereRadius * Math.cos( phi );

            tweetMeshInstance.lookAt(new Vector3D());


            TweenMax.to(tweetMeshInstance, 1, {scaleX:newScale,scaleY:newScale,x:destx,y:desty,z:destz,onUpdate:onLookAtTween, onUpdateParams:[tweetMeshInstance]});

        }

    }
    private function onLookAtTween(theMesh:TweetMesh):void {
        theMesh.lookAt(new Vector3D());
    }
0 голосов
/ 25 сентября 2012 
# create uniform spiral grid
numOfPoints = varargin[0]
vxyz = zeros((numOfPoints,3),dtype=float)
sq0 = 0.00033333333**2
sq2 = 0.9999998**2
sumsq = 2*sq0 + sq2
vxyz[numOfPoints -1] = array([(sqrt(sq0/sumsq)), 
                              (sqrt(sq0/sumsq)), 
                              (-sqrt(sq2/sumsq))])
vxyz[0] = -vxyz[numOfPoints -1] 
phi2 = sqrt(5)*0.5 + 2.5
rootCnt = sqrt(numOfPoints)
prevLongitude = 0
for index in arange(1, (numOfPoints -1), 1, dtype=float):
  zInc = (2*index)/(numOfPoints) -1
  radius = sqrt(1-zInc**2)

  longitude = phi2/(rootCnt*radius)
  longitude = longitude + prevLongitude
  while (longitude > 2*pi): 
    longitude = longitude - 2*pi

  prevLongitude = longitude
  if (longitude > pi):
    longitude = longitude - 2*pi

  latitude = arccos(zInc) - pi/2
  vxyz[index] = array([ (cos(latitude) * cos(longitude)) ,
                        (cos(latitude) * sin(longitude)), 
                        sin(latitude)])
Страница:
...