沿CCW或CW方向对多边形的顶点进行排序 [英] Sorting vertices of a polygon in CCW or CW direction

问题描述

对于这个问题，我真的需要一些紧急帮助.

I really need some urgent help with this problem.

我有一组定义多边形(不一定是凸面)的边和顶点.顶点和边的顺序是随机的，我想按顺时针(或逆时针)方向对该多边形的顶点进行排序/排序.

I have a set of edges and vertices defining a polygon (not necessarily convex). The vertices and edges are in random order and I want to sort/order the vertices of this polygon in clockwise (or anti-clock wise) direction.

请参阅此页面以获取更详细的描述:

please see this page for more detailed description: http://www.dixittech.com/blog/2012/10/28/sorting-vertices-of-a-polygon-in-ccw-or-cw-direction/

有什么想法可以实现吗?

Any idea how this can be achieved?

推荐答案

我认为这本质上是柯尼斯堡桥问题的简化版本.

I think this is a simplified version of Königsberg Bridge Problem essentially.

如果在单个节点上连接的边缘不超过两个，则可以构建一个相邻列表并遍历所有节点.

if there's no any case that more than two edges are connected at a single node, you can build an adjacent list and "travel" through all the nodes.

如果在一个节点上连接的边缘> 2个，则……哼，我认为可能会有不止一个的顺序.只需参考柯尼斯堡桥问题的解决方案即可.

If there's case that >2 edges are connected at a node, ... hum i think there will be more than one possible order. Just refer to the solution of Königsberg Bridge Problem.

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)

这篇关于沿CCW或CW方向对多边形的顶点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！