Overlapping rectangles: how to determine?

Overlapping rectangles: how to determine?

Post by Dave Busho » Wed, 25 May 1994 04:12:31



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?

Post by Alejo Hausn » Fri, 27 May 1994 06:46:38



>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?

Post by Jens Alfk » Sun, 29 May 1994 05:48:39



> 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

 
 
 

1. How to determine the contact plane for overlapping convex polyhedra

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.

Is it possible to get more information from the simplex?

When GJK is finished, it has a simplex (1 to 4 points) in the Minkowski-sum
space (vectors formed by the difference of vertices on each polyhedron). The
simplex contains the origin in its interior.

If the simplex is only 1 or 2 points, I think it doesn't tell us much.
However, if the simplex has 3 or 4 points, we can take the vector from the
origin to the nearest point on the hull of the simplex (perpendicular to the
hull). Doesn't it seem like that would it be a good candidate for the
contact normal direction? It works in all the cases I have thought of.

Any help is greatly appreciated.


2. Animation GIF

3. How can I determine if two triangles are overlapping

4. Going from .FLI files to .GIF files.

5. How do I determine if 2d polygons overlap?

6. vertex structure

7. Determining when to images touch/overlap

8. Damos a conocer la Cultura Latina en Internet

9. Overlapping rectangles -- HELP

10. Checking rectangle overlap in a plane

11. Overlap of Rectangles

12. Checking rectangle overlap in a plane

13. Moving rectangles to avoid overlapping