多边形与弧段关系的建立，点、弧段、多边形间的关系以什么形式表示比较好_Python_论坛

多边形与弧段关系的建立，点、弧段、多边形间的关系以什么形式表示比较好

黄***得分类：Python 人气：1481 回帖：2 发布于6年前收藏

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

标签：python

讨论这个帖子（2）垃圾回帖将一律封号处理……

Lv5 码农

zh***ao 职业无 6年前#1

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

def get_var(name):
    return globals()[name]

A=[1,2]
get_var('A') # [1, 2]

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

Lv2 入门

钱***8 软件测试工程师 6年前#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 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)

文明上网，理性发言！ 😉 阿里云幸运券，戳我领取