Moving rectangles to avoid overlapping

Moving rectangles to avoid overlapping

Post by Olivier Guilli » Wed, 16 Oct 2002 23:23:51



Hi,

Given a set of rectangles, is there an algorithm that enables to move
them slightly so that none of them will overlap with others ?

I need this to display text items on a map, and would need the
rectangles not to be moved too far away from their original position.

I presume this problem has already been encountered by somebody else,
and that this algorithm is highly recursive...

Thanks for any help, link or advice you could provide on this topic.

Olivier Guillion
Myriad software

(please remove the word before .com to get my real address)

 
 
 

Moving rectangles to avoid overlapping

Post by Hans-Bernhard Broeke » Thu, 17 Oct 2002 00:46:16



> I presume this problem has already been encountered by somebody else,
> and that this algorithm is highly recursive...

Not necessarily recursive, but iterative.  With a serious probability
of oscillating behaviour that refuses to settle down on one particular
solution, too.

The "obvious" method would be to model each box as a physical body,
and all existing intersections to create repelling forces between
these bodies.  Add some damping, and forces that try to pull every box
back to its home position, and model the resulting mechanical system,
until all intersections are resolved.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Moving rectangles to avoid overlapping

Post by Olivier Guilli » Thu, 17 Oct 2002 01:03:01


On 15 Oct 2002 15:46:16 GMT, Hans-Bernhard Broeker



>> I presume this problem has already been encountered by somebody else,
>> and that this algorithm is highly recursive...

>Not necessarily recursive, but iterative.  With a serious probability
>of oscillating behaviour that refuses to settle down on one particular
>solution, too.

>The "obvious" method would be to model each box as a physical body,
>and all existing intersections to create repelling forces between
>these bodies.  Add some damping, and forces that try to pull every box
>back to its home position, and model the resulting mechanical system,
>until all intersections are resolved.

It is a great idea. Not very suitable for an instant display with
many, many rectangles (quite time-consuming) but that can provide nice
animation effects when items are moving on the map (two rectangles
overlap, then slightly move away from each other until there is no
more overlapping)

Thanks a lot !

Olivier Guillion
Myriad software

(please remove the word before .com to get my real address)

 
 
 

Moving rectangles to avoid overlapping

Post by Ian Kemmi » Thu, 17 Oct 2002 03:59:08




Quote:

>Given a set of rectangles, is there an algorithm that enables to move
>them slightly so that none of them will overlap with others ?

In general, obviously not, since the total area of the rectangles *may* be
greater than the total area of the map:-)

This suggests that *one* of the strategies for fitting the labels onto the map
*must* be to reduce the size of the text.

Given that as a last resort, the problem seems much more tractable.  If you
have lots of overlap, reduce the size of one class of text labels until there
is a small enough amount of overlap that you can nudge the labels around.

You'll also need to specify, separately for each label, just how far it is
allowed to move in each direction.  It's clearly no use if the label for Nether
Wallop ends up over Piddle Wyre.

Whatever, the solution is, it probably involves adding labels to a map one at a
time, and trying hard not to move any labels that have already been placed.  As
long as you add labels in decreasing order of `importance' (most important ==
least able to move), you should be on the right track.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ian Kemmish                   18 Durham Close, Biggleswade, Beds SG18 8HZ, UK

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Never forget that the sole purpose of your life may be to serve
as a warning to others.

 
 
 

Moving rectangles to avoid overlapping

Post by Richard J Kinc » Thu, 17 Oct 2002 14:43:01


Quote:Olivier Guillion writes:
> Given a set of rectangles, is there an algorithm that enables to move
> them slightly so that none of them will overlap with others ?

This is the map labeling problem.

NP complete.

Google "annealing".

 
 
 

Moving rectangles to avoid overlapping

Post by Ole-Hjalmar Kristense » Thu, 17 Oct 2002 18:36:26



> Hi,

> Given a set of rectangles, is there an algorithm that enables to move
> them slightly so that none of them will overlap with others ?

> I need this to display text items on a map, and would need the
> rectangles not to be moved too far away from their original position.

> I presume this problem has already been encountered by somebody else,
> and that this algorithm is highly recursive...

> Thanks for any help, link or advice you could provide on this topic.

> Olivier Guillion
> Myriad software

> (please remove the word before .com to get my real address)

I actually solved a similar problem years ago, namely "optimal"
placement of GUI components within a window, one of the criteria being
no overlap. I tried several algorithms, simulated annealing gave the
best results, but was also the slowest. You could probably get away
with just adding a repulsive force between the rectangles, while at
the same time attracting them to the original position.

If there are just a few rectangles that overlap, you could just do an
exhaustive search around the initial position, as you know the final
position will not be much difefrent.  Anyway, it seems that you should
start with defining a goodness criteria or cost function for your
problem, then try to optimize this.

 
 
 

Moving rectangles to avoid overlapping

Post by Gerry Qui » Thu, 17 Oct 2002 19:51:43




>> I presume this problem has already been encountered by somebody else,
>> and that this algorithm is highly recursive...

>Not necessarily recursive, but iterative.  With a serious probability
>of oscillating behaviour that refuses to settle down on one particular
>solution, too.

What's essential in this kind of thing is to progressively relax the
conditions, so at least you'll get some result, even if it's not ideal.

Gerry Quinn                                  
--
http://bindweed.com
Entertainment software for Windows
Puzzles, Strategy Games, Kaleidoscope Screensaver
Download evaluation versions free - no time limits

 
 
 

1. Overlapping rectangles -- HELP

I thought this would be trivial problem, but...

If I have the 4 vertices of two rectangles, is there a quick and easy way
to tell if they overlap.  I don't even need the overlapping region!

All I've thoght of so far is brute force checing several cases.  
eg.  one in other, other in one, one with vertices in other, other with
verticies in one, one with line through other, other with line through
one...  I must be missing the boat big time here!

Any help would be GREATLY appreciated!

Thanks,
-Gary

2. Buying older versions of 3D Studio - legal?

3. Checking rectangle overlap in a plane

4. Video Cards

5. Overlap of Rectangles

6. Drawtext on multiple pages

7. Checking rectangle overlap in a plane

8. TERRAGEN NEW PICS

9. Merging unit sqaures into non-overlapping rectangles

10. area of rectangles overlap algorithm needed

11. Polygon from overlapping Rectangles?

12. Rectangles overlapping

13. Overlapping rectangles