20
3
In this challenge, you are given two overlapping rectangles, and you need to calculate the rectangles created by removing one from the other.
For example, if you remove the red rectangle from the black one:
You end up with one of the following two rectangle sets:
You'll also need to handle the following:
To be more explicit:
- You will input the coordinates of two rectangles, A and B.
- You need to output the fewest non-overlapping rectangles that cover all of the area of A without B. Any possible covering is allowed
- Rectangular coordinates are passed as 4 integers. You can pass them in two pairs (representing the two corner points), or as a tuple/list of 4 integers. Your inputs and outputs need to be consistent.
- A and B will not necessarily overlap or touch, and each will have an area of at least 1
Test cases:
[(0 0) (5 5)] [(3 4) (8 7)] -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)] -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)] #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)] -> #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)] -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)] #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)] -> [(1 5) (7 8)] #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)] -> [(4 1) (10 5)] [(4 7) (10 9)] #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)] -> [(1 1) (8 6)] #Only possible output
This is a code-golf, so make your code as short as possible!
3Related. – Martin Ender – 2017-07-05T15:46:11.263
1can we assume that the given input
{(x1, y1), (x2, y2)}
holdsx1 < x2
andy1 < y2
? – tsh – 2017-07-06T03:01:57.683Yep. The rectangle will have an area of 1, and you can order the coordinates in any order you like. – Nathan Merrill – 2017-07-06T03:57:22.813
Is edge thick? When rectangle defined is edge included? – Евгений Новиков – 2017-07-06T04:05:54.690
The edge has 0 thickness. – Nathan Merrill – 2017-07-06T04:06:55.790
Seems, that only one edge is included. Rectangle formula is
(x1 <= x < x2) && (y1 <= y < y2)
? – Евгений Новиков – 2017-07-06T04:23:49.043Another words, seems that
[(0 0) (2 2)]
is2x2
rectangle, but not3x3
– Евгений Новиков – 2017-07-06T04:25:44.073The way I like to think of it is that the rectangle consists of lines of width 0 that go from (x1, y1) to (x2, y1) to (x2, y2) to (x1, y2). Whether or not the rectangle "includes" the point (x1, y1) is largely irrelevant. – Nathan Merrill – 2017-07-06T04:31:27.493
Let us continue this discussion in chat.
– Евгений Новиков – 2017-07-06T04:32:54.480