在回答“给定四个坐标,检查它们是否构成正方形”时,我遇到了这个答案,它先检查平行四边形,然后检查直角。这个方法可以工作,但仅当输入的点按特定顺序排列时才有效。即P1和P3必须“相对”,而不是相邻。
我知道大多数排列都是简单的旋转(
这样,我只需要检查三个基本排列:
我想不出其他方法,但似乎我漏掉了什么。有更好的方法吗?对于正方形问题给出的答案很好,但如果我必须进行额外(最多)18次检查来验证点的正确顺序,那么使用角间距离会更快。
因此问题来了:如果输入的四个点可以是任意顺序,如何将它们排序,以便它们处于“正确”的顺序以形成一个四边形?
我能想到的最简单的方法就是:
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次检查来验证点的正确顺序,那么使用角间距离会更快。