0

我正在尝试在 python(2.7) 中编写一个函数。该函数将采用一个包含 8 个值的列表，这些值表示顶点的坐标。
（输入的形式是 [Ax,Ay,Bx,By,Cx,Cy,Dx,Dy] ）
该函数将确定这些顶点是否被给出以形成一个有效的矩形。

如果不是，它会将它们按顺序排列并返回这些顶点的排序列表。起点或方向（是顺时针还是逆时针）并不重要。

让我说明我想要什么：
如果给定的输入在下面的链接中形成第二或第三个形状；该函数会将其转换为第一个。 http://i.stack.imgur.com/IsRqr.png

我可以使用哪种算法来做到这一点？

我使用了 Alexey 建议的方式并编写了我的代码。它可能需要一些优化，但对我来说不是必需的。

def crossProduct(vector1,vector2) :
    a,b,c = vector1
    d,e,f = vector2
    vector3 = (b*f-c*e , -a*f+c*d , a*e-b*d)
    return vector3

def fixRect(rectList) :
    Ax,Ay,Bx,By,Cx,Cy,Dx,Dy = rectList[:]
    v12 = (Bx-Ax,By-Ay,0)
    v13 = (Cx-Ax,Cy-Ay,0)
    v14 = (Dx-Ax,Dy-Ay,0)
    z1 = crossProduct(v13,v12)[2]
    z2 = crossProduct(v13,v14)[2]
    if z1*z2 < 0 : # if two z values have different sign, they are in order
        return [Ax,Ay,Bx,By,Cx,Cy,Dx,Dy]
    # else swap 2 and 3
    Ax,Ay,Cx,Cy,Bx,By,Dx,Dy = rectList[:]
    # repeat
    v12 = (Bx-Ax,By-Ay,0)
    v13 = (Cx-Ax,Cy-Ay,0)
    v14 = (Dx-Ax,Dy-Ay,0)
    z1 = crossProduct(v13,v12)[2]
    z2 = crossProduct(v13,v14)[2]
    if z1*z2 < 0 : # if two z values have different sign, they are in order
        return [Ax,Ay,Bx,By,Cx,Cy,Dx,Dy]
    # else swap 3 and 4
    Ax,Ay,Bx,By,Dx,Dy,Cx,Cy = rectList[:]
    # repeat
    v12 = (Bx-Ax,By-Ay,0)
    v13 = (Cx-Ax,Cy-Ay,0)
    v14 = (Dx-Ax,Dy-Ay,0)
    z1 = crossProduct(v13,v12)[2]
    z2 = crossProduct(v13,v14)[2]
    if z1*z2 < 0 : # if two z values have different sign, they are in order
        return [Ax,Ay,Bx,By,Cx,Cy,Dx,Dy]
    else: raise Exception("Couldn't fix the rectangle")
4

2 回答 2

2

制作从点 1 到点 2 的向量。

制作从点 1 到点 3 的向量。

制作一个从点 1 到点 4 的向量。

计算向量 1->3 和 1->2 的叉积的 z 分量。

计算向量 1->3 和 1->4 的叉积的 z 分量。

如果这两个 z 有不同的符号（一个是负数，另一个是正数），那么你的观点是有序的。

如果它们不按顺序排列，请重复上述所有操作，首先交换点 3 和 2。如果这还不够，则交换原始点列表/数组中的点 3 和 4。

于 2013-03-28T11:19:17.680 回答
1

我知道这有点像僵尸问题，但我找不到相关的新问题。所以我会发布这个以防它对某人有帮助。

这是我使用的算法。它依赖于以下假设：

  • 它是一个正方形/矩形：4 个顶点，彼此成 90 度的边
  • 顶点已经按顺序排列（顺时针或逆时针）
  • 它被 R 旋转，使得 -45 < R < +45 度

注意：它使用和坐标约定：(Y,X)，左上角为 (0,0)。

import numpy as np
def sorted_rect(vec):
    # returns vec in clockwise order, starting with topleft
    normd = vec - np.average(vec,axis=0) # vertices relative to centroid
    tl_idx = np.argmax(np.dot(normd,np.array([-1,-1]))) #index of top left vertex
    clockwise = np.cross(vec[(tl_idx+1) % 4] - vec[tl_idx],
                         vec[tl_idx] - vec[tl_idx-1]) > 0
    return np.roll(vec,-tl_idx,axis=0) if clockwise else np.roll(vec,-1-tl_idx,axis=0)[::-1]
于 2016-07-14T11:24:47.437 回答