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

``````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] # starting point
Nc=S[i] # 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)
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.py`There is a total of`Node`,`NodeMgr`,`Edge`,`EdgeMgr`,`Polygon (website)`,`PolyMgr`,`PolyFinder`There 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 __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:`PolyFinder`This class contains two method`find_left_poly`And`find_right_poly`Used 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:
poly_edge.left_poly = p
print p
return p

# recursive
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:
poly_edge.right_poly = p
print p
return p

# recursive
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)`````` 