玩蛇网提供最新Python编程技术信息以及Python资源下载!

python算法. 在球面上取随机N个均匀的点(或者间距不小于某距离的点)

希望能在球上获得均匀分布, 或者 每两个点之间的间距不小于某个值的N个点的坐标.
点的数量不需要太大, 在100到200之间就够用了.
球的中心点就是坐标系原点.

有看到另外一个大牛写的.
https://www.oschina.net/code/...
但是传入100个点的时候, 相邻很近的点出现几率非常大. 导致在球面上的点上放东西的时候, 就叠在一起了.

求教, 有没有什么其他算法能实现.

球面上要实现均匀采样不难,用正态分布随机变量产生三维向量再单位化就可以了。

#include <iostream>
#include <fstream>
#include <random>

using namespace std;

int main()
{
    std::default_random_engine gen;
    std::normal_distribution<float> distrib(0.f, 1.f);

    ofstream ofs("sphere.txt");
    for (int i = 0; i < 1000; i++) {
        float x = distrib(gen);
        float y = distrib(gen);
        float z = distrib(gen);
        float r = sqrt(x*x + y*y + z*z);
        ofs << x / r << ' ' << y / r << ' ' << z / r << endl;
    }
    return 0;
}

不过不知道满不满足相邻点之间的要求。如果要保证相邻点比较远,可以借鉴一下
jittering或者stratified sampling之类的思路。

Java版

import java.util.Random;
import java.io.*;

class SphericalSampling{
    public static void main(String[] args){
        Random rnd = new Random();
        try{
            PrintWriter writer = new PrintWriter("sphere.txt", "UTF-8");
            for(int i = 0; i < 1000; i++){
                double x = rnd.nextGaussian();
                double y = rnd.nextGaussian();
                double z = rnd.nextGaussian();
                double r = Math.sqrt(x*x + y*y + z*z);
                writer.println(x/r + " " + y/r + " " + z/r);
            }            
        }catch (Exception e) {
               e.printStackTrace(System.out);
        }
    }
}

另外,保存的sphere.txt可以用CloudCompare打开查看点云。

题主的意思是想让球面上的点间距尽量大,而均匀随机分布无法保证不出现距离任意小的两点,所以这个题与球面上的随机分布无关(标题太坑人)。

这个问题本质是求解球面点最小间距的最大值,各种优化工具包可以各显神通了。如果目标函数直接写成球面点最小间距的形式,函数稳定性很差,不容易求到最优解。这里将目标函数取为所有点间距平方的倒数和并求最小值:

$$\text{minimize:} \quad \sum_{i\lt{}j}\frac{1}{d^2(i,j)}$$

这样既突出了相邻点间距又保持函数相对平滑。

我用的是Mathematica提供的NMinimize函数,点数比较多时需要很长计算。比如在我机器上算160个点需要四个小时。结果画图:

Spherical Codes

网上一搜才发现,原来这个问题还是蛮有来头的,叫做Tamme's problem,问题的解称为“spherical codes”。这里有一些计算好的结果。同时也知道,当点数比较多时寻找和证明最优解是很困难的。所以题主找到个还不错的次优解就可以啦。

球面均匀随机分布

啰嗦一句球面均匀分布吧。前面大神给出的神奇算法我百思不得其解,为啥用正态分布?后来从单位化上窥见了端倪:单位化其实是体分布到球面的投影。因为正态分布是球对称的,因此它投影到球面上就一定是均匀的了。也就是说,真正重要的是分布的球对称性,具体形式无所谓。比如圆内的面积均匀分布投影可以得到圆上的均匀分布:

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd13731.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月24日 - 14时41分43秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules