在n维的受限空间中，如何找到p个点的坐标，使它们尽可能彼此远离？

问题描述

例如，在2D空间中，x [0; 1]和y [0; 1]。对于p = 4，直观地讲，我将每个点放置在正方形的每个角上。

但是一般的算法是什么？

解决方案

1. 2D情况

   
   
   

   在 2D （ n = 2 ）中，解决方案是将 p 点平均放置在某个圆圈上。如果还要定义点之间的距离 d ，则圆的半径应为：

     2 * Pi * r =〜p * d 
   r =〜（p * d）/（2 * Pi）
     

   为了更加精确，您应该使用规则的p点多边形的圆周而不是圆的圆周（我太懒了）。或者，您也可以计算产生的点的距离并根据需要进行缩放。

   
   
   

   因此每个点p（i）可以定义为：

     p（i）.x = r * cos（（i * 2.0 * Pi）/ p）
   p（i）.y = r * sin（（i * 2.0 * Pi）/ p）
     




2. 3D case

   
   
   

   仅使用球体而不是圆形。




3. ND case

   
   
   

   使用 ND 超球而不是圆形。

因此，您的问题归结为放置 p 等距指向nD超球面（表面或体积）。如您所见，2D情况很简单，但是在3D中这是一个问题。请参见：

• 
  
  

  最上面的数字是用于确定模拟停止的粒子的最大abs速度，而白线是速度矢量。您需要仔细选择加速度和阻尼系数，以便快速仿真。

  
  

  For example, in a 2D space, with x [0 ; 1] and y [0 ; 1]. For p = 4, intuitively, I will place each point at each corner of the square.

  But what can be the general algorithm?

  解决方案

  1. 2D case

     In 2D (n=2) the solution is to place your p points evenly on some circle. If you want also to define the distance d between points then the circle should have radius around:

     2*Pi*r = ~p*d
     r = ~(p*d)/(2*Pi)
     

     To be more precise you should use circumference of regular p-point polygon instead of circle circumference (I am too lazy to do that). Or you can compute the distance of produced points and scale up/down as needed instead.

     So each point p(i) can be defined as:

     p(i).x = r*cos((i*2.0*Pi)/p)
     p(i).y = r*sin((i*2.0*Pi)/p)
     

  2. 3D case

     Just use sphere instead of circle.

  3. ND case

     Use ND hypersphere instead of circle.

  So your question boils down to place p "equidistant" points to a n-D hypersphere (either surface or volume). As you can see 2D case is simple, but in 3D this starts to be a problem. See:

  • Make a sphere with equidistant vertices
  • sphere subdivision triangulation

  As you can see there are quite a few approaches to do this (there are much more of them even using Fibonacci sequence generated spiral) which are more or less hard to grasp or implement.

  However If you want to generalize this into ND space you need to chose general approach. I would try to do something like this:

  1. Place p uniformly distributed place inside bounding hypersphere

     each point should have position,velocity and acceleration vectors. You can also place the points randomly (just ensure none are at the same position)...

  2. For each p compute acceleration

     each p should retract any other point (opposite of gravity).

  3. update position

     just do a Newton D'Alembert physics simulation in ND. Do not forget to include some dampening of speed so the simulation will stop in time. Bound the position and speed to the sphere so points will not cross it's border nor they would reflect the speed inwards.

  4. loop #2 until max speed of any p crosses some threshold

  This will more or less accurately place p points on the circumference of ND hypersphere. So you got minimal distance d between them. If you got some special dependency between n and p then there might be better configurations then this but for arbitrary numbers I think this approach should be safe enough.

  Now by modifying #2 rules you can achieve 2 different outcomes. One filling hypersphere surface (by placing massive negative mass into center of surface) and second filling its volume. For these two options also the radius will be different. For one you need to use surface and for the other volume...

  Here example of similar simulation used to solve a geometry problem:

  • How to implement a constraint solver for 2-D geometry?

  Here preview of 3D surface case:

  The number on top is the max abs speed of particles used to determine the simulations stopped and the white-ish lines are speed vectors. You need to carefully select the acceleration and dampening coefficients so the simulation is fast ...

  这篇关于在n维的受限空间中，如何找到p个点的坐标，使它们尽可能彼此远离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！