3

在回答“给定四个坐标检查它是否形成正方形”时，我遇到了这个答案，它检查平行四边形，然后检查直角。这有效，但前提是输入的点按特定顺序。也就是说，P1 和 P3 必须彼此“相对”，而不是相邻。

所以，问题。如果进来的四个点可以按任何顺序排列，你如何对它们进行排序，使它们按“正确”的顺序排列成一个四边形？

我能想到的最简单的事情是：

for each valid permutation of points[]{ // see below for "valid"
    generate line segment for:
        points[0] -> points[1]
        points[1] -> points[2]
        points[2] -> points[3]
        points[3] -> points[0]
    if any line segment crosses another // use cross product
        continue
    return permutation
}

我知道大多数排列都是简单的旋转（0123 == 1230），所以我可以保持第一点“固定”。0另外，我认为我可以通过仅考虑每个排列点的和中的点来减少它2，因为其他两个的顺序无关紧要。例如，如果0123是一个多边形，0321也是，因为它生成相同的线段。

这让我只需要检查三个基本排列：

  • [0,1,2,3]
  • [0,1,3,2]
  • [0,2,1,3]

每个排列都有六个段到段检查，所以总共有 18 次比较。

我想不出任何其他方法来做到这一点，但似乎我错过了一些东西。有一个更好的方法吗？为方形问题给出的答案很好，但如果我必须进行额外（最多）18 次检查以验证点的顺序是否正确，那么使用角间距离会更快。

4

4 回答 4

2

每个排列都有六个段到段检查，所以总共有 18 次比较。

您不需要检查所有线段：检查线段[0-2]和[1-3]（即两条对角线）相交就足够了。您需要检查线段是否相交，而不是线段所属的线，即线段之外的交叉点不算在内。

一旦你确定了起点"A"，你最终会得到六种可能的排列：

在此处输入图像描述

其中两个（A-B-D-C和A-C-D-B）是好的；剩下的四个是坏的。只需两张支票，您就可以得到一张好的：

  • 检查初始排列；如果好，就留着；否则
  • 交换点 1 和 2，并检查排列；如果好，就留着；否则
  • 恢复到原始排列，交换点 2 和 3，并保持该排列；它一定是“好”的。
于 2013-08-06T16:10:29.567 回答
1

您不能简单地检查以下所有内容，直到找到正确的内容吗？（即检查P1对面的点）

P3 = P1 + (P2-P1) + (P4-P1)
P2 = P1 + (P3-P1) + (P4-P1)
P4 = P1 + (P2-P1) + (P3-P1)

对于方形变体，如果它们恰好是轴对齐的，您可以这样做：（也就是说，相反的点是没有共同坐标的点）

if (P1.x != P3.x && P1.y != P3.y)
  check P3 = P1 + (P2-P1) + (P4-P1)

if (P1.x != P2.x && P1.y != P2.y)
  check P2 = P1 + (P3-P1) + (P4-P1)

if (P1.x != P4.x && P1.y != P4.y)
  check P4 = P1 + (P2-P1) + (P3-P1)

otherwise return false
于 2013-08-06T15:57:11.870 回答
1

实现一个名为 isParallelAndEqual(p0,p1,q0,q1) 的方法。这将检查线 p1-p1 和 q0-q1 是否平行且长度相等。

给定点 a、b、c 和 d，最终结果如下所示：

ifParallelAndEqual(a,b,c,d)||ifParallelAndEqual(a,c,b,d)

于 2013-08-06T15:45:37.560 回答
0

执行以下操作会不会更简单：

  1. 检查点是否0, 1跨越2三角形（如果它们是共线的，则四边形也是退化的）
  2. 检查以下路段是否有交集：

[0, 3] and [1, 2]
[1, 3] and [0, 2]
[2, 3] and [0, 1]

如果它们都不相交，则四边形是非凸的。

否则，您应该只有一个相交的案例。您在那里找到了相反的顶点。

于 2013-08-06T15:45:09.900 回答