Detect Overlapping Subrectangles

Table of Contents

Problem Description

Analysis

Used Terminology

Quantification

Completeness

All Cases

Karnaugh Map

Variable Naming

Prime Implicants

Deriving Result

Verification

Theorem

Algorithm

Formal

In Computers

Application

Article

Organization

DocumentHome » DocumentArticles » Detect Overlapping Subrectangles

Scope

If we have

  • two essentially different rectangles ("main rectangles") of arbitrary size > 0;
  • in each main rectangle an identical rectangular area of equal or smaller size ("subrectangle"), starting at an arbitrary position within the main rectangle;
  • the edges of each subrectangle (if any), which are shared at least partially with the parental main rectangle,

then it is a surprisingly inexpensive task to determine, if the two main rectangles can be joined to a polygon with a common area (the overlaid subrectangles), such eliminating the space for one of the two subrectangles.

This article

  • derives a boolean equation to find the answer to above question in just 7 boolean operations
  • presents an algorithm suitable for implementation into computer programs, at a cost of just 1 boolean operation and a comparison.

The discussion involves knowledge of Karnaugh maps (a special kind of decision tables). If you want to understand the technique and not just get the result, and if you are unfamiliar with Karnaugh maps, then it is suggested that you first follow the links given in the section External Links below.

If you just want the resulting equation, you may skip to the section results after having made sure you understand the used notation. Or maybe you want to jump directly to the algorithms section.

Author

Herbert Glarner

Published

2006-Dec-20

External Links

Problem Description

Assume you have two identical subrectangles, each within a distinct main rectangle. Identical means, that the two subrectangles have identical content and identical dimensions. The horizontal and vertical offsets may be anywhere within the corresponding main rectangles and do not need to be identical as well.

Let's visualize the problem with an example. We have a yellow rectangle with red outlines along its edges, and we have a cyan rectangle with blue outlines. They both share an identical subrectangle, shown in magenta.

Subrectangle at bottom right The subrectangle comprises its main rectangle's edges at the bottom and to the right
Subrectangle at top left The subrectangle comprises its main rectangle's edges at the top and to the left

Fig. 1: Two rectangles sharing an identical subrectangle at diagonally opposite corners

It is obvious, that the two rectangles can be overlapped to form the following polygon:

Polygon sharing the identical rectangle

Fig. 2: Polygon sharing the identical rectangle

It also should be obvious, that the following two main rectangles can not be fused into a polygon with a shared area:

Subrectangle at bottom right The subrectangle comprises its main rectangle's edges at the bottom and to the right
Subrectangle at top right The subrectangle comprises its main rectangle's at the top and to the right

Fig. 3: Two rectangles sharing an identical subrectangle at directly opposite corners

The problem is, that the yellow and cyan areas are not identical (the areas marked with the double-ended arrow), and therefore must be kept apart. (If these areas were identical, they should have been included in their magenta subrectangles.)

No possibility to merge the two rectangles into a polygon

Fig. 4: No possibility to merge the two rectangles into a polygon

"So, what's the deal? Simply fuse all those rectangles having two opposite corners, and done", you say.

Well, unfortunately things are more complicated. It turns out, that there are quite many combinations, of which some are not as obvious as the ones just shown. Quite the opposite, actually.

Let's dive into the details, after definining some terminology.

Analysis

Used Terminology

When we refer to the edges of a rectangle, we will call them Right, Bottom, Top, and Left, and abbreviate the terms with R, B, T, or L, respectively.

Naming edges

Fig. 5: Naming edges

An edge order is important. Not this particular order, but any determined order. In your particular project you might want to choose a clockwise or counterclockwise direction. In this article, however, whenever we are going to compare two rectangles, we always will use the given order RBTL for both rectangles, from left to right in exactly this way.

Ordering edges

Fig. 6: Ordering edges

Quantification

Subrectangles can appear in virtually every position within a main rectangle, including none or some or all edges of the parental main rectangle:

Subrectangle inside main rectangle No edges
Subrectangle at 1 edge of main rectangle 1 edge
Subrectangle at 2 edges of main rectangle (corner) Subrectangle at 2 edges of main rectangle (strip) 2 edges (corner, strip)
Subrectangle at 3 edges of main rectangle 3 edges
Subrectangle comprising all edges of main rectangle All edges

Fig. 7: Involved edges of main rectangle

Because there are 4 edges in a rectangle, of which each can either be included or not included in the subrectangle, we have a total of 24=16 combinations in which a subrectangle can be arranged with respect to these edges. This includes also "no edges" and "all edges".

And because we compare two rectangle/subrectangle-combinations with each other, we even will have to deal with (24)2=256 cases.

Completeness

Let's have a closer look at the mentioned 256 cases. It is obvious, that many of the rectangle/subrectangle-combinations will include rotations:

Subrectangle at 0 degrees Subrectangle at 0 degrees Subrectangle at 0 degrees Subrectangle at 0 degrees
0° 90° 180° 270°

Fig. 8: Rotated rectangles

And it requires only little imagination to realize, that any two of all main rectangle/sub rectangle-combinations have a counterpart with swapped roles:

Cyan rectangle with Yellow rectangle Comparing cyan with yellow
Yellow rectangle with Cyan rectangle Its counterpart

Fig. 9: Comparison with swapped roles

Although true reflections do not appear for a single main rectangle/sub rectangle-combination (all can be reduced to rotations), we will encounter true reflections when we compare two such combinations:

Possible overlap Possible overlap
Its reflection Its reflection

Fig. 10: Reflections when comparing two rectangle/subrectangle-combinations

"So, all in all, we should reduce our analysis to just one half, and in that half omit all reflections and rotations and just concentrate on the basic cases, no?" - Well: No. Not with the taken approach. We will in fact exhaustively look at all combinations to eventually derive our basic formula.

So let's draw the possible 2×16 inputs and the resulting 256 polygons.

An "input" is the information, which of the 16 edge combinations are involved, and since we compare two main/sub-rectangle-combinations, we have 2×16 inputs.

A "polygon" is a closed planar path composed of a finite number of sequential line segments. In our case the polygons have internal angles being a multiple of 90°, so we more precisely should call them "orthogonal polygons". (Notice, that polyominoes are a subset of orthogonal polygons, but not all orthogonal polygons are polyominoes: polyominoes are based on equilateral rectangles (squares), which is not neccessarily the case for general orthogonal polygons.) - However, for sake of brevity, we in the following shall refer to these orthogonal polygons simply as polygons.

All Cases

To represent all cases we use tables. The inputs are given as row and column headers.

In all our tables, the rows represent the input for the first main rectangle. The first main rectangle is colored in cyan, and outlined in blue. Its sub rectangle is colored blue. - Likewise do the columns represent the input for the second main rectangle, colored in yellow and outlined in red. Its sub rectangle is colored red.

Notice, that the rows and columns are labeled in the order defined above, i.e. Edge order. If an edge is not involved, i.e. if a subrectangle does not include that particular main rectangle's edge, then this is marked with a "-" at the appropriate position. - Also notice, that the sequence in which the input rows and input columns appear is not arbitrary: the reason for this order is explained in a few.

For each combination of the two input rectangles a resulting polygon is given, leaving the input colors unchanged with the exception of the subrectangular area which is shared by both input rectangles. This shared area is colored magenta.

In the table's cells, the size or shape of the input boxes may be modified to keep things somewhat space-efficient. However, keep in mind, that a magenta rectangle represents the row header's blue rectangle as well as the column header's red rectangle. Likewise do the cyan and yellow areas within a cell correspond exactly to the cyan and yellow areas of that cell's row and column headers.

But let's have a look at the table now:

---- ---L --TL --T- -BT- -BTL -B-L -B-- RB-- RB-L RBTL RBT- R-T- R-TL R--L R---
Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle Rectangle
---- Rectangle Overlapping Rectangles
---L Rectangle Overlapping Rectangles Overlapping Rectangles
--TL Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
--T- Rectangle Overlapping Rectangles Overlapping Rectangles
-BT- Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
-BTL Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
-B-L Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
-B-- Rectangle Overlapping Rectangles Overlapping Rectangles
RB-- Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
RB-L Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
RBTL Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
RBT- Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
R-T- Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
R-TL Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
R--L Rectangle Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles Overlapping Rectangles
R--- Rectangle Overlapping Rectangles Overlapping Rectangles

Fig. 11: All possible overlaps

All cells displaying no entry have two inputs which can not be merged to a single polygon with a shared area.

Karnaugh Map

Now above table is converted into an equivalent Karnaugh Map. The Karnaugh map essentially is a table exactly like the above, only that it consists completely of binary information.

In a Karnaugh map, we work with results of functions, not with graphics, and these results are expressed in binary from, i.e. each cell will have a "0" where in above table no graphic was present, or a "1" when there is a graphic, resp. However, for better legibility, we omit the zeroes within the result cells and leave them blank: this way, the human eye is better able to catch patterns. - (Those readers famliar with Karnaugh maps should notice, that a blank cell does not imply "Don't care".)

Similarly, the input must be coded such, that we can represent the different input values as a binary variable, each containing a "0" or "1". We already coded the row and column headers binary, though: a particular edge was present and marked with its initial letter, e.g.: "T" for the top edge, or it was not present and then marked with a "-". Therefore our task is reduced to replace the letters with ones and the "-" with zeroes (and this time we better do not omit the zeroes). - Each of the binary digits defines a variable, namely a particular edge within the rectangle. Hence we in total have 2×4 variables (4 edges for each of the two input rectangles): 4 variables head each row, and the other 4 each column.

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
0000 1
0001 1 1
0011 1 1 1 1
0010 1 1
0110 1 1 1 1
0111 1 1 1 1 1 1 1 1
0101 1 1 1 1
0100 1 1
1100 1 1 1 1
1101 1 1 1 1 1 1 1 1
1111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1110 1 1 1 1 1 1 1 1
1010 1 1 1 1
1011 1 1 1 1 1 1 1 1
1001 1 1 1 1
1000 1 1

It became apparent now that the rows and columns indeed are by no means ordered as a binary sequence. Instead, the ordering follows the so-called WikipediaGray code, a sequence which has the desired property, that each subsequent element changes a bit in just one single position.

Contrast this with "traditional" binary counting: a transition from decimal 7 to 8 (binary 0111 to 1000) causes 4 bits to change at once. Not so in a Gray sequence: you can easily verify in above table, that each element's successor changes in just 1 bit. This property is required in Karnaugh maps.

Variable Naming

We will need to refer to our variables in the following sections. Because it would be quite cumbersome to always refer to "the T (or the 3rd digit) of the 2nd rectangle" all the time, we are going to introduce a shorter notation.

We redefine the digits in an unambigeous way and set "A" for the leftmost digit (the "R" edge) of the first input rectangle, and subsequently "B" for its "B" edge, "C" for "T", and "D" for "L". Similarly, we rename the edges of the second input rectangle to "E", "F", "G" and "H".

Now, if we reserve 4 rows and 4 columns to represent each of the 8 variables A to H, omitting the zeroes, the pattern of the Gray code immediately will become apparent.

The header rows and header columns in which no entry appears is to be read "variable is not set", i.e. 0. When such an entry appears, e.g. "H", then this variable has an input value of 1.

In Karnaugh maps, it is common practice to display half of the row variables to the left and the other to the right of the table, and in analogy each half of the column variables above and below the table.

F F F F F F F F
H H H H H H H H
1
D 1 1
D 1 1 1 1 C
1 1 C
B 1 1 1 1 C
B D 1 1 1 1 1 1 1 1 C
B D 1 1 1 1
B 1 1
B 1 1 1 1 A
B D 1 1 1 1 1 1 1 1 A
B D 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C A
B 1 1 1 1 1 1 1 1 C A
1 1 1 1 C A
D 1 1 1 1 1 1 1 1 C A
D 1 1 1 1 A
1 1 A
G G G G G G G G
E E E E E E E E

Prime Implicants

Eventually we start to work with the Karnaugh map. Our first task is to identify the Wikipediaminterms to use in the final expression. On how to find minterms, and more about Wikipediaprime implicants, please refer to the linked Wikipedia articles.

Notice, that we use the following notation for the Boolean operations:

Symbol Operation
× AND
+ OR

(The symbol × is omitted when between terms to be ANDed, much like the conventional multiplication sign between variables; e.g. "ABCD" reads "A×B×C×D").

The following 16 prime implicants can be found:

Prime-1-block Prime Implicant Costs
1-1-1-1- ABCD 3
1-1-1--1 ABCH 3
1-1--11- ABGD 3
1-1--1-1 ABGH 3
1--11-1- AFCD 3
1--11--1 AFCH 3
1--1-11- AFGD 3
1--1-1-1 AFGH 3
-11-1-1- EBCD 3
-11-1--1 EBCH 3
-11--11- EBGD 3
-11--1-1 EBGH 3
-1-11-1- EFCD 3
-1-11--1 EFCH 3
-1-1-11- EFGD 3
-1-1-1-1 EFGH 3

"Costs" are the number of involved boolean operations. All found prime implicants require 3 AND operations. E.g. for the first prime implicant: A AND B AND C AND D.

All terms are essentials, hence our first equation reads:

X=ABCD+ABCH+ABGD+ABGH+AFCD+AFCH+AFGD+AFGH+EBCD+EBCH+EBGD+EBGH+EFCD+EFCH+EFGD+EFGH

Total costs: 16×3 ANDs + 15 ORs = 63 boolean operations.

Deriving Result

Some algebra will simplify this term. We don't even need to apply any "specials" of Boolean algebra.

This is the found equation which we want to simplify:

X=ABCD+ABCH+ABGD+ABGH+AFCD+AFCH+AFGD+AFGH+EBCD+EBCH+EBGD+EBGH+EFCD+EFCH+EFGD+EFGH

Factoring out the first two products of each term in above equation:

X=AB(CD+CH+GD+GH)+AF(CD+CH+GD+GH)+EB(CD+CH+GD+GH)+EF(CD+CH+GD+GH)

The terms in the 4 parantheses are identical, hence we have a binomial:

X=(AB+AF+EB+EF)(CD+CH+GD+GH)

Within the 2 parantheses we factor out their first factors:

X=( A(B+F)+E(B+F) )( C(D+H)+G(D+H) )

The inner two parantheses within each outer parathesis are identical, forming binomials once again:

X=( (A+E)(B+F) )( (C+G)(D+H) )

The outer parantheses can be removed, and the final equation reads:

X=(A+E)(B+F)(C+G)(D+H)

Total costs: 4 ORs and 3 ANDs

Verification

Let's see if our equation holds. A worksheet table is quickly set up to generate a truth table for the 256 possible values. For easy access to the variables from the table body's cells, A to D are written into separate columns, and E to H into separate rows.

E.g. for MS Excel: Assuming that your table starts in cell A1, the table's body starts in F7. Enter this formula into cell F7:

=IF(AND(OR($B7;F$2);OR($C7;F$3);OR($D7;F$4);OR($E7;F$5));"T";"F")

then copy it to all 256 cells of the cell body.

These are the values you get. (The "T" results were bolded manually for easier comparison.)

Cell A1 EFGH 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
E 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
F 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
G 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
H 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
ABCD A B C D
0000 0 0 0 0 F F F F F F F F F F T F F F F F
0000 0 0 0 1 F F F F F F F F F F T T F F F F
0000 0 0 1 1 F F F F F F F F T T T T F F F F
0000 0 0 1 0 F F F F F F F F F T T F F F F F
0000 0 1 1 0 F F F F F F F F F T T F F T T F
0000 0 1 1 1 F F F F F F F F T T T T T T T T
0000 0 1 0 1 F F F F F F F F F F T T T T F F
0000 0 1 0 0 F F F F F F F F F F T F F T F F
0001 1 1 0 0 F F T F F T F F F F T F F T F F
0001 1 1 0 1 F F T T T T F F F F T T T T F F
0001 1 1 1 1 T T T T T T T T T T T T T T T T
0001 1 1 1 0 F T T F F T T F F T T F F T T F
0001 1 0 1 0 F F F F F T T F F T T F F F F F
0001 1 0 1 1 F F F F T T T T T T T T F F F F
0001 1 0 0 1 F F F F T T F F F F T T F F F F
0001 1 0 0 0 F F F F F T F F F F T F F F F F

A comparison with the first Karnaugh map shows, that the equation holds.

Theorem

It has been shown for all 256 possible cases, that the formula holds. However, as per the date writing this article (Dec 20, 2006) I was not able to find an according theorem on the Internet. If the theorem given here has an accepted name already, I would be grateful for a comment or an e-mail in order to mention it. The same is true when you happen to come across a mathematical proof.

Theorem: When two otherwise distinct rectangles A and B have an identical subrectangle C1 and C2 at an arbitrary position within their parental rectangles A and B, then the rectangles A and B can be partially overlaid to form a single polygon sharing the common subrectangle C1=C2 then and only then, when the area of any subrectangle C1 or C2 (or both) includes a length larger than 0 for all four edges of either rectangle A or B or both.

Algorithm

Formal

The algorithm may formally be expressed like this:

  • Set R:=1 (R will hold the final result)
  • For all 4 edges:
    • Set X:=0 if the subrectangle of the first main rectangle does not include that particular edge of its main rectangle, X:=1 otherwise
    • Set Y:=0 if the subrectangle of the second main rectangle does not include that particular edge of its main rectangle, Y:=1 otherwise
    • Perform the boolean operation Z:=X OR Y
    • Perform the boolean operation R:=R AND Z
    • If R became 0, then the algorithm terminates and no overlapping polygon is possible
    • If R still is 1, repeat for the next edge. If there is no more next edge, the algorithm terminates and creation of a polygon with a shared area is possible

In Computers

Note, however, that on a computer the loop of the formal algorithm is not needed, because we can make use of bit parallelism.

Assume, that we have the values of 4 edges of the first rectangle ABCD in a variable X, coded in 4 bits; and similarly those of the second rectangle EFGH in a variable Y. The order of the edges does not matter, as long as both variables use the same order and the 4 bits are in the same position.

Variable Content
X ABCD
Y EFGH

Then X OR Y will perform all 4 Boolean OR operations in one go. Let's store the result in variable Z and name the 4 resulting bits IJKL.

Parallel Boolean operation Content after operation
Z := X OR Y IJKL

Now it is only left to find out, if any of the bits in IJKL is 0. If so, no overlapping area exists for the two inputs. If all 4 bits are set to 1, though, then such an overlapping area exists.

And because the 4 bits form an unambigeous value when all set, this can be found out with just one comparison. E.g., assume that the 4 bits all are in the least significant bits of a word (bit values from LSB to MSB: 1+2+4+8). Then:

    IF Z = 15 THEN 
        Overlapping
    ELSE 
        Not Overlapping
    FI

Application

Of course, this algorithm does not tell you yet, how to merge the original rectangles into a polygon combining the common area. But it tells you, if it is possible at all, and this it does at surprisingly low costs.

Source: http://www.gandraxa.com/detect_overlapping_subrectangles.aspx

Site Menu

Home

Articles – some samples:

Digital Terrain Analysis: Obtain and render digital elevation models, and learn the basic formulas for isometric projections

Length of Day and Twilight: Deriving formulae, including tables and graphs

Recreation

TEAK: take the Test of Encyclopedic and Analytic Knowledge and compare your score with that of your friends