Right data structure for containing shapes and spatial relations between them

Question

I am a BEGINNER of Python and I would really need some help.

I have a (working) script that retrieves simple shapes in images drawn by hand. The next step is to determine the spatial relations between the shapes and a data structure that contains all those information. I know how to determine the spatial relations between the shapes, like inside, next to, above and below. However, I need a data structure to contain all those information: shapes (x,y) coordinate of the edges and relation with other shapes. I was thinking about a hierarchical representation, something like this picture:

In which each shape contains the info.

Shape = (x0, y0, ..., xn, yn), position(Shape)

where

• (x0, y0, ..., xn, yn) are the coordinates of the edges of the shape
• position(Shape) is the relation of the shape against another.

For example:

S1: (x0, y0, x1, y1, x2, y2, x3, y3), below(T1)
T1: (x0, y0, x1, y1, x2, y2), above(S1)
C1: (radius), inside(S1), above(C2)
C2: (radius), inside(S1), below(C1)

But how to implement it in python? I read about dictionaries (here) but I am not sure if it's the right tool to use here. Why? Because I need to write in the data structure the position of a shape against others. So how could I write this relation? I am quite confused about the argument and I would really need an help.

Answer 1

Just as update for everybody is interested and for completeness, I used the Python package Natworkx as suggested by @Cilyan. The package gives me the opportunity to make a graph (as I need) and also supplies a data structure dictionary-like for keeping the information. Starting from one of the picture I got from experiments, the graph is correctly created, as shown in the following picture:

And, the data structure to keep the information looks like this:

nodes of the graph:

[('3-gon', {'points': array([[250, 181],
                             [133,  43],
                             [ 21, 188]]), 
            'center': (139, 135)}), 
 ('4-gon', {'points': array([[251, 184],
                             [ 22, 192],
                             [ 41, 350],
                             [244, 346]]), 
            'center': (139, 265)}), 
 ('5-gon', {'points': array([[131,  37],
                             [ 11, 192],
                             [ 37, 354],
                             [247, 350],
                             [256, 182]]), 
            'center': (138, 223)})]

edges of the graph:

[('3-gon', '5-gon', {'relation': 'inside'}), 
 ('4-gon', '3-gon', {'relation': 'below'}), 
 ('4-gon', '5-gon', {'relation': 'inside'})]

Thanks for your help guys! I've really apreciated.

Answer 2

Use Python's classes for this.

A simple example. Let's first define a Point data structure that will hold information about a point in cartesian coordinates:

class Point(object):
    """ Define a point at X, Y """
    def __init__(self, x=0, y=0):
        self.x=x
        self.y=y

Now let's define a circle:

class Circle(object):
    def __init__(self, x=0, y=0, radius=1):
        """ Define a circle centered at X, Y with radius """
        self.x=x
        self.y=y
        self.radius=radius

Now you can declare an instance of each and test if the point is inside the circle:

>>> c1=Circle()      # default of x=0, y=0, radius=1
>>> p1=Point(5,6)    # a point at x=5, y=6

Is that point inside the circle? You can test it:

>>> ((p1.x-c1.x)**2 + (p1.y - c1.y)**2)**0.5<c1.radius
False

That would be a whole lot easier if we did not have to remember the pythagorian theorem for the circle's center and the point. Let's add that basic functionality to the Circle object:

class Circle(object):
    def __init__(self, x=0, y=0, radius=1):
        self.x=x
        self.y=y
        self.radius=radius

    def point_in(self, p):
        return ((p.x-self.x)**2 + (p.y - self.y)**2)**0.5<self.radius

Now you can use a more logical method:

>>> c1.point_in(Point(5,5))
False
>>> c1.point_in(Point(.5,.5))
True

So what about 'above' or 'below'? I suppose 'above' would mean if a point is outside the circle and Point.y > Circle.y. Add this to the Circle class:

def above(self, p):
    return ((p.x-self.x)**2 + (p.y - self.y)**2)**0.5 > self.radius and p.y>self.y 

Test it:

>>> c1.above(Point(5,5)) 
True

You can extend this concept so that you can test if a circle overlaps another circle or an area of a polygon defined by Points. You can also extend it so that each shape will use the appropriate formula for itself and the other shape. (How do you know if polygons intersect? Now we are talking more complexity! Start HERE. If you have OpenGL, you can draw the two polygons offscreen with two additive colors and test for added pixel colors...)

Then extend that to what you mean by 'above' and 'below' for triangles squares, rectangles, circles. Your basic definition of shapes other than a circle will require a rotation or just be defined as polygons by their vertices.