python - 多边形与弧段关系的建立，点、弧段、多边形间的关系以什么形式表示比较好-PHP 중국어 네트워크 Q&A

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的子集名变为字符？或者有什么更好的表达形式？

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

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)

모든 응답 (2)

巴扎黑2017-04-17 17:51:59 2층

我自己稍微寫了一下這個問題(用我自己的算法，應該結果相同)．

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:PolyFinder，此類包含兩個 methodfind_left_poly和find_right_poly用來對每個弧段尋找左右多邊形．

接著是實際定義問題跟求解的 main script:

最後是結果：

좋다+0

답글 추가

洪涛2017-04-17 17:51:59 1층

不是很明白你要做什么，不过这个应该可以帮到你

def get_var(name): return globals()[name] A=[1,2] get_var('A') # [1, 2]

涉及到复杂的数据类型，最好将其封装成类，内聚数据的操作

Php8, 나도 갈게

30분 안에 웹사이트 레이아웃 배우기

Shangguan Oracle 초보자부터 능숙한 비디오 튜토리얼까지

UNI-APP 코드의 첫 번째 줄

처음부터 앱 실행까지 Flutter

Lian 형제 새 Linux 비디오 튜토리얼

AXURE 9 비디오 튜토리얼(제품 관리자 대화형 제품 디자인 UI에 적합)

Zero 기본 숙련도 PS 비디오 튜토리얼

시작하는 데 도움이 되는 16일 UI 비디오 튜토리얼

PS 기술 및 슬라이싱 기술 비디오 튜토리얼

Alibaba Cloud 환경 구축 및 프로젝트 출시 비디오 튜토리얼

컴퓨터 네트워크 개요 - 프로그래머가 마스터해야 하는 기본 지식

프로그래머를 위한 필수 튜토리얼 - HTTP 프로토콜 설명

웹소켓 비디오 튜토리얼