如何将四个点连接成一个凸多边形

Question

如何将四个点链接成凸多边形？我的意思是如何确定这四个点的顺序。

谢谢。

中

- Fihop

---

这是图像识别吗？你需要给出一张图片并找到其中的点吗？你尝试过什么，结果如何？ - James Black

Closers：这不是一个真正的问题吗？ - paxdiablo

我不明白“这不是一个真正的问题”是什么意思？ - Fihop

Answer 1

取中心点（即x和y坐标的平均值），然后计算y<centery和y>=centery的x/y值，我想这应该是最快的方法。

（也就是说，如果我一开始理解问题的话...）

- mvds

---

是的！我同意。这是一个很好的解决方案。以下是我的理解： 假设我们有四个二维点（a_x，a_y），（b_x，b_y）（d_x，d_y），（e_x，e_y）。我们可以计算中心点，即（c_x，c_y）。 - Fihop

找出 y > c_y 的 y 值，分别为 4 和 2，以及 y < c_y 的 y 值，分别为 1 和 3。找出 x > c_x 的 x 值，分别为 1 和 4，以及 x < c_x 的 x 值，分别为 2 和 3。 - Fihop

关于如何将这四个点连接成凸多边形，首先连接4和2，然后我们应该决定点2的下一个点，即3（因为2和3的x值小于c_x）。接下来是3和1。最后，连接1和4。 - Fihop

我猜有人可能会问，如果两个点的坐标值具有相同的c_y值或c_x值，例如一个菱形，该怎么办？是的，这可以修复。 - Fihop

在将x除以y之前，是否需要根据中心点规范化所有点的坐标？ - Fihop

Answer 2

将它们垂直排序，将两个最上面的连接在一起，将两个最下面的连接在一起。
水平排序，然后将最左边的两个连接在一起，将最右边的两个连接在一起。

编辑：无论如何，SO右侧酷炫的相关部分建议一个已回答的重复问题：按顺时针顺序排序四个点

- MK.

---

如果左上角的两个数字与顶部的两个数字相同，会发生什么？ - Maciej Hehl

这确实在基本的菱形上失败了。 - mvds

好的，取最上面的两个，然后从不同的对中选择最左边的。 菱形的形状通过说如果有两个点在同一垂直水平线上，最左边的获胜来消除歧义。 我怀疑mvds的解决方案更好，但我不完全理解它。 - MK.

我只是在寻找角度，但跳过tan-1()步骤，因为tan在感兴趣的范围内是一个递增函数。 - mvds

Answer 3

atan2() 方法非常方便，几乎所有编程语言都支持。

atan2(y,x) 可以将直角坐标 (x,y) 转换为极坐标 (r,theta) 中的角度 theta。

给定 4 个点，找到它们的平均值。然后计算通过从每个点中减去平均值而获得的四个 (x,y) 向量。

对于这些 (x,y) 向量中的每一个，计算角度 θ = atan2(y,x)。θ 的取值范围在 -π/2 和 π/2 之间。

对 θ 进行排序。这将给出点的顺序，按顺时针方向排列。

这仅适用于凸四边形。

- brainjam

---

完美~。你回答了我的问题。在把x除以y之前，需要根据中心点归一化所有点的坐标吗？ - Fihop

没有涉及除法运算。而且在atan2()函数中不需要对坐标进行归一化处理。 - brainjam

你肯定想要进行标准化。如果(cx,cy)是中心点，而(px,py)是其中的一个点，那么你将会调用atan2(py-cy,px-cx)。 - brainjam

@brainjam：我担心这种“优雅”会让我的全新电脑比2000年的那台更难以制作一个简单的Excel散点图。这种优雅属于数学分析，而不是编程。 - mvds

@brainjam：但是atan2函数深藏在你的库中，只使用了“几次”。然后有人发现在iPhone上每秒调用你的函数1000次的原因（请参见当前关于(i)phone上OCR库的开发和问题），所以只需在代码中加入一行//我们应该在这里执行atan2()，但跳过这一步更快，所有人都会很高兴。 - mvds