geometry - 在 2D 平面上定位随机点

Question

这里有一些几何知识供您引用。我已经被困在这个问题上有一段时间了:

我需要编写一个生成随机点的脚本(用 C# 编写，但请随意回答您想要的任何脚本)。 A 点具有值 x 和 y。

我必须总共生成 N 个点(其中 N > 1 并且随机最多为 100)。

点 1 必须为 x = 0，y = 0。点 2 与点 1 的距离必须为 1。因此 Root(x2 + y2) = 1。点 3 与点 2 的距离必须为 1，依此类推。

现在这是棘手的部分 - 点 N 到点 1 的距离必须为 1。因此，如果您要将所有点连接成一个形状，您将得到一个每个顶点长度相同的闭合形状。

(顶点可能会交叉，甚至可能有两个点位于完全相同的位置。只要它是随机的)。

知道如何做到这一点吗？

Answer 1

我会通过模拟链来做到这一点，有两种基本方法，一种是从正多边形开始，然后稍微随机化一个点(旋转一点)，然后迭代其余部分以维持线段size=1.

第二个是从完全随机的开链开始(如 MBo 答案)，然后迭代地改变角度，直到最后一个点与第一个点的距离达到所需的距离。我认为第二种方法编码更简单......

如果您想要更复杂的东西，那么您可以生成M个随机点并将它们作为闭合贝塞尔曲线曲线三次面片循环控制点进行处理。然后只需在其上找到 N 个等距点(这是一项艰巨的任务)并重新缩放整个物体以匹配线段大小 = 1

如果您想尝试第一种方法，那么

1. 规则多边形起点(闭环)

   从正多边形(圆上的等距点)开始。因此，将圆分成N个角段。选择半径r，使线长度匹配l=1

   

   所以r=0.5/cos(pi/N) ...来自半角三角形

2. 制作函数将第 i 个点旋转某个小步

   因此，只需以 1 半径围绕第 (i-1) 点旋转第 i-1 点，然后迭代更改 {i +1,...N} 指向匹配段大小

3. 您可以利用对称性来避免子弹 #2

   但这不会导致小 N 产生非常随机的结果。只需反转随机点 p(i) 的 2 个接触线段并循环多次即可。

   

   为了使其更加随机，您可以对整个部分(2 个随机点之间)应用对称，而不是仅在 2 条线上应用对称

第二种方法是这样的:

1. 创建随机开放链(如 MBo 的答案)

   因此所有段都已具有 size=1.0。还要记住角度而不仅仅是位置

2. i点迭代

   为简单起见，将这些点称为 p1,p2,...pn

   1. 计算d0=||pn-p1|-1.0|
   2. 将点pi向左旋转一些小da角度步长
   3. 计算dl=||pn-p1|-1.0|
   4. 将点 pi 向右旋转 2.0*da
   5. 计算dr=||pn-p1|-1.0|
   6. 将点pi旋转到原始位置...离开da

   现在选择更接近解决方案的方向(min dl,dr,d0)，因此:

   • 如果 d0 最小，则根本不改变这一点并停止
   • 如果 dl 最小，则在 dl 降低时向左旋转 da
   • 如果 dr 最小，则在 dr 降低时向右旋转 da

3. 解决方案

   循环子弹#2，同时d=||pn-p0|-1.0|正在降低，然后将da更改为 da*=0.1 并再次循环。如果da步太小或者循环迭代后d没有变化，则停止。

[注释]

Booth 解决方案并不精确，您的距离将非常接近 1.0，但可能会存在 +/- 一些误差，具体取决于最后的 da 步长。如果旋转点 pi，则只需向所有 pi,pi+1,pi+2,..pn 点添加/子角度