sorting - ポリゴンの頂点を CCW または CW 方向に並べ替える

Question

多角形を定義するエッジと頂点のセットがあります (必ずしも凸状である必要はありません)。頂点とエッジはランダムな順序であり、このポリゴンの頂点を時計回り (または反時計回り) にソート/順序付けしたいと考えています。

これをどのように達成できるか考えていますか?

Answer 1

これは本質的にケーニヒスベルク橋問題の簡略版だと思います。

1 つのノードで 2 つ以上のエッジが接続されているケースがない場合は、隣接するリストを作成して、すべてのノードを「移動」できます。

ノードで 2 つ以上のエッジが接続されている場合、...うーん、複数の順序が考えられると思います。ケーニヒスベルク橋問題の解を参照してください。

for v,u in edges:
  adjacent[v].append(u)
  adjacent[u].append(v)

order=[]

start = v0 #start from an arbitrary node

def draw(now,last):
  if now==start and len(order)>0:
    return
  order.append(now)
  for i in adjacent[now]:
    if i != last:
      draw(i,now)

draw(start,NULL)

Answer 2

私は CW/CCW 方向は問題ではないと仮定しています (どちらかを保証するのはもっと複雑です)。この疑似コード アルゴリズムは、CW または CCW のいずれかで頂点を並べ替えます。

marked_edge <- any edge
first <- marked_edge.start
list <- [first]
current <- marked_edge.end
while current <> first
    list <- list + [current]
    new_edge <- find the edge that is not the marked_edge and has the vertex current as either start or end
    if new_edge.start=current then
        current <- new_edge.end
    else
        current <- new_edge.start
   endif
   marked_edge <- new_edge
endwhile