0
$\begingroup$

This problem takes place on a coordinate plane. I need assistance in creating the algorithm to solve this problem. I am solving this problem in java if you are interested.
I have 1 carpet and 2 tarps.
The 1 tarp covers the carpet (note in some scenarios it may not cover it at all).
The second tarp will cover the remaining area of the carpet, however, this is where it gets tricky. The tarp cannot be a special shape or tilted, meaning the tarp HAS to be rectangular. I am given the inputs of the lower left and top right corners of both the 1st tarp and the carpet. As of now, I have calculated the visible area of the carpet after the first tarp has been placed, the overlapping (non-visible) area of the tarp, and the areas of both the carpet and 1st tarp.
So basically what I am saying is, given a rectangle C (the carpet) that intersects the rectangle T1 (tarp 1), find another rectangle T2T2 (tarp 2) such that the area of T2T2 is minimal. Below is a picture of some test cases I drew up:

test case *Excuse my messy handwriting

Cutting to the chase, what I need is help with is developing an algorithm that would satisfy all of the above test cases, given the lower left and top right coordinates of both the first tarp and carpet. Note I am going to be writing this in Java and I currently have an area function and visible area of the carpet function.

Sorry if I was a little unclear on what I am asking, leave a comment and I'll be happy to clarify. Note: this is not a homework problem, as many of you may think. This is merely an interesting scenario of another programming problem I had.

$\endgroup$
  • $\begingroup$ If I understand it correctly, your problem boils down to: given a rectangle $C$ (the carpet) that intersects the rectangle $T_1$ (tarp 1), find another rectangle $T_2$ (tarp 2) such that the area of $T_2$ is minimal. Is this correct? If so, you may add something similar to this formulation to make your question more clear. $\endgroup$ – Discrete lizard Jan 21 '18 at 18:07
  • $\begingroup$ @Discretelizard Yep that is correct. Could you help out here? $\endgroup$ – joshkmartinez Jan 21 '18 at 18:33
0
$\begingroup$

To solve this, consider what happens when exactly $k$ corners of $C$ lie inside $T_1$, for $k\in \{0,1,2,3,4\}$, where $C\setminus T_1$ denotes the area of $C$ not covered by $T_1$:

  • If $0$ corners of $C$ lie in $T_1$, then $T_1$ doesn't cover any corner of $C$. So any rectangle covering $C\setminus T_1$ must cover all corners of $C$, so the smallest of these rectangles is $C$ itself.
  • If exactly $1$ corner of $C$ lies in $T_1$, the $C\setminus T_1$ contains $3$ corners of $C$ and the smallest rectangle covering this area is again $C$ itself.
  • If exactly $2$ corners of $C$ lie in $T_1$, then $C\setminus T_1$ is a rectangle, so the smallest rectangle covering it is itself. More precisely, this is the rectangle with as corners the two intersection points of the edges of $C$ and $T_1$ and the two corners of $C$ not covered by $T_1$.
  • If $3$ corners of $C$ lie in $T_1$, then $4$ corners of $C$ lie in $T_1$, so $k$ cannot be $3$.
  • If $4$ corners of $C$ lie inside $T_1$, then $C$ is fully covered by $T_1$, so the smallest rectangle covering the remainder has area $0$.

So, to determine the size of the smallest rectangle covering $C\setminus T_1$, we simply count the number of corners of $C$ inside $T_1$, apply the proper case and we're done.

$\endgroup$

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.