将矩形的顶点放入ord中

Question

我试图用python（2.7）编写一个函数。 此函数将获取8个代表顶点坐标的值的列表。
（输入格式为[Ax，Ay，Bx，By，Cx，Cy，Dx，Dy]）
函数将确定这些顶点是否是为了形成一个有效的矩形。在

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

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

我可以用哪种算法来做这件事？在

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

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")

Answer 1

我知道这是一个僵尸问题，但我找不到一个相关的新问题。所以我会把这个贴出来，以防对别人有帮助。在

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

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

注意：它使用numpy和scikit-image坐标约定：（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]

Answer 2

做一个从点1到点2的向量。在

做一个从点1到点3的向量。在

做一个从点1到点4的向量。在

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

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

如果这两个z有不同的符号（一个是负的，另一个是正的），你就有了你的观点。在

如果没有按顺序排列，则重复上述所有步骤，首先交换点3和2。如果这还不够，那么交换原始列表/数组中的点3和点4。在