如何生成保留给定最近邻距离的非平凡二维点集？

嘿，这个需求挺有意思的——既要严格守住每个点的最近邻距离，又要跳出平移、旋转、反射这些刚体变换的局限，还要让点集分布更随机，确实得动点脑筋。

先说说你之前用的按距离从大到小生成的方法，我懂为啥你觉得不够理想：先放的全是离得远的点，最后堆一堆近点，分布太规整了，完全没随机感。给你几个更灵活的思路，应该能解决你的问题：

• 打乱生成顺序+局部微调：不用死磕从远到近的排序，完全可以随机选点来生成。每次新增一个点后，立刻检查已经放好的点有没有出现最近邻距离不符合要求的情况——如果有冲突（比如某个已放的点的最近邻变成了新点，而不是它原本该有的那个），就把冲突的点往远离新点的方向挪一点点。注意挪的距离要小于它自己的Dx(i)的一半，这样既不会破坏它自己的最近邻距离约束，又能避开新点的干扰。这种方法能让你完全随机地生成点，同时保证所有约束都满足。

• 基于对偶图的随机重构：先把你的点集转换成一个“最近邻图”：如果点A的最近邻是点B，或者互为最近邻，就给A和B连一条边。接下来你可以对这个图做各种非刚体的变形操作：

  • 对于互为最近邻的点对，你可以把它们绕任意点旋转任意角度，或者整体平移，只要保持它们之间的距离等于对应的Dx值就行，这样它们的最近邻关系和距离都不会变。
  • 对于像A→B→C这样的链状结构（A的最近邻是B，B的最近邻是C，C的最近邻是B），你可以固定B，把A绕B转个新角度，同时把C绕B转另一个角度——只要保证A和C之间的距离大于Dx(A)和Dx(C)，它们的最近邻就还是B，约束也不会被打破。
    这种方式相当于在保留核心约束的前提下，把点集的结构拆成小块随机重组，完全不会是原集合的刚体变换。

• 基准点集+随机扰动：先用你之前的排序方法生成一个满足约束的基准点集，然后对这个点集做全局的随机扰动：

  • 每个点往随机方向移动一小段距离，移动的距离必须小于它自己Dx(i)的一半——这样就不会有其他点离它近到破坏最近邻距离的约束。
  • 对于互为最近邻的点对，你可以把它们作为一个整体来移动，或者绕它们的中点旋转，这样既能改变位置，又能保证它们之间的距离不变，最近邻关系也不受影响。
    这种方法能快速把规整的基准点集打乱，得到分布更随机的结果。

最后提个小建议：不管用哪种方法，最好每次调整后都做个校验——遍历每个点，计算它到所有其他点的最小距离，确认是不是等于对应的Dx(i)。毕竟有时候微调可能会有疏漏，校验一下能确保最终结果完全符合要求。

备注：内容来源于stack exchange，提问作者Zain