在 Networkx 中循环遍历节点并提取属性 [英] looping through nodes and extract attributes in Networkx

问题描述

我在python中定义了一些带有对应角点的形状，像这样:

I defined in python some shapes with corresponding corner points, like this:

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:

Then, I make use of NetworkX package to create a Graph:

G = nx.DiGraph()

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

Then, I create a node in the graph for each shape:

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

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

Now is the problem, I have to create some edges connecting two nodes if a condition is satisfied. The condition to satisfy is if the center of a shape is inside or outside another shape, then create an edge like this:

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

为此，我必须遍历节点，提取形状的center，提取的points>其他形状(不是自己，没用)并制作pointPolygonTest.

To do so, I have to loop through the nodes, extract the center of a shape, extract the points of the other shapes (NOT themselves, it's useless) and make the pointPolygonTest.

我已经尝试了很多，但没有提出任何解决方案.我得到的最接近(不是很有效)的解决方案是:

I've been trying quite much, but didn't came out with any solution. The closest (not really effective) solution I got is this:

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)

This, gives me the following output, that is not optimal because there are some relation that should have been avoided (like triangle inside triangle) or some wrong relations (like 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

我该如何解决这个问题?任何建议都值得赞赏.提醒:主要问题是如何遍历节点并提取信息.我为整个脚本导入的包是:

How can I solve this problem? Any suggestion is apreciated. Reminder: the main problem is how to loop through the nodes and extract the info. The packages I import for the whole script are:

import numpy as np
import networkx as nx
import cv2

推荐答案

这是你的多边形图像

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

First, there is no need to cast the nodes as dictionaries, we can iterate on them directly. This code is based off of this example

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

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

Since the goal is to determine if one polygon is completely inside the other, we should check all of the vertices of one polygon are inside another. Here is a tentative (unfortunately untested) solution.

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

这个例子的输出如下，现在应该是正确的.

The output for this example is as follows and now should be correct.

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 构建凸性检查，请参阅 此博客了解详情.

Note that I have made the assumption that the polygons will be convex. If this is not true, then you could check all the points on the contour instead of just the corner points. You could also build in a convexity check using cv2, see this blog for details.

这篇关于在 Networkx 中循环遍历节点并提取属性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！