## Overlapping rectangles: how to determine?

### Overlapping rectangles: how to determine?

I'm in the process of integrating an OCR engine into our product line,
and one of the peculiarities it has is that if you specify two text
regions on a page, where one overlaps the other, then the one "on top"
will get the text from that area, but the one "under" it will not.  If
this weren't an ASCII posting, a diagram would make it much easier to
describe, but alas.....

In my code, I need to know if any rectangular region in my list
overlaps with any other region.  Does anyone have a suggestion about
how to determine this, other than a brute-force point-in-a-polygon
test, for each vertex against each rectangle, which requires 4 *
((n^2)/2) tests?  Yuk.

Thanks for any hints.

Dave
--
Dave Bushong, Wang Laboratories, Inc.

### Overlapping rectangles: how to determine?

>In my code, I need to know if any rectangular region in my list
>overlaps with any other region.  Does anyone have a suggestion about
>how to determine this, other than a brute-force point-in-a-polygon
>test, for each vertex against each rectangle, which requires 4 *
>((n^2)/2) tests?  Yuk.

Try a sweeping-line algorithm, which is described in
computational-geometry texts such as Preparata and Shamos.  The basic
idea is as follows:
1. Sort the rectangles by their x-min values (x-coord of left side).
2. Move an imaginary vertical line from left to right, keeping track
of which rectangles it is intersecting.  This involves:
a - using a tree to keep the current set of rectangles.
It should order the rectangles by y coordinate.
b - adding rectangles when the sweep line first hits them,
and removing them when it leaves them behind.
c - when a rectangle is added, test it for intersection with
rectangles in the current set that have a y-range that
overlaps the new rectangle's y-range.

You could probably replace the tree with a simple list, and still get
something like n^1.5 performance.  The tree gives you nlogn
performance, I'm sure.

### Overlapping rectangles: how to determine?

> In my code, I need to know if any rectangular region in my list
> overlaps with any other region.  Does anyone have a suggestion about
> how to determine this, other than a brute-force point-in-a-polygon
> test, for each vertex against each rectangle, which requires 4 *
> ((n^2)/2) tests?  Yuk.

First, you don't need a general point-in-polygon test, since I assume the
rectangles in question have horizontal and vertical edges. All you need to do
is compare the intervals generated by the left/right and top/bottom
coordinates of the rectangles for intersection.

Second, I can't imagine you'd have so many rectangles on a page that even an
O(n^2) algorithm would prove time-consuming. Each rectangle is a block of
text, right, not an individual character? So a really complex page like a
newspaper might have twenty or thirty of these. No biggie; I'll bet the whole
set of comparisons would take about a millisecond or less on any modern-day
computer.

--Jens Alfke

.apple.com              Rebel girl you are the queen of my world

I need an algorithm to determine to best contact plane for two partially
overlapping convex polyhedra.

I am writing a 3D rigid body physics simulator. I am using Gilbert's
algorithm (enhanced GJK) for collision detection. From what I can tell, when
GJK detects a collision, it does not tell the normal direction of the
contact surface. GJK only tells me the location of contact.

When the two polyhedra intersect at more than one point, the problem is
worse. GJK only tells me an arbitrary point in the intersection volume.

What algorithm do I use to determine the contact plane?

One option is to search the geometry of the two polyhedra near the
intersection location and try to find the nearest face (or two edges). I
think this would be ad-hoc and would require a lot of coding.

Some people have proposed to just use the separation vector returned by GJK
at the last time the two objects were NOT touching as the contact plane
normal direction. This produces bizarre results in cases of prolonged
contact when both objects are rotating. For example when one domino leans on
another one and tips it over, the contact plane stays vertical instead of
rotating with the objects.