how to find order of rectangles sorted by the overlapping (python)

0
votes

taking as input an image, such as the example one, I want to order the colored rectangles that compose it by their overlap.

examples image

I'll explain: from the image I can get the rectangles for each point in the format (x, y)

example :

{("blue"): [(5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5), (16, 5), (17, 5), (18, 5), (19, 5), (20 , 5), (21, 5), (22, 5), (23, 5), (24, 5), (25, 5), (26, 5), (27, 5), (5, 6 ), (27, 6), (5, 7), (27, 7), (5, 8), (27, 8), (5, 9), (27, 9), (5, 10), (27, 10), (5, 11), (27, 11), (5, 12), (27, 12), (5, 13), (27, 13), (5, 14), (27 , 14), (5, 15), (27, 15), (5, 16), (27, 16), (5, 17), (27, 17), (5, 18), (27, 18 ), (5, 19), (27, 19), (5, 20), (5, 21), (27, 21), (5, 22), (27, 22), (5, 23), (27, 23), (5, 24), (5, 25), (27, 25), (5, 26), (27, 26), (5, 27), (6, 27), (7 , 27), (8, 27), (9, 27), (10, 27), (11, 27), (12, 27), (13, 27), (14, 27), (15, 27 ), (16, 27), (17, 27), (18, 27), (19, 27), (21, 27), (22, 27), (23, 27), (25, 27), (26, 27), (27, 27)]

represents a dictionary whose key is the color of the rectangle and as values ​​a list of each single pixel that forms it, through its x and y coordinates in space

I can therefore obtain for each rectangle also its spatial coordinates ((5,5), (27,27)) which represent the upper left corner and the lower right corner.

however, I can't find a way to sort the rectangles in the order they should be drawn.

example from the image: the order of the rectangles will be blue, green and yellow because I will have to draw them to regain the image in this order so as to maintain the correct sequence of intersections.

p.s I would like to make it without using libraries, like openCV ecc..

EDIT.

I take a png image as input. i create a list of list of tuple where i have every single pixel of the image represented like a RGB tuple (ex. (0, 0, 255))

i want every rectangles to be encoded as a pixel which represents the color of the rectangle. : encoded rectangles

the coded image therefore allows you to know that the blue rectangle will be drawn first, then the green one and finally the yellow one.

this is what I mean by overlapping order: if from the encoded image i draw in order the rectangles i obtain the same overlapping of the original image.

1
pythonimage-processing
I don't understand what all the numbers in your "example (not from the image): " mean and how they relate to the problem. What does the input look like? Do you have only the image to work with, or something else? - Stef
only the image. i can distinguish every rectangle: def get_pixels(img): ` coords = {} for j in range(len(img[0])): for i in range(len(img)): rgb = img[i][j] if rgb != (0, 0, 0): coords[rgb] = coords.get(rgb, []) + [(i, j)] return coords ` i have a dictionary with every rectangles color and it's coordinates(x,y). - Wilwbus
i want every rectangles to be encoded as 5 consecutive pixels horizontally : - four pixel that represent its spatial coordinates ((5,5), (27,27)) and i do it with a codification from decimal to rgb tuple - the last pixel is the color of rectangles. - Wilwbus
so i make a bitmap that have to be order in the way they have to be draw - Wilwbus
1) Locate the pixels of intersection for every pair of rectangles; 2) Figure out the colour of the intersection pixel and use that to decide which of the two rectangles is on top of the other 3) Sort the list of rectangles using the comparisons established at step 2) - Stef

1 Answers

1
votes

Though the question is pretty unclear, I seem to understand that you

  • have raw lists of colored pixels which are the result of drawing overlapping rectangles edges;

  • are able to figure out the rectangles they originate from.

If this is the case, then traverse the edges of the rectangles and every time you meet a pixel of a different color (say green instead of blue), note it as a relation "green overlaps blue"). Then apply a topological sort to the partial order so obtained.

There can be harder cases such as multiple overlaps or several rectangles of the same color.