Combining Rects into a Shape2d

Using Cinder
1

Hi,

I have a group of ci::Rectf’s that i would like to combine into a Shape2d if they are touching.(or Path2D, but i think a Path2D cannot be drawSolid/filled in ). I would also like to check if a ci::Rectf is not touching any other ci::Recf and give it its own shape.

Can Cinder already do this automatically?

My first solution would be iterative, brute force and O(n2). Improvements/critique welcome!
Some pseudo-code.

1 - pick the first rect from array of rects.
2 - call it Rect1
3 - remove Rect1 from the array of rects
4 - convert into a Shape
5 - call it Shape1
6 - loop through the array of rects
7 - test if Shape1 is touching each rect
8 - If touching a rect, say Rect2
9 - combine Shape1 and Rect2
10 - remove Rect2 from array of rects
11 - when finished loop store Shape1 in an array
12 - repeat steps 1 - 11 until array of rects empty

2

I don’t know if Cinder provides this functionality out of the box (would be surprised if it does - this seems like a very specific feature). You could improve your algorithm and bring it closer to linear complexity by not checking the shape against every rect, just the next one:

  1. Create a list of shapes that will be the output
  2. Convert the first rect into a shape and add it to the output list
  3. Check each remaining rect against each shape in the output list until you find one that it intersects. If you find an intersection merge the rect with that shape. If not convert the rect to a shape and add it to the output list.
3

If you want a quick and dirty implementation you can use the PolyLine2f and its calcUnion and calcIntersection methods. One upside is it would support holes in Rects. Downside is it’s probably slower than what you could hand tune.

1 Like
4

@Ghirigoro Thanks, that would speed things up. I remove rects i have merged from the array but your way would avoid the cost of removing.

@drewish thats great, i will check it out. I will be doing this task once in the setup function and then using the results else where in my app so being slow might not matter too much. Accurate is more important.

5

How much does the input data change (i.e. is the data likely to be different every time you run the program)? If the input doesn’t change much it might be more efficient (both in terms of the computer’s time and yours), to do a quick and dirty implementation and serialize the results.

6

@Ghirigoro thats a good idea, the input data is actually read from file so yeah serialising the results would make sense.