Here is an image of your polygons
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
The output is
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
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.