A=['S3','S2','S1']
B=['S4','S6','S1']
C=['S2','S5','S4']
D=['S3','S6','S5']
N=[A,B,C,D] #节点表,每个点记录顺时针方向排序的弧段
N0=['A','B','C','D'] #节点的字符表
S1=['A','B']
S2=['C','A']
S3=['D','A']
S4=['B','C']
S5=['C','D']
S6=['B','D']
S=[S1,S2,S3,S4,S5,S6] #弧段表,每个弧段含有起始点和终点
S0=['S1','S2','S3','S4','S5','S6'] #弧段的字符表
P=[]
def du(Si,P): #定义弧段的‘度’,弧段属于一个多边形度就加一
d=0
for Pi in P:
if Si in Pi:
d=d+1
return d
for i,Si in enumerate(S0):
for j,Nj in enumerate(N0):
if du(Si,P)==1: #如果某弧段度等于1,将其从弧段表中删去
S0.remove(Si)
S.remove(S[i])
elif du(Si,P)==2: #如果某弧段度等于2,将其从节点的弧段排序中删去
N[j].remove(Si)
else:
Pc=[Si] #建立当前多边形
Sc=Si #当前边
Ns=S[i][0] #起点
Nc=S[i][1] #当前点
while Ns != Nc:
k=N0.index(Nc)
p=N[k].index(Sc) #寻找当前点字符对应的节点,并在结点表中找到当前边位置
p1=p+1 #当前边在表中下一条边的位置
if p1 > len(N[k]):
i_p1=0
Sc=N[k][p1] #把下一条边设为当前边
Pc.append(Sc) #把新的当前边加入多边形中
n=S0.index(Sc)
Nc=S[n][2] #新当前点
P.append(Pc) #起点终点重合时将当前多边形放入多边形组中
这是一个建立多边形拓扑关系的代码,其中我有以下几个问题:
1.忽略了左多边形和右多边形,左多边形的新当前点为Sn,右多边形新当前点为Sn,这个可以先做个if看原本的当前点在新的当前弧中的位置,再确定是左还是右
2.但是多边形组'P'的结构不知道怎么设置比较好,如果在每个多边形里再分L,R两个分组会不会太复杂(起始边可以默认放在左多边形里)
3.节点表和弧段表每个都有对应的字符表,下边运算的时候还要找相应位置进行处理,挺麻烦,有没有什么函数直接把list的子集名变为字符?或者有什么更好的表达形式?
我自己稍微寫了一下這個問題(用我自己的算法,應該結果相同).
P.S. 自覺寫得沒有很漂亮(只是為了解這個問題),我們可以再討論應該怎麼寫會比較 elegant 和 pythonic
首先是定義一個含有各種 data class 和 核心算法 的 module: topology.py
,裡面一共有 Node
, NodeMgr
, Edge
, EdgeMgr
, Polygon
, PolyMgr
, PolyFinder
共7個類.
class Node:
def __init__(self, name):
self.name = name
def set_edges(self, *edges):
self.edges = edges
def __repr__(self):
return 'Node({0})'.format(self.name)
class NodeMgr:
def __init__(self):
self.nodes = {}
def set_edge_mgr(self, edge_mgr):
self.edge_mgr = edge_mgr
def create_node(self, name):
self.nodes[name] = Node(name)
return self.nodes[name]
def set_edges(self, name, *edge_names):
self.nodes[name].set_edges(*(self.edge_mgr.get_edge(edge_name) for edge_name in edge_names))
def get_node(self, name):
return self.nodes.get(name, None)
def __len__(self):
return len(self.nodes)
def __iter__(self):
return iter(self.nodes.items())
class Edge:
def __init__(self, name, start_node, end_node):
self.name = name
self.start_node = start_node
self.end_node = end_node
self.left_poly = None
self.right_poly = None
def __repr__(self):
return 'Edge({0}, {1}, {2})'.format(self.name, self.start_node, self.end_node)
class EdgeMgr:
def __init__(self):
self.edges = {}
def set_node_mgr(self, node_mgr):
self.node_mgr = node_mgr
def create_edge(self, name, start_node_name, end_node_name):
start_node = self.node_mgr.get_node(start_node_name)
end_node = self.node_mgr.get_node(end_node_name)
self.edges[name] = Edge(name, start_node, end_node)
return self.edges[name]
def get_edge(self, name):
return self.edges.get(name, None)
def __iter__(self):
return iter(self.edges.items())
def __len__(self):
return len(self.edges)
class Polygon:
def __init__(self, name):
self.name = name
self.edges = set()
def add_edge(self, edge):
self.edges.add(edge)
def __repr__(self):
return 'Polygon({0})'.format(self.name)
def __iter__(self):
return iter(self.edges)
class PolyMgr:
def __init__(self):
self.polys = {}
self.index = 0
def create_poly(self):
name = 'P{0}'.format(self.index)
self.polys[name] = Polygon(name)
self.index += 1
return self.polys[name]
def get_poly(self, name):
return self.polys.get(name, None)
def __iter__(self):
return iter(self.polys.items())
def __len__(self):
return len(self.polys)
核心演算法 class: PolyFinder
,此類包含兩個 method find_left_poly
和 find_right_poly
用來對每個弧段尋找左右多邊形.
class PolyFinder:
def __init__(self, poly_mgr):
self.poly_mgr = poly_mgr
def find_left_poly(self, edge, poly_edges):
print edge, '->',
# check if left polygon exists
if not edge.left_poly is None:
print edge.left_poly, 'exists'
return edge.left_poly
# loop -> new a poly
if edge in poly_edges:
p = self.poly_mgr.create_poly()
for poly_edge in poly_edges:
p.add_edge(poly_edge)
poly_edge.left_poly = p
print p
return p
# recursive
poly_edges.add(edge)
idx = edge.end_node.edges.index(edge)
next_idx = idx - 1
next_edge = edge.end_node.edges[next_idx]
if next_edge.start_node != edge.end_node:
print 'there is no left poly'
return None
return self.find_left_poly(next_edge, poly_edges)
def find_right_poly(self, edge, poly_edges):
print edge, '->',
# check if right polygon exists
if not edge.right_poly is None:
print edge.right_poly, 'exists'
return edge.right_poly
# loop -> new a poly
if edge in poly_edges:
p = self.poly_mgr.create_poly()
for poly_edge in poly_edges:
p.add_edge(poly_edge)
poly_edge.right_poly = p
print p
return p
# recursive
poly_edges.add(edge)
idx = edge.end_node.edges.index(edge)
next_idx = (idx + 1)%len(edge.end_node.edges)
next_edge = edge.end_node.edges[next_idx]
if next_edge.start_node != edge.end_node:
print 'there is no right poly'
return None
return self.find_right_poly(next_edge, poly_edges)
接著是實際定義問題跟求解的 main script:
from topology import Node, NodeMgr, Edge, EdgeMgr, Polygon, PolyMgr
from topology import PolyFinder
if __name__ == '__main__':
# create nodes
node_mgr = NodeMgr()
edge_mgr = EdgeMgr()
node_mgr.set_edge_mgr(edge_mgr)
edge_mgr.set_node_mgr(node_mgr)
for name in 'ABCD':
node_mgr.create_node(name)
# create edges
edge_mgr.create_edge('S1', 'A', 'B')
edge_mgr.create_edge('S2', 'C', 'A')
edge_mgr.create_edge('S3', 'D', 'A')
edge_mgr.create_edge('S4', 'B', 'C')
edge_mgr.create_edge('S5', 'C', 'D')
edge_mgr.create_edge('S6', 'B', 'D')
# node table
node_mgr.set_edges('A', 'S3', 'S2', 'S1')
node_mgr.set_edges('B', 'S4', 'S6', 'S1')
node_mgr.set_edges('C', 'S2', 'S5', 'S4')
node_mgr.set_edges('D', 'S3', 'S6', 'S5')
# algorithm
poly_mgr = PolyMgr()
poly_finder = PolyFinder(poly_mgr)
print '---- Search ----'
for name, edge in edge_mgr:
print 'find left of {0}: '.format(name)
left_poly = poly_finder.find_left_poly(edge, set())
print 'find right of {0}: '.format(name)
right_poly = poly_finder.find_right_poly(edge, set())
print '\n---- Result ----'
for name, poly in poly_mgr:
print name, [edge for edge in poly]
for name, edge in edge_mgr:
print name, 'left poly ->', edge.left_poly
print name, 'right poly->', edge.right_poly
最後是結果:
---- Search ----
find left of S3:
Edge(S3, Node(D), Node(A)) -> Edge(S1, Node(A), Node(B)) -> Edge(S6, Node(B), Node(D)) -> Edge(S3, Node(D), Node(A)) -> Polygon(P0)
find right of S3:
Edge(S3, Node(D), Node(A)) -> there is no right poly
find left of S2:
Edge(S2, Node(C), Node(A)) -> there is no left poly
find right of S2:
Edge(S2, Node(C), Node(A)) -> Edge(S1, Node(A), Node(B)) -> Edge(S4, Node(B), Node(C)) -> Edge(S2, Node(C), Node(A)) -> Polygon(P1)
find left of S1:
Edge(S1, Node(A), Node(B)) -> Polygon(P0) exists
find right of S1:
Edge(S1, Node(A), Node(B)) -> Polygon(P1) exists
find left of S6:
Edge(S6, Node(B), Node(D)) -> Polygon(P0) exists
find right of S6:
Edge(S6, Node(B), Node(D)) -> there is no right poly
find left of S5:
Edge(S5, Node(C), Node(D)) -> there is no left poly
find right of S5:
Edge(S5, Node(C), Node(D)) -> Edge(S3, Node(D), Node(A)) -> there is no right poly
find left of S4:
Edge(S4, Node(B), Node(C)) -> Edge(S5, Node(C), Node(D)) -> there is no left poly
find right of S4:
Edge(S4, Node(B), Node(C)) -> Polygon(P1) exists
---- Result ----
P0 [Edge(S6, Node(B), Node(D)), Edge(S1, Node(A), Node(B)), Edge(S3, Node(D), Node(A))]
P1 [Edge(S2, Node(C), Node(A)), Edge(S4, Node(B), Node(C)), Edge(S1, Node(A), Node(B))]
S3 left poly -> Polygon(P0)
S3 right poly-> None
S2 left poly -> None
S2 right poly-> Polygon(P1)
S1 left poly -> Polygon(P0)
S1 right poly-> Polygon(P1)
S6 left poly -> Polygon(P0)
S6 right poly-> None
S5 left poly -> None
S5 right poly-> None
S4 left poly -> None
S4 right poly-> Polygon(P1)