In order to establish the relationship between polygon and arc segment, what form is better to express the relationship between points, arc segments and polygons

  python
A=['S3','S2','S1']
 B=['S4','S6','S1']
 C=['S2','S5','S4']
 D=['S3','S6','S5']
 N=[A,B,C,D] # node table, each point records arc segments sorted clockwise
 N0=['A','B','C','D'] # node's character table
 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] # arc segment table, each arc segment contains a start point and an end point
 S0 = ['S1',' S2',' S3',' S4',' S5',' S6'] # arc segment character table
 P=[]
 
 
 Def du(Si,P): # defines the' degree' of an arc segment. if an arc segment belongs to a polygon, the degree is added by one
 d=0
 for Pi in P:
 if Si in Pi:
 D=d plus 1
 return d
 
 for i,Si in enumerate(S0):
 for j,Nj in enumerate(N0):
 If du(Si,P)==1: # if an arc segment is equal to 1, delete it from the arc segment table
 S0.remove(Si)
 S.remove(S[i])
 Elif du(Si,P)==2: # if the arc segment degree is equal to 2, delete it from the arc segment order of the node
 N[j].remove(Si)
 else:
 Pc=[Si] # Creates Current Polygon
 Sc=Si # current edge
 Ns=S[i][0] # starting point
 Nc=S[i][1] # current point
 while Ns !  = Nc:
 k=N0.index(Nc)
 P=N[k].index(Sc) # finds the node corresponding to the current point character and finds the current edge position in the node table
 P1=p+1 # Position of Current Edge at Next Edge in Table
 if p1 > len(N[k]):
 i_p1=0
 Sc=N[k][p1] # sets the next edge as the current edge
 Pc.append(Sc) # Adds the new current edge to the polygon
 n=S0.index(Sc)
 Nc=S[n][2] # new leading point
 P.append(Pc) # Place the current polygon into the polygon group when the start and end points coincide

This is a code to establish polygon topological relations, among which I have the following questions:

1. Ignore the left polygon and the right polygon. The new front point of the left polygon is Sn and the new front point of the right polygon is Sn. This can be done by making an if to see the original current point’s position in the new current arc before determining whether it is left or right.

2. However, the structure of polygon group’ P’ does not know how to set it better. If L and R are divided into two groups in each polygon inside, will it be too complicated (the starting edge can be placed in the left polygon inside by default)

3. The node table and arc table each have a corresponding character table. It is very troublesome to find the corresponding position for processing when operating below. Is there any function that directly converts the subset name of list into characters? Or is there a better expression?

图片描述

I wrote a little bit about this problem myself (using my own algorithm, the result should be the same).

P.s. consciously did not write beautifully (just to understand this problem), we can discuss how to write it and compare elegant and pythonic.


The first is to define a system that contains all kinds ofdata classAndCore algorithmModule for:topology.pyThere is a total ofNode,NodeMgr,Edge,EdgeMgr,Polygon (website),PolyMgr,PolyFinderThere are 7 classes.

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 plus = 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)

The core algorithm class:PolyFinderThis class contains two methodfind_left_polyAndfind_right_polyUsed to find left and right polygons for each arc segment.

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 plus 1) percent 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)

The next step is to actually define the problem and solve the 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

The final result is:

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

示意圖