如何将5个点均匀分布在一个不规则形状上？

Question

我正在尝试解决一个问题：

我有一个不规则的形状。我该如何均匀地在这个形状上分布5个点，使得每个点之间的距离相等？

- saliem

---

这是那种情况之一，图片绝对比千言万语更有说服力。 - Bill the Lizard

你的意思是在形状的边缘上选择一个任意点，然后放置4个更多的点，每个点距离上一个点的周长的1/5吗？还是你所说的点是指顶点？ - Eric

不是作业，Paul。虽然几何学从来都不是我的强项 :) - saliem

你需要澄清哪些点之间的距离是相等的。如果有三个点，它们可以放置在一个正三角形中，使得任何两个点之间的距离都与其他两个点之间的距离相同。然而，四个或更多的点不能这样放置（在二维平面上）。因此，确实需要澄清。 - Will

@starblue @Glenn Yelp API允许为给定位置/社区提供20个商家评论响应。我知道对于一些社区，有超过20家企业。起初，我只使用了社区和城市的名称。由于这没有给我网站上列出的所有结果，我打印了社区地图并放置了8-14个点。这些点是十字路口。然后我发送了包括半径和十字路口的请求。经过一些调整，这给了我60+。我想自动化大部分这个过程。不过我认为我已经找到了更好的方法。 - saliem

Answer 1

大卫说这是不可能的，但实际上有一个出乎意料的答案：只需将所有点叠放在一起！它们都与其他点具有相同的距离：零。

实际上，这是唯一的算法，无论输入形状如何，都有解（即所有成对距离相等）。

我知道问题要求将点“均匀”放置，但由于这没有正式定义，我认为那只是为了解释“所有成对距离相等”，因此我的答案是“均匀的”。

- redtuna

Answer 2

这在数学上是不可能的。它只适用于一小部分基本形状。

然而，有一些解决方案可以尝试：

1. 分析方法。从点P0开始，创建一个围绕P0的球，并与基本形状相交，得到一组曲线C0。然后在C0上创建另一个点P1。再次创建一个围绕P1的球，并与C0相交，得到一组点C1，你的第三个点P2将是C1中的一个点。以此类推。这种方法保证了距离约束，但也严重依赖于初始条件。

2. 迭代方法。实质上是形态发现。你在物体上创建一些点，并在共享距离约束的点之间创建弹簧。然后解决弹簧力并相应地移动你的点。这很可能会使它们远离基本形状，因此你需要将它们拉回基本形状。重复直到你的点不再移动或距离约束已在容差范围内满足。

3. 采样方法。将你的基本几何体转换为体素空间，并开始挖掘所有太靠近新插入点的体素。这确保你永远不会让两个点太靠近，但它也存在容差（和可能的性能）问题。

如果你能提供有关你的几何形状和约束性质的更多信息，就可以得到更具体的答案。

- David Rutten

---

你所谈论的是哪些基本形状？在空间中（至多三个维度）放置五个点且所有两点之间的距离都相等是不可能的。从你所提到的分析方法来看这很容易理解。前三个点（ABC）将形成一个等边三角形；接下来（D）将使其成为一个正四面体。当你尝试放置第五个点（E）时，如果把它放在ABC的等距位置上，它要么在D处，要么在由ABC定义的平面上D的镜像处，这样DE的距离就不正确了。 - Cascabel

我不完全确定您所说的几何形状和约束的性质是什么意思...但是这个不规则的形状是一个地区/邻域。节点是纬度和经度点。 - saliem

那么我们是在地球表面工作吗？我们是沿着形状的边缘测量距离（不是通常的度量单位！），还是直接测量（在球体上，也不是通常的度量单位！）？我们想要每个成对距离都相等，还是只是寻找AB = BC = CD = DE = EA？ - Cascabel

@saliem；通过形状的本质，我指的是它的定义。它是数学表面吗？是由三角网格定义的自由形式表面，还是Nurbs补丁。您的表面是否连续、闭合、光滑、G1等等。通过约束的本质，我只是指基本信息。您有多少个约束条件？它们都是相同的距离还是不同的距离？在您的问题中是否涉及公差？ - David Rutten

确切的说，通过具有不一定是标准三维几何形状的特定几何形状，您可以获得这种行为。在标准欧几里得三维空间中无法发生这种情况。 - aperkins

Answer 3

如果您是未来无意中发现这里的人，请查看Lloyd算法。

- Bruno

---

是的，但它只适用于规则形状，比如矩形。 - Florin Andrei

查看劳埃德的松弛算法。该算法是一种边界检测算法，您可以添加虚拟墙壁。 - Bruno

Answer 4

除了将它们穿过原点之外，使5个点彼此等距离的唯一方法是在4+维空间中。在三维空间中，有5个等距物体是数学上不可能的。最多只能有四个，而这种形状是四面体。

- binaryinitials