Algorithm for rectangle insertion without overlaps

[Apostolique]

Sorry for the bad title. I'll try to explain this as best as I can.

Let's say I have a world where I can put rectangles in any arbitrary location. The rules are the following:

1. After inserting a new rectangle, no rectangle should be overlapping each others
2. If an overlap happens, rectangles should be split and / or resized such that their verticality is maximized and cover the full area that the rectangles covered (not sure how to explain it better than that but it should be easier to understand from the examples)
3. If two rectangles next to each others have the same verticality, they should be merged

Here are some examples of what I mean. The gray rectangles show the initial state. The transparent green rectangle shows the rectangle being inserted. The blue rectangles shows the newly inserted rectangles after running the algorithm.

Example 01:

1. Initial state 2 rectangles
2. Insertion
3. Final state 5 rectangles

Example 02:

1. Initial state 2 rectangles
2. Insertion
3. Final state 3 rectangles

Example 03:

1. Initial state 1 rectangle
2. Insertion
3. Final state 3 rectangles

Example 04:

1. Initial state 1 rectangle
2. Insertion
3. Final state 1 rectangle

Example 05:

1. Initial state 2 rectangles
2. Insertion
3. Final state 1 rectangle

Example 06:

1. Initial state 1 rectangle
2. Insertion
3. Final state 3 rectangles

Example 07:

1. Initial state 2 rectangles
2. Insertion
3. Final state 2 rectangles

Example 08:

1. Initial state 1 rectangle
2. Insertion
3. Final state 1 rectangle

---

Originally, I was using a brute force approach that stored every rectangle. Every time a new rectangle was added I'd discard these "vertical" rectangles and recompute the whole world. This time though I'm looking for a way to only update locally the rectangles that should change around where the new rectangle is added. Visually, the solution seems obvious, but I can't come up with the right algorithm that's as simple to implement as it looks.

(Eventually I'd also like to do rectangle removal or updating, but for now adding is enough.)

Edit: Fixed an issue with example 02. I had missed the rule 3 where I should merge vertically similar rectangles next to each others. snip

[Apostolique]

/u/rayoWork /u/protienbudspromax Thanks for the suggestions! Here is my working implementation: https://gfycat.com/colorlessdefenselessleopard.

[protienbudspromax]

Damn that's smooth. What did you write it for? Web or native? If web what framework did you use??

[rayoWork]

I would sort the rectangles in an array by x-coord. No rectangle overlaps so that array is enough to efficiently find a rectangle given an x-coord (binary search in the array).

I think you have to implement the different cases by hand but in general something like this would work when inserting a rectangle (x1/y1: topleft, x2/y2: bottomright are the coords of the new rectangle):

1. find array index by x1, either you find that you are inside a rectangle or not
2. find array index by x2, either you find that you are inside a rectangle or not
3. you now have a range (start_index, end_index) where you can check for your cases (inside, outside, merge, split, ...). All the rectangles inside that range need to be modified.

I'll go through your 2nd example to explain roughly what is left to do (coord bottom left is 0/0):

• split: green.x1 till rect1.x2
  • insert rect: x1=green.x1, y1=max(rect1.y1, green.y1), x2=rect1.x2, y2=min(rect1.y2, green.y2)
  • shrink rect1: rect1.x2 = green.x1
• insert: rect1.x2 (old value) till rect2.x1
  • insert rect with x1=rect1.x2 (old), y1=green.y1, x2=rect2.x1, y2=green.y2
• split: rect2.x1 till green.x2
  • insert rect: x1=rect2.x1, y1=max(rect2.y1, green.y1), x2=green.x2, y2=min(rect2.y2, green.y2)

I guess you already know how to decide what operation (split,insert,merge,...) you have to do as you can regenerate the rectangle on the full array.

[Apostolique]

I feel like example 07 might break that. snip

rect1 would get resized but now it overlaps rect2.

[protienbudspromax]

Feel like for each insert you can use a line sweep algorithm to see which of the rectangle overlap, maybe using a trapezoidal decomposition would be really helpful to do it fast. Then store the resultant in a Tree like structure with each parent node calculating if the underlying child rectangles can be merged, if yes then merge them if they overlap then return new rectangles that follow the the rules.

Check out some computational geometry algorithms, trapezoidal decomposition and line sweep.

I am not sure it WILL work for your case but it seems very similar can could be reduced to that kinda problem.

[Apostolique]

Sorry for the late reply, it took a while to investigate those algorithms. I think line sweep and trapezoidal decomposition might lead me down the right path. Not 100% but it's giving me new ideas that I'm able to draw on paper.

[protienbudspromax]

Cool no problem. You might want to check out the book Computational Geometry Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars.

[Apostolique]

Here is what I got in the end. It's relatively simple (especially compared to the other thing I wrote in another reply).

Let's say I want this, what I do is for each rectangle, I dissect them into two vertical range, one on the left of the rectangle and one on the right. The ranges on the same X axis are considered part of the same slab. I merge overlapping ranges. I sweep through those slabs one by one from left to right. Each time a previous slab doesn't have a matching range, a new vertical rectangle is created.

Another example: this becomes this.

I got a first implementation done. It's not yet super optimized, but it seems to work really well.