View Full Version : Rectangle layout and occlusion avoidance

05-15-2006, 05:04 AM
Hi there,

I was wondering if someone could point me in the right direction. This is probably not strictly a GL style of issue so my apologies in advance, but I will be programming the solution in GL.

I have a number of rectangles and wish to avoid having them occlude each other. A friend suggested a magnet style of effect where a rectangle is effectively attracted to a point but repelled by other rectangles in the vicinity. Happy to consider other techniques though. The end goal is just to space out rectangles so that they don't overlap each other (or do so at a minimum), but have some relationship with the point they've been associated with.

My application shows flight paths and I'm labelling these paths with a flight number. With many flight paths, I have flight numbers overlapping each other.

Thanks for any help.


Jack Dingler
05-19-2006, 02:03 PM
Your friend's suggestion is essentially how I've handled that problem in the past.

Consider though that the more rectangles you have, the more calculations you'll incur if you check against all of them. The number of calculations will increase by the power of two.

So to simplify, you might make a grid of pointers to the rectangles, representing a low rez integer representation of the their coordinates. Each rectangle might for instance cover, a 3X8 section of the grid. As you move the rectangles around, you'd calculate the center point and apply it's pointer to that grid location and removing the old one.

You want to make sure that no two rectangles are positioned on the same center.

Then to find a rectangle's neighbors to compare against, You'd scan only a few grid points where two recs might interlap.

This way, as you add rectangles, your searches will expand in a linear fashion and not exponentially. A rectangle with no neighbor's will not need to be compared against anything except it's focal point.

05-29-2006, 04:04 AM
Thanks for this Jack - very interesting idea.