What is a simple algorithm for creating non-overlapping rectangles?

What is a simple algorithm for creating non-overlapping rectangles?

Post by C.P. Chandrasek » Fri, 06 Aug 1999 04:00:00



Hello,

Given a set of non-overlaping Rectangles positioned in a graph
(the co-ordinate system offered in most comptuers
where 0,0 is the top left hand corner of the monitor).  
What could be the simplest algo to find out if an added new
rectangle overlaps any of the existing rectangles...?

Thanks for any help.
Regards
CP Chandrasekar

 
 
 

What is a simple algorithm for creating non-overlapping rectangles?

Post by MS » Sat, 07 Aug 1999 04:00:00



> Given a set of non-overlaping Rectangles positioned in a graph
> (the co-ordinate system offered in most comptuers
> where 0,0 is the top left hand corner of the monitor).
> What could be the simplest algo to find out if an added new
> rectangle overlaps any of the existing rectangles...?

What can be simpler than this?

        bool DoesNewRectOverlap(Rect newrect, Rect oldrects[], int no_of_rects){
                for(int i=0;i<no_of_rects; i++){
                        if( OverlapTest(newrect,oldrects[i]) return true;
                }
                return false;
        }

Well, you have to write a function "OverlapTest" for two rectangles, but that should be not too
hard.

- Michael -

 
 
 

What is a simple algorithm for creating non-overlapping rectangles?

Post by Jim Hargi » Sat, 07 Aug 1999 04:00:00


Performance depends on the no. of existing rectangles and queries.  If
nexisting or nquery = N  is greater than O(1,000), my guess would be that it
might be worth using a spatial data structure such as pr-kd tree or
quadtree,  to store the rectangles and their relative positions, which
should reduce the search time from your proposed O(nquery)*O(nexisting),
down to O(nquery * log2 (nexisting) ). Similar considerations hold for
multidimensional rectangles.  But your proposal is still valid for
reasonably small N.


>What can be simpler than this?

> bool DoesNewRectOverlap(Rect newrect, Rect oldrects[], int no_of_rects){
> for(int i=0;i<no_of_rects; i++){
> if( OverlapTest(newrect,oldrects[i]) return true;
> }
> return false;
> }

>Well, you have to write a function "OverlapTest" for two rectangles, but

that should be not too
Quote:>hard.

>- Michael -

 
 
 

What is a simple algorithm for creating non-overlapping rectangles?

Post by C.P. Chandrasek » Sun, 08 Aug 1999 04:00:00


How would the algorithm look like if we are supposed to use a quad tree?
I went by MS's original suggestion and it was indeed a strikingly (though
it didn't strike me at first!) simple solution. It works but O(nquery x log2(nexist))
sounds interesting!

Thx.
CP Chandrasekar

: Performance depends on the no. of existing rectangles and queries.  If
: nexisting or nquery = N  is greater than O(1,000), my guess would be that it
: might be worth using a spatial data structure such as pr-kd tree or
: quadtree,  to store the rectangles and their relative positions, which
: should reduce the search time from your proposed O(nquery)*O(nexisting),
: down to O(nquery * log2 (nexisting) ). Similar considerations hold for
: multidimensional rectangles.  But your proposal is still valid for
: reasonably small N.
:
:
: >>
: >What can be simpler than this?
: >
: > bool DoesNewRectOverlap(Rect newrect, Rect oldrects[], int no_of_rects){
: > for(int i=0;i<no_of_rects; i++){
: > if( OverlapTest(newrect,oldrects[i]) return true;
: > }
: > return false;
: > }
: >
: >Well, you have to write a function "OverlapTest" for two rectangles, but
: that should be not too
: >hard.
: >
: >
: >- Michael -
:

--
The surest sign that intelligent life exists elsewhere in the Universe is
that none of it has ever tried to contact us. -- Calvin

CP Chandrasekar,
Off: Telco Systems, 63, Nahatan St, Norwood, MA 02062 : Ph # 781 255 5217
Res: 301 Engamore Lane, Apt 13-T4, Norwood, MA 02062 :  Ph # 781 440 9508

 
 
 

What is a simple algorithm for creating non-overlapping rectangles?

Post by Jim Hargi » Mon, 09 Aug 1999 04:00:00


Basically, these are hierarchical data structures (related to the binary
search tree).  In the case of 2 dimensions: the quad tree uses 4 pointers
for each node, indicating the next node in the tree to check in each of the
4 quadrants; and the k-d tree uses one pointer per node.  Creating these
structures boils down to sorting multidimensional data.  There are many
papers and textbooks describing both of these, mostly tracing back to Jon
Bentley in the 1970's, and many textbooks have examples (see for instance,
H. Samet, "The Design and Analysis of Spatial Data Structures,"
Addison-Wesley, Reading, MA, 1990.).  Perhaps the easiest introduction to
these is at the following links:

http://www.cs.umd.edu/~brabec/quadtree/index.html
http://shum.huji.ac.il/~bennun/muky/java/index.html

Check and compare the size and performance of the Rectangle Quadtree and the
PMR rectangle k-d tree demos for your situation.  Somewhat more complicated
are the range tree and interval tree.  I don't recall any code for these at
Graphic Gems or in O'Rourke's  or Eberly's sites.

For other readers, regarding performance, please keep in mind the
limitations of the big-O notation.  For example, O(n), does not give you a
time, but an approximate number of comparisons proportional to the time,
where the proportionality constant varies between languages and algorithms.
For simple methods,O(n), it takes less time t1 per comparison; for spatial
structures, O(log(n)), it takes a little more t2 per comparison, but there
is a big reduction in the number of comparisons ( i.e. t2*O(log(n)) is less
than t1*O(n) for n sufficiently large!).  Thus, you will almost always
benefit if there is a sufficiently "large" number of items to compare.


>How would the algorithm look like if we are supposed to use a quad tree?
>I went by MS's original suggestion and it was indeed a strikingly (though
>it didn't strike me at first!) simple solution. It works but O(nquery x
log2(nexist))
>sounds interesting!

>Thx.
>CP Chandrasekar

 
 
 

What is a simple algorithm for creating non-overlapping rectangles?

Post by MS » Tue, 10 Aug 1999 04:00:00



> How would the algorithm look like if we are supposed to use a quad tree?
> I went by MS's original suggestion and it was indeed a strikingly (though
> it didn't strike me at first!) simple solution. It works but O(nquery x log2(nexist))
> sounds interesting!

Well, you asked for the most simple algorithm, not for the quickest one ;-)

- Michael -

--

 
 
 

1. Merging unit sqaures into non-overlapping rectangles

Apologies if this turns out to be a repost, but I'm not sure my first
attempt made it through.

I'm looking for an algorithm that will take a set of unit squares in 2D
space and output the smallest number of rectangles that cover all and
only the unit squares.  The algorithm doesn't have to be optimal, and I
can even tolerate some overlapping rectangles in the output (if that
helps), although I would prefer it if these were limited.

I appreciate any help.

Thank you,
Mark

Sent via Deja.com http://www.deja.com/
Before you buy.

2. Pure Windows parameter and handles to Builder

3. area of rectangles overlap algorithm needed

4. Linespoints style

5. Create a non-rectangle D3D window...

6. icons in files

7. Simple Question on Creating a Filled Rectangle Fast

8. need simple algorithm if point is inside rectangle

9. creating a transparent rectangle within a filled rectangle

10. Clever rectangle in rectangle clipping algorithm...

11. Rectangle in Rectangle Algorithm

12. How to partition a non-simple polygon with holes into some simple polygons