python - 球上にn点を均等に分散

Question

球の周りの位置をNポイント（おそらく20未満）で漠然と広げることができるアルゴリズムが必要です。「完璧」の必要はありませんが、私はそれが必要なだけなので、それらのどれも一緒に束ねられていません。

• この質問は良いコードを提供しましたが、これは100％ランダム化されているように見えたため、これを統一する方法を見つけることができませんでした。
• 推奨されるこのブログ投稿には、球上の点の数を入力できる2つの方法がありましたが、SaffとKuijlaarsのアルゴリズムは、正確に私が書き写すことができる擬似コードであり、見つけたコード例には「node[k]」が含まれていました。説明を参照して、その可能性を台無しにしました。2番目のブログの例は黄金分割スパイラルでした。これは、一定の半径を定義する明確な方法がなく、奇妙でまとまりのある結果をもたらしました。
• この質問からのこのアルゴリズムはおそらく機能するようですが、そのページにあるものを擬似コードなどにまとめることはできません。

私が出くわした他のいくつかの質問スレッドは、ランダム化された一様分布について話しました。これは、私が心配していないレベルの複雑さを追加します。これはとてもばかげた質問であることをお詫びしますが、私は本当に一生懸命に見えて、まだ不足していることを示したかったのです。

したがって、私が探しているのは、球座標またはデカルト座標のいずれかで返される、単位球の周りにNポイントを均等に分散するための単純な擬似コードです。それが少しのランダム化でさえ分配することができればさらに良いです（星の周りの惑星を考えてください、きちんと広がっていますが、余裕があります）。

Answer 1

これは、球上のパッキング ポイントとして知られており、(既知の) 一般的で完全な解はありません。ただし、不完全なソリューションがたくさんあります。最も人気があるのは次の 3 つです。

1. シミュレーションを作成します。各点を球に拘束された電子として扱い、特定のステップ数でシミュレーションを実行します。電子の反発により、システムは自然に、より安定した状態になり、点が互いに可能な限り離れた状態になります。
2. ハイパーキューブの拒否。この派手に聞こえる方法は、実際には非常に単純です。球を囲む立方体の内側のポイント(それらよりもはるかに多いn) を均一に選択し、球の外側のポイントを拒否します。残りの点をベクトルとして扱い、それらを正規化します。これらはあなたの「サンプル」です -nいくつかの方法 (無作為、貪欲など) を使用してそれらを選択します。
3. らせん近似。球体の周りにらせんをトレースし、らせんの周りにポイントを均等に配置します。数学が関係しているため、これらはシミュレーションよりも理解が複雑ですが、はるかに高速です (そして、おそらくコードが少なくて済みます)。最も人気があるのは、 Saff などによるものと思われます。

この問題に関するより多くの情報は、ここで見つけることができます

Answer 2

このコード例 node[k]では、k 番目のノードだけです。配列 N ポイントを生成してnode[k]おり、k 番目 (0 から N-1 まで) です。それだけで混乱している場合は、今すぐそれを使用できることを願っています。

(つまり、kコードフラグメントが開始する前に定義され、ポイントのリストを含むサイズ N の配列です)。

または、ここで他の回答に基づいて構築します（およびPythonを使用）：

> cat ll.py
from math import asin
nx = 4; ny = 5
for x in range(nx):
    lon = 360 * ((x+0.5) / nx)
    for y in range(ny):                                                         
        midpt = (y+0.5) / ny                                                    
        lat = 180 * asin(2*((y+0.5)/ny-0.5))                                    
        print lon,lat                                                           
> python2.7 ll.py                                                      
45.0 -166.91313924                                                              
45.0 -74.0730322921                                                             
45.0 0.0                                                                        
45.0 74.0730322921                                                              
45.0 166.91313924                                                               
135.0 -166.91313924                                                             
135.0 -74.0730322921                                                            
135.0 0.0                                                                       
135.0 74.0730322921                                                             
135.0 166.91313924                                                              
225.0 -166.91313924                                                             
225.0 -74.0730322921                                                            
225.0 0.0                                                                       
225.0 74.0730322921                                                             
225.0 166.91313924
315.0 -166.91313924
315.0 -74.0730322921
315.0 0.0
315.0 74.0730322921
315.0 166.91313924

それをプロットすると、極の近くで垂直方向の間隔が大きくなり、各ポイントがほぼ同じ総空間領域に位置することがわかります(極の近くでは「水平方向」のスペースが少なくなるため、「垂直方向」により多くのスペースが得られます)。 ）。

これは、すべてのポイントが隣接するポイントとほぼ同じ距離にあることと同じではありません (これは、リンクが話していることだと思います)。 .

Answer 3

この回答は、この回答で概説されているのと同じ「理論」に基づいています

私はこの答えを次のように追加しています：
-他のオプションはどれも「均一性」の必要性「スポットオン」に適合しません（または明らかにそうではありません）。(元の質問で特に必要な惑星のような分布のような動作を取得することに注意してください。ランダムに作成された k 個の均一に作成されたポイントの有限リストから拒否するだけです (k 個のアイテムのインデックス カウントに関してランダムです)。)
-- 最も近い他の impl では、「角度軸」によって「N」を決定する必要がありましたが、両方の角度軸の値にわたって「N の 1 つの値」だけを決定する必要がありました (これは、N の数が少ない場合、何が重要であるかどうかを知るのが非常に難しいです (例: '5' ポイントが必要です -- 楽しんでください ) )
--さらに、画像なしで他のオプションを区別する方法を「理解」するのは非常に難しいため、このオプションがどのように見えるか (以下) と、すぐに実行できる実装を示します。

N が 20 の場合:

そして80でN：

エミュレーションが同じソースである、すぐに実行できる python3 コードを次に示します。 . （私が含めたプロットは、「メイン」として実行されたときに起動します。http ://www.scipy.org/Cookbook/Matplotlib/mplot3D から取得されます）

from math import cos, sin, pi, sqrt

def GetPointsEquiAngularlyDistancedOnSphere(numberOfPoints=45):
    """ each point you get will be of form 'x, y, z'; in cartesian coordinates
        eg. the 'l2 distance' from the origion [0., 0., 0.] for each point will be 1.0 
        ------------
        converted from:  http://web.archive.org/web/20120421191837/http://www.cgafaq.info/wiki/Evenly_distributed_points_on_sphere ) 
    """
    dlong = pi*(3.0-sqrt(5.0))  # ~2.39996323 
    dz   =  2.0/numberOfPoints
    long =  0.0
    z    =  1.0 - dz/2.0
    ptsOnSphere =[]
    for k in range( 0, numberOfPoints): 
        r    = sqrt(1.0-z*z)
        ptNew = (cos(long)*r, sin(long)*r, z)
        ptsOnSphere.append( ptNew )
        z    = z - dz
        long = long + dlong
    return ptsOnSphere

if __name__ == '__main__':                
    ptsOnSphere = GetPointsEquiAngularlyDistancedOnSphere( 80)    

    #toggle True/False to print them
    if( True ):    
        for pt in ptsOnSphere:  print( pt)

    #toggle True/False to plot them
    if(True):
        from numpy import *
        import pylab as p
        import mpl_toolkits.mplot3d.axes3d as p3

        fig=p.figure()
        ax = p3.Axes3D(fig)

        x_s=[];y_s=[]; z_s=[]

        for pt in ptsOnSphere:
            x_s.append( pt[0]); y_s.append( pt[1]); z_s.append( pt[2])

        ax.scatter3D( array( x_s), array( y_s), array( z_s) )                
        ax.set_xlabel('X'); ax.set_ylabel('Y'); ax.set_zlabel('Z')
        p.show()
        #end

低カウント（2、5、7、13などのN）でテストされ、「うまく」動作するようです

Answer 4

試す：

function sphere ( N:float,k:int):Vector3 {
    var inc =  Mathf.PI  * (3 - Mathf.Sqrt(5));
    var off = 2 / N;
    var y = k * off - 1 + (off / 2);
    var r = Mathf.Sqrt(1 - y*y);
    var phi = k * inc;
    return Vector3((Mathf.Cos(phi)*r), y, Mathf.Sin(phi)*r); 
};

上記の関数は、N ループの合計と k ループの現在の反復を使用してループで実行する必要があります。

ヒマワリの種のパターンに基づいていますが、ヒマワリの種が半分のドームに湾曲し、再び球になっています。

カメラがすべての点から同じ距離にあるため、3D ではなく 2D に見えるようにカメラを球の内側の半分に置いたことを除いて、これは写真です。 http://3.bp.blogspot.com/-9lbPHLccQHA/USXf88_bvVI/AAAAAAAAADY/j7qhQsSZsA8/s640/sphere.jpg

Answer 5

edit: This does not answer the question the OP meant to ask, leaving it here in case people find it useful somehow.

We use the multiplication rule of probability, combined with infinitessimals. This results in 2 lines of code to achieve your desired result:

longitude: φ = uniform([0,2pi))
azimuth:   θ = -arcsin(1 - 2*uniform([0,1]))

(defined in the following coordinate system:)

Your language typically has a uniform random number primitive. For example in python you can use random.random() to return a number in the range [0,1). You can multiply this number by k to get a random number in the range [0,k). Thus in python, uniform([0,2pi)) would mean random.random()*2*math.pi.

---

Proof

Now we can't assign θ uniformly, otherwise we'd get clumping at the poles. We wish to assign probabilities proportional to the surface area of the spherical wedge (the θ in this diagram is actually φ):

An angular displacement dφ at the equator will result in a displacement of dφ*r. What will that displacement be at an arbitrary azimuth θ? Well, the radius from the z-axis is r*sin(θ), so the arclength of that "latitude" intersecting the wedge is dφ * r*sin(θ). Thus we calculate the cumulative distribution of the area to sample from it, by integrating the area of the slice from the south pole to the north pole.

(where stuff=dφ*r)

We will now attempt to get the inverse of the CDF to sample from it: http://en.wikipedia.org/wiki/Inverse_transform_sampling

First we normalize by dividing our almost-CDF by its maximum value. This has the side-effect of cancelling out the dφ and r.

azimuthalCDF: cumProb = (sin(θ)+1)/2 from -pi/2 to pi/2

inverseCDF: θ = -sin^(-1)(1 - 2*cumProb)

Thus:

let x by a random float in range [0,1]
θ = -arcsin(1-2*x)

Answer 6

または... 20 点を配置するには、20 面体の面の中心を計算します。12 点については、20 面体の頂点を見つけます。30 ポイントの場合、20 面体のエッジの中点。4 面体、立方体、12 面体、および 8 面体でも同じことができます。1 組の点は頂点にあり、別の点は面の中心にあり、もう 1 つはエッジの中心にあります。ただし、混合することはできません。

Answer 7

少数のポイントでシミュレーションを実行できます。

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)]

Answer 8

あなたの の 2 つの最大の要因を取るN場合N==20、2 つの最大の要因が{5,4}、またはより一般的には{a,b}です。計算する

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

{90-dlat/2,(dlong/2)-180}最初のポイントを、2 番目のポイントを 、 {90-dlat/2,(3*dlong/2)-180}3番目のポイントを に置き{90-dlat/2,(5*dlong/2)-180}、世界を 1 周するまで、次のポイントに{75,150}行く必要があります{90-3*dlat/2,(dlong/2)-180}。

明らかに、私はこれを球形の地球の表面で度単位で作業しており、+/- を N/S または E/W に変換するための通常の規則を使用しています。そして明らかに、これは完全に非ランダムな分布を与えますが、それは一様であり、ポイントは一緒に集まっていません.

ある程度のランダム性を追加するには、2 つの正規分布 (必要に応じて平均 0 と {dlat/3, dlong/3} の std dev) を生成し、それらを一様分布ポイントに追加します。

Answer 9

# 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)])

Answer 10

これは機能し、非常に簡単です。必要な数のポイント：

    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());
    }