: 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.