We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates.

We want a list of the minimum number of lines defined by a pair of points (x,y) that cut up the big rectangle into the small ones.

For example for this case:

enter image description here

The minimum number of cuts would be 7, and they are represented in the following picture.

enter image description here

Any idea to achieve this? (The rectangles are not always touching the borders.)

  • $\begingroup$ your first cut will probably be from one edge to the opposing edge, now you have 2 rectangles that may or may not be subdivided $\endgroup$ – ratchet freak Sep 21 '17 at 15:28
  • 1
    $\begingroup$ Do the rectangles always touch the border as in your pictures? $\endgroup$ – adrianN Sep 21 '17 at 15:40
  • $\begingroup$ No, they are not always touching the borders $\endgroup$ – E. Williams Sep 21 '17 at 15:41

Each edge of an inner rectangle that (that isn't on the exterior of the big rectangle) is a line segment. Your problem now becomes: given a collection of line segments, find the minimum number of lines to cover all of the line segments (and nothing more).

This problem can be solved as follows. For each line segment, extend the line as far as you can in both directions, until it no longer is touching any line segment. Add that line to your collection of lines. Repeat until you've covered all of the line segments. In other words, merge two line segments if they are touching and go in the same direction (since in that case they can be merged into a single line that covers both). Repeat until you can't merge anything any longer.

| cite | improve this answer | |
  • $\begingroup$ Thanks, it sounds good. What do you mean by "extend the line as far as you can, until it no longer is touching any line segment"? Do I have to consider any condition to extend it? $\endgroup$ – E. Williams Sep 21 '17 at 16:58
  • $\begingroup$ @E.Williams, I edited my question to add two sentences to the end to explain it differently. Does that help? $\endgroup$ – D.W. Sep 21 '17 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.