## Rectangles overlapping

### Rectangles overlapping

We're working on an app that has to be able to determine whether one
rectangular region overlaps another.  The requirement is complicated by the
fact that either rectangle can be in a rotated state, so the sides are no
longer pure vertical or horizontal lines.

The algorithm we are currently using compares all 4 sides of one rectangle
against the sides of the other, testing for intersections.  This algorithm is
too calculation-intensive.  Is there a more elegant (and hopefully efficient)
solution?

if you think others may be interested).

PeteJ

### Rectangles overlapping

>We're working on an app that has to be able to determine whether one
>rectangular region overlaps another.  The requirement is complicated by the
>fact that either rectangle can be in a rotated state, so the sides are no
>longer pure vertical or horizontal lines.

>The algorithm we are currently using compares all 4 sides of one rectangle
>against the sides of the other, testing for intersections.  This algorithm is
>too calculation-intensive.  Is there a more elegant (and hopefully efficient)
>solution?

Why not rotate one of the rectangles into orthogonal coordinates and
(rotate the other with the same rotation) and do a simple containment
test on the second's points.

Jim.

### Rectangles overlapping

>We're working on an app that has to be able to determine whether one
>rectangular region overlaps another.  The requirement is complicated by the
>fact that either rectangle can be in a rotated state, so the sides are no
>longer pure vertical or horizontal lines.

You might want to look at http://www.cs.unc.edu/~geom/OBB/OBBT.html,
which has a paper (that was in Siggraph96) on "Oriented Bounding Box"
tests.  I haven't read it yet, but it sounds like exactly what you want.

Chris

### Rectangles overlapping

If you are using Windows and aren't terribly concerned about performance,
you can create polygonal regions and then check for intersection using
CombineRgn().

Kaushik

> >We're working on an app that has to be able to determine whether one
> >rectangular region overlaps another.  The requirement is complicated by
the
> >fact that either rectangle can be in a rotated state, so the sides are
no
> >longer pure vertical or horizontal lines.

> You might want to look at http://www.cs.unc.edu/~geom/OBB/OBBT.html,
> which has a paper (that was in Siggraph96) on "Oriented Bounding Box"
> tests.  I haven't read it yet, but it sounds like exactly what you want.

> Chris

### Rectangles overlapping

>We're working on an app that has to be able to determine whether one
>rectangular region overlaps another.  The requirement is complicated by the
>fact that either rectangle can be in a rotated state, so the sides are no
>longer pure vertical or horizontal lines.

>The algorithm we are currently using compares all 4 sides of one rectangle
>against the sides of the other, testing for intersections.  This algorithm is
>too calculation-intensive.  Is there a more elegant (and hopefully efficient)
>solution?

>if you think others may be interested).

>                                                    PeteJ

There exists a more elegant algorithm that uses the principle of a
SWEEP LINE. I know only of the algorithm that finds intersections of a
set of arbitrarily orientated line segments, but perhaps it is similar
to the rectangle-problem. Though I can't explain it to you in detail
nor give you a reference to where I found it I'll try to give you an
idea on how it works:

First this algorithm is only of the order of O(n*log(n)+k) where n is
the numer of rectangles and k is the number of intersections. As I see
at the moment, your algorithm is of the order O(n**2) as it compares
each rectangle with each other.

For the alg:
Imagine a vertical line (sweep line) that scans from the very left to
the very right of your segments. The only point where sth. 'happens'
are the start/endpoints of the segments. So you maintain a sorted list
of these points (event-list) and process each of these points
sequentially. For the sweep line you maintain also a list of segments
that actually intersect this line (sorted by y-coordinates). These
segments are easily found as you know that at each start point a
segment enters the list and at each end point it leaves the list (so
there's no searching). Segments can only intersect when the are
neighbours in the sweep line. So you calculate the intersections of
an intersection point in your event-list the corresponding
line-segments will change order in your sweep-line structure.

Perhaps you can use this idea to implement your
rectangle-intersection-algorithm.

Good luck and let me know how you did it,
Carsten

------------------------------------------------------------------------
Carsten Leue               phone:                (++49) 6221 54-5477
Institute for              fax:                  (++49) 6221 54-6405

University of Heidelberg
INF 366
69126 Heidelberg
Germany
------------------------------------------------------------------------

### Rectangles overlapping

: We're working on an app that has to be able to determine whether one
: rectangular region overlaps another.  The requirement is complicated by the
: fact that either rectangle can be in a rotated state, so the sides are no
: longer pure vertical or horizontal lines.

: The algorithm we are currently using compares all 4 sides of one rectangle
: against the sides of the other, testing for intersections.  This algorithm is
: too calculation-intensive.  Is there a more elegant (and hopefully efficient)
: solution?

: if you think others may be interested).

You don't say how likely the rectangles are to overlap.
I would first compare using the smallest enclosing circle.
1.  Calculate the length of the diagonal.
2.  Calcualte the center of the box.
3.  Calcuatate the distance between the centers of the two boxes.
If this distance is greater than the sum of the two boxes diagonals,
then they can't overlap. (Note: instead of calculating lengths,
calculate length squared -- squareroot is an expensive operation, so
when possible compare the squares.

Ok, if this test fails -- e.g. they are close enough that they may
overlap:

Another quick test is to compare their orthog*bounding boxes --
the box in screen corrdinates that surrounds the rotated box.  If these
two boxes don't overlap, then the smaller ones inside can't.

While this doesn't solve your original problem, if the rectagles are
small compared to the screen, you may not have to solve a zillion
intersection problems.

(I vaguely recall a cartesian geometry proof of a theorem that allows
you to show whether a given point is inside some convex polygon, just
given the coordinates of the polygon.  But that book isn't handy.  It
basically amounts to a proof using areas of the triangles formed by the
one point and each side. If the point is inside the polygon then the sum
of the areas formed by it and each side is the area of the polygon.  If
the point is outside, then the total is larger.)

--

Sherwood Botsford |Unsolicited email that advertises commercial
Physics Dept      |activities will consitute a request for
U of Alberta      |spellchecking of all words of less than three
Edmonton, AB,     |characters.  I charge \$US500 for this service.
T6G 2J1           |There is no warranty of correctness of this service.

### Rectangles overlapping

> >We're working on an app that has to be able to determine whether one
> >rectangular region overlaps another.  The requirement is complicated by the
> >fact that either rectangle can be in a rotated state, so the sides are no
> >longer pure vertical or horizontal lines.

> There exists a more elegant algorithm that uses the principle of a
> SWEEP LINE.

This algorithm is solving a different problem: given a bunch of
rectangles, determine which pairs intersect.  "Singularity"'s problem
involves only two rectangles.

Quote:> First this algorithm is only of the order of O(n*log(n)+k) where n is
> the numer of rectangles and k is the number of intersections.

This is quite ambitious.  An algorithm of Bentley and Ottman runs in
time O((n+k)log n) and is much easier to understand and impliment.  The
O(log n) term comes from using a priority queue to store the order in
which the sweep line intersects the segments.  In some applications,
this can be eliminated (or at least reduced) by using bucketing instead
of a binary tree structure.

For more details on sweep-line algorithms, see Joe O'rourke's textbook
"Computational Geometry in C" (Cambridge, 1994).  Here are a few more
technical references.

, author =      "Ivan J. Balaban"
, title =       "An Optimal Algorithm for Finding Segment Intersections"
, booktitle =   "Proc. 11th Annu. ACM Sympos. Comput. Geom."
, year =        1995
, pages =       "211--219"
, keywords =    ""
, update =      "95.09 mitchell"

}

, author =      "J. L. Bentley and T. A. Ottmann"
, title =       "Algorithms for reporting and counting geometric
intersections"
, journal =     "IEEE Trans. Comput."
, volume =      "C-28"
, year =        1979
, pages =       "643--647"
, precedes =    "b-carcg-81"

}

, author =      "K. Q. Brown"
, title =       "Comments on ``{Algorithms} for reporting and counting
geometric intersections''"
, journal =     "IEEE Trans. Comput."
, volume =      "C-30"
, year =        1981
, pages =       "147--148"
, succeeds =    "bo-arcgi-79"

}

, author =      "B. Chazelle and H. Edelsbrunner"
, title =       "An optimal algorithm for intersecting line segments in
the plane"
, journal =     "J. ACM"
, volume =      39
, year =        1992
, pages =       "1--54"
, keywords =    "intersection, topological sweep, segments"
, succeeds =    "ce-oails-88"

}

, author =      "M. Edahiro and K. Tanaka and R. Hoshino and Ta. Asano"
, title =       "A bucketing algorithm for the orthogonal segment
intersection
search problem and its practical efficiency"
, journal =     "Algorithmica"
, volume =      4
, year =        1989
, pages =       "61--76"
, succeeds =    "etha-baosi-87"

}

, author =      "R. Kalin and N. Ramsey"
, title =       "A new analysis and comparison of algorithms for the
planar
segment intersection problem"
, type =        "Report"
, number =      "??"
, institution = "Dept. Elect. Engrg. Comput. Sci., Princeton Univ."
, year =        1984

Quote:}

--
Jeff Erickson

http://www.cs.duke.edu/~jeffe

If the sides are parallel to the axes, it's easy:  If the high X of one is less
then the low X of the other, or the high Y of one is less than the low Y of the
other, they DON'T overlap.  Otherwise, they do.  This can be determined in 4
comparisons:

if ((hi_x1 < lo_x2) || (hi_x2 < lo_x1) ||
(hi_y1 < lo_y2) || (hi_y2 < lo_y1))
{
They don't overlap
}
else
{
They do
}

If the sides are not parallel to the principal axes, but they have the same
orientation (ie, the sides are parallel to each other), then it might be easiest
to just transform the coordinates so they are parallel to the X and Y axes.