遍历节点并提取Networkx中的属性

Question

我在python中定义了一些具有相应拐角点的形状，例如：

square = [[251, 184],
          [22, 192],
          [41, 350],
          [244, 346]]

triangle = [[250, 181],
            [133, 43],
            [21, 188]]

pentagon = [[131,  37],
            [11, 192],
            [37, 354],
            [247, 350],
            [256, 182]]

然后，我利用NetworkX包创建一个Graph：

G = nx.DiGraph()

然后，在图形中为每个形状创建一个节点：

G.add_node('square', points = square, center = (139, 265))
G.add_node('triangle', points = triangle, center = (139, 135))
G.add_node('pentagon', points = pentagon, center = (138, 223))

现在是问题所在，如果满足条件，我必须创建一些连接两个节点的边。要满足的条件是，形状的中心是在另一个形状的内部还是外部，则创建这样的边：

G.add_edge('triangle', 'pentagon', relation = 'inside')
G.add_edge('triangle', 'square', relation = 'outside')

要做到这一点，我必须通过环路节点，提取center后的形状，提取points了的其他形状（不是自己，也没用），并使pointPolygonTest。

我一直在努力，但是没有提出任何解决方案。我得到的最接近的（不是很有效的）解决方案是这样的：

nodes_p=dict([((u),d['points']) for u,d in G.nodes(data=True)])
nodes_c=dict([((u),d['center']) for u,d in G.nodes(data=True)])
for z,c in nodes_c.items():
    print z + ' with center', c
    for z,p in nodes_p.items():
        p_array = np.asarray(p)
        if cv2.pointPolygonTest(p_array,c,False)>=0:
            print 'inside ' + z
            #create edge
        else:
            print 'outside ' + z
            #create edge

这给了我以下输出，因为不是应该避免某些关系（如triangle inside triangle）或某些错误的关系（如pentagon inside square），所以它不是最佳的输出

triangle with center (139, 135)
inside triangle
outside square
inside pentagon
square with center (139, 265)
outside triangle
inside square
inside pentagon
pentagon with center (138, 223)
outside triangle
inside square
inside pentagon

我怎么解决这个问题？任何建议都很赞赏。提醒：主要问题是如何遍历节点并提取信息。我为整个脚本导入的软件包是：

import numpy as np
import networkx as nx
import cv2

Answer 1

这是您的多边形的图像

首先，不需要将节点强制转换为字典，我们可以直接对其进行迭代。此代码基于此示例

for u,outer_d in G.nodes(data=True):
   center = outer_d['center']
   print u, "with center", center
   for v, inner_d in G.nodes(data=True):
        #Don't compare self to self
        if u != v:
            # Create a source image
            src = np.zeros((400,400),np.uint8)          
            # draw an polygon on image src
            points = np.array(inner_d['points'],np.int0)
            cv2.polylines(src,[points],True,255,3)
            contours,_ = cv2.findContours(src,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
            if cv2.pointPolygonTest(contours[0],center,True) <= 0:
                print 'outside',v
            else:
                print 'inside',v

输出是

pentagon with center (138, 223)
inside square
outside triangle
square with center (139, 265)
inside pentagon
outside triangle
triangle with center (139, 135)
inside pentagon
outside square

由于目标是确定一个多边形是否完全在另一个多边形内，因此我们应检查一个多边形的所有顶点是否在另一个多边形内。这是一个暂定（不幸的是未经测试）的解决方案。

def checkPoint(point, poly,r=400):
    ''' determine if point is on the interior of poly'''
    # Create a source image
    src = np.zeros((r,r),np.uint8)       
    # draw an polygon on image src
    verts = np.array(poly,np.int0)
    cv2.polylines(src,[verts],True,255,3)
    contours,_ = cv2.findContours(src,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
    return cv2.pointPolygonTest(contours[0],tuple(point),True) > 0:


for u,outer_d in G.nodes(data=True):
    points = outer_d['points']
    center = outer_d['center']
    print u, "with center", center
    for v, inner_d in G.nodes(data=True):
        poly = inner_d['points']
        if u != v:
            if all([checkPoint(point,poly) for point in points]):
                print 'inside',v
            else:
                print 'outside',v

此示例的输出如下，现在应该正确。

pentagon with center (138, 223)
outside square
outside triangle
square with center (139, 265)
inside pentagon
outside triangle
triangle with center (139, 135)
inside pentagon
outside square

请注意，我已经假设多边形将是凸的。如果不是这样，则可以检查轮廓上的所有点，而不仅仅是角点。您也可以使用来建立凸度检查cv2，有关详细信息，请参见此博客。