0

Python(2.7)で関数を書こうとしています。この関数は、頂点の座標を表す 8 つの値のリストを受け取ります。
( 入力の形式は [Ax,Ay,Bx,By,Cx,Cy,Dx,Dy] です)
関数は、有効な長方形を形成するためにこれらの頂点が与えられているかどうかを判断します。

そうでない場合は、それらを順番に並べて、これらの頂点の並べ替えられたリストを返します。開始点または方向 (時計回りか反時計回りか) は重要ではありません。

私が望むものを説明しましょう:
与えられた入力が下のリンクの 2 番目または 3 番目の形状を形成する場合。関数はそれを最初のものに変換します。 http://i.stack.imgur.com/IsRqr.png

これを行うためにどのアルゴリズムを使用できますか?

アレクセイが提案した方法を使用して、コードを記述しました。いくつかの最適化が必要になる場合がありますが、私の 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")
4

2 に答える 2

2

点 1 から点 2 へのベクトルを作成します。

点 1 から点 3 へのベクトルを作成します。

点 1 から点 4 までのベクトルを作成します。

ベクトル 1->3 と 1->2 の外積の z 成分を計算します。

ベクトル 1->3 と 1->4 の外積の z 成分を計算します。

これらの 2 つの z の符号が異なる場合 (一方が負で、もう一方が正)、ポイントは適切です。

それらが順番どおりでない場合は、上記のすべてを繰り返し、最初にポイント 3 と 2 を交換します。それで十分でない場合は、元のリスト/ポイントの配列のポイント 3 と 4 を交換します。

于 2013-03-28T11:19:17.680 に答える
1

これは少しゾンビの質問であることは知っていますが、関連する新しい質問を見つけることができませんでした. だから、誰かに役立つ場合に備えてこれを投稿します。

これが私が使用したアルゴリズムです。これは、次の仮定に依存しています。

  • 正方形/長方形: 4 つの頂点、互いに 90 度のエッジ
  • 頂点はすでに連続しています (時計回りまたは反時計回りのいずれか)
  • -45 < R < +45 度となるように R だけ回転

注: との座標規則 (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 に答える