如何按顺时针顺序排序3D点？

Question

我有一堆3D点（一个数组），它们没有按照特定顺序排序，也不限于某个轴/平面。根据这些点的坐标，我想将数组按顺时针顺序排序，就像图片中那样。目前我不知道从哪里开始。一个想法是为每个点找到最近的点，然后想办法确定方向。

- trshmanx

---

3D点？在没有一个共同的参考框架（如视图平面）的情况下，"顺时针"在三维空间中没有实际意义。 - undefined

只是为了记录，还请注意，即使他们在飞机上，顺时针也取决于你从哪一边看！ - undefined

@Fattie 我以为飞机会有一个正常的。 :) - undefined

嘿！好吧，它有两个方向啊！一个方向是顺时针，另一个方向是逆时针。 - undefined

这让我想起修车的时候。"左边"是指从驾驶员坐在座位上看过去的方向。如果你在引擎盖下面工作（在前置发动机汽车中），那么"左边"就在你的右边。这使得解读服务手册的指示变得相当有趣。 - undefined

@trshmanx 你需要更多限制条件才能提供这个问题的通用解决方案。 - undefined

Answer 1

3Dave已经说过了，但这完全取决于相机的位置。

除非您指定视锥体，否则没有答案。

请注意，圆是2D而不是3D对象。 “顺时针”与圆有关。

---

假设您是指在飞机上：

这是一个有两个部分的问题。

第一部分非常困难。

第二部分相对容易。

第一部分：确实，您正在进行物体识别：您必须找到一个圆形。

为此，请调查现有的形状识别技术，或阅读类似于https://link.springer.com/article/10.1007/s11042-018-6167-2的内容。

对于第二部分（在第一部分之后几乎无关紧要）。只需获取每个点相对于您找到的圆形的中心的坐标，简单地计算每个点相对于顶部的角度，并将它们排序。

---

便宜的游戏解决方案

如果您想要便宜的解决方案，并且可以使用“合理”的点..

1. 找到所有点的重心（它只是所有点的平均值）

2. 将每个点写成从重心到该点的向量

3. 选择任何一个点作为“顶部”

4. 使用类似于此https://docs.unity3d.com/ScriptReference/Vector3.Angle.html的东西来获取每个点与“顶部”之间的角度

5. 完成！只需按顺序放置它们

实际上，您可能还需要以下内容：

6. 找到点所在的“平面”（找到它们所在的“平均平面”，这相对容易做到，查找一下！）

7. 制作通过重心的轴，该轴垂直于平面

- Fattie

---

相机可以改变。比如说绕着走等等。根据这个我可以确定方向，但是我只需要将它们排序，使得所有边缘都在外面。 - undefined

@trshmanx - 就像大家所说的那样，除非它们实际上都在同一平面上（或者可以说非常接近某个平面），否则这是没有意义的。想象一下（比如）一个��方体的八个点。你怎么���“按顺时针的方式对它们排序”呢？这是没有意义的。 - undefined

好的，假设它在飞机上，但我没有它的“中心”？ - undefined

这里可能存在一个问题。想象一下一个弯月形或肾脏形状；“中心”不会在形状内部，所以你最终得到的是一个参差不齐的线条，而不是一个多边形。这种情况可能是可以接受的！ - undefined

肯定的，伙计。OP的问题真的很难回答。首先你必须（在三维空间中）搜索一个圆，否则就是失败。我所提出的“廉价游戏式解决方案”只有在点是“合理的”情况下才有效！如果这个“廉价游戏式解决方案”不起作用，他将不得不开发一种堪称全面人工智能的解决方案。 - undefined