Search code examples
algorithmgisgraphics2d

2D objects distribution algo

I have to align elements in such a way to avoid their intersection, but not moving them too far:

Before and after

For simplicity, elements are rectangular (actually bounding boxes). Elements can move only by it's normal vector (can be any angle).

Is there any well-known algorithm, that can used here? About 50-200 elements have to be aligned each time (delay is matter, it should be a few milliseconds), and I don't think, that brute force is a good idea (but didn't try yet)

Going deeper: I have to implement street's name labeling. Let's say, I have vector lines (streets), and now, text should be displayed along those vectors (it can be rotated, not twisted). But text shouldn't overlap much, so I have to move it along its vector line . Maybe some algo for this stuff?

All it happens in run-time, when user navigates over the streets.

PS: I use Qt (simple QPainter, not the graphic framework)

Solution

  • OK, after long time, I found something suitable: Automatic label placement, Dynamic Label Placement in Practice