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

Question

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

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

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

Answer 1

구체에서 균일한 샘플링을 얻는 것은 어렵지 않습니다. 정규 분포 확률 변수를 사용하여 3차원 벡터를 생성한 다음 이를 단위화하면 됩니다.

으아악

그런데 인접 지점 간의 요구 사항을 충족하는지 모르겠습니다. 인접한 지점이 멀리 떨어져 있는지 확인하려면
지터링이나 계층화된 샘플링과 같은 아이디어를 통해 학습할 수 있습니다.

자바 버전

으아악

또한 CloudCompare로 저장된sphere.txt를 열어 포인트 클라우드를 볼 수 있습니다.

Answer 2

질문의 목적은 구 위의 점 사이의 거리를 최대한 크게 만드는 것이며 균일한 무작위 분포는 임의로 거리가 작은 두 점이 나타나지 않는다는 것을 보장할 수 없으므로 이 질문은 무작위와 관련이 없습니다. 영역에서의 배포(제목이 너무 기만적임).

구체에 균일하고 무작위로 분포한다는 것은 말이 너무 길어요. 이전에 @lianera가 제공한 마법의 알고리즘에 의아해합니다. 정규 분포를 사용하는 이유는 무엇입니까? 나중에 저는 단위화의 단서를 엿볼 수 있었습니다. 단위화는 실제로 부피 분포를 구에 투영한 것입니다. 정규 분포는 구형 대칭이므로 구형에 투영할 때 균일해야 합니다. 즉, 정말 중요한 것은 분포의 구형대칭이지, 구체적인 형태는 중요하지 않습니다. 예를 들어 원 안의 면적이 균일하게 분포되어 투영되면 원의 균일한 분포를 얻을 수 있습니다.

구형 코드

온라인에서 검색해보니 이 문제의 유래가 꽤 깊은데, 이를 탐메의 문제(Tamme's Problem)라고 하는데, 그 문제의 해결 방법이 '구형 코드(Spherical Codes)'라고 합니다. 다음은 몇 가지 계산된 결과입니다. 동시에 우리는 포인트가 많을 때 최적의 솔루션을 찾고 증명하는 것이 매우 어렵다는 것도 알고 있습니다. 그러므로 질문 보유자는 좋은 차선책 솔루션을 찾을 수 있습니다.

질문자가 제공한 링크는 실제로 평균 쌓기 전략을 기반으로 합니다. 즉, 구를 위도선을 사용하여 여러 개의 원으로 균등하게 나눈 다음 각 원을 동일한 각도로 나누지만 고위도에서는 원 위에 점이 더 적습니다. 낮은 위도에는 더 많은 것이 있습니다.

가장 소중한 질문

더 나은 결과를 얻으려면 다양한 최적화 툴킷을 사용하여 구형 점 사이의 최소 거리의 최대값을 찾을 수 있습니다. 목적함수를 구면점 사이의 최소거리 형태로 직접 작성한다면 함수의 안정성이 떨어지고 최적의 해를 찾기가 어려울 것이다. 여기서 목적함수는 모든 점 간격의 제곱의 역수의 합으로 취해지며 최소값을 구합니다.

$$text{최소화:} 쿼드 sum_{ilt{}j}frac{1}{d^2(i,j)}$$

이것은 인접한 지점 사이의 거리를 강조할 뿐만 아니라 기능을 비교적 부드럽게 유지합니다.

Mathematica에서 제공하는 NMinimize 기능을 사용합니다. 포인트가 많을 경우 계산하는데 시간이 오래 걸립니다. 예를 들어 내 컴퓨터에서 160점을 계산하는 데 4시간이 걸립니다. 결과 그림: