按顺时针顺序对四个点排序

  • Z时代
  • 2024-01-10
  • 分类：问答

阵列中的四个2D点。我需要按顺时针顺序对其进行排序。我认为仅需执行一次交换操作就可以完成，但是我无法正式将其删除。

编辑：在我的情况下，这四个点是凸多边形。

编辑：这四个点是凸多边形的顶点。他们不必井井有条。

回答：

如果您想从数学的角度出发，我们可以考虑4点的排列

在我们的例子中，有4个排列按顺时针顺序排列

A B C D
B C D A
C D A B
D A B C

所有其他可能的排列都可以通过0或1交换转换为这些形式之一。（我将只考虑以A开头的排列，因为它是对称的）

  1. ABCD-完成

  2. ABDC-交换C和D

  3. ACBD-交换B和C

  4. ACDB-交换A和B

  5. ADBC-交换A和D

  6. ADCB-交换B和D

因此，只需要进行一次交换-但是可能需要一些工作才能确定哪个。

通过查看前三个点，并检查ABC签名区域的符号，我们可以确定它们是否为顺时针方向。如果它们是顺时针的，那么我们是1 2或5

为了区分这些情况，我们必须检查另外两个三角形-如果ACD是顺时针方向，则可以将其缩小到情况1，否则我们必须处于情况2或5。

为了选择情况2和5，我们可以测试ABD

我们可以类似地逆时针检查ABC的情况。

在最坏的情况下，我们必须测试3个三角形。

如果您的点不是凸的，则可以找到内部点，对其余点进行排序，然后将其添加到任何边缘。请注意，如果四边形是凸的，则不再有4个点唯一地确定该四边形，而是有3个同等有效的四边形。

以上是 按顺时针顺序对四个点排序 的全部内容， 来源链接： utcz.com/qa/433406.html

回到顶部