Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two rectangles can overlap in lots of different ways. One can be entirely inside the other (2 variations depending on which is inside which). They can overlap at a single corner (4 variations there depending on which corner pair is involved), they can overlap with one rectangle passing through one side but not the other (8 variations, 1 for each side of each rectangle), etc.

Take the following two rectangles:

+--------+
|        |
|  +--+  |
|  |  |  |
+--|--|--+
   |  |
   +--+

They would become the following 5 rectangles:

+--------+
|        |
+--+--+--+
|  |  |  |
+--+--+--+
   |  |
   +--+

Or possibly just the following 2 rectangles:

+--------+
|        |
|        |
|        |
+--+--+--+
   |  |
   +--+

I want to write code which would take two arbitrary rectangles (each one has x,y coordinates of one corner plus a width and height) and chop them up so that we end up with a set of non-overlapping rectangles.

The problem is that there are SO MANY possible variations! Would it really be necessary to write code with 20 or more special cases where I first check if the upper left corner overlaps the other rectangle and then check the upper right corner, etc., and eventually check if two corners overlap and so on and so on?

Can anyone think of a simpler way to do this other than to enumerate all possible overlaps and then laboriously check every point and combinations of points to see how they overlap?

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

This problem is well-studied in computer graphics, because, at its core, it is a special case of clipping. Two traditional solutions are the Weiler–Atherton clipping algorithm, and the Sutherland–Hodgman clipping algorithm. Both are more general than you need. But using the search term "rectangle clipping" will lead you to specific code, e.g., this C++ code. Finally, this question might be better asked at StackExchange. For example: "How to subtract a rectangle from another?."

share|improve this answer
1  
This doesn't get me all the way there, but I was able to implement the Sutherland–Hodgman clipping algorithm (that page provides great pseudocode). Now, given two rectangles I can get a set of points describing the areas of overlap. I still need to subtract that area from one rectangle and split up the resulting polygon to get a new set of rectangles, but that seems like an easier problem. –  HappyEngineer Aug 27 '11 at 17:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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