Non-overlapping non-convex polygons

Question

Suppose a set of n randomly distributed non-convex polygons P={Pi}, n = |P|, in the plane, some of them overlap (approx 50% of them overlap each other).

1] Move the polygons such that no overlap occurs.

2] Only "small" shifts are allowed (the relative position of objects Pi is preserved as far as possible).

In my opinion, the problem is NP-hard. I tried several approaches (stochastic optimization minimizing overlap area + shifts), moving all in one (random shaking), adding outside the convex hull (works well for convex polygons but for non-convex ones suffers from large shifts),...

The most promissing is the incremental method using a simple heuristic (move in 2 directions).

0] Compute minimum bounding boxes (MBB) for all Pi. Sort Pi by area.
1] Add a Pi to the solution S and check for overlaps
    1.a] Test intersection  Pi vs. all Pj in S.
    1.b] If MBB(Pj) vs. MBB(Pi) overlap, check the polygons Pi vs. Pj: 
        1.b.1] If Pi, Pj overlap, moving Pi perpendicular to Pj (left, right) by s may help
        1.b.2] Suppose Pi1=Pi(sl), Pi2=Pi(sr) to be shifted Pi, shifts sl=s, sr=-s
        1.b.3] Check, which direction is more perspective:
        1.b.4] While intersections Pi1 vs. Pj exist //Left
           1.b.4.a] Preselect collisions Pi1 vs. all Pj by MBB.
           1.b.4.b] If MBB(Pi1) and MBB(Pj) overlap, check Pi1 vs. Pj
           1.b.4.c] If overlap found sl = sl + s;
           1.b.4.c] Shift Pi1(sl);
        1.b.5] While intersections Pi1 vs. Pj exist //Right
           1.b.5.a] Preselect collisions Pi1 vs.all Pj by MBB.
           1.b.5.b] If MBB(Pi1) and MBB(Pj) overlap, check Pi1 vs. Pj
           1.b.5.c] If overlap found sr = sr + s;
           1.b.5.d] Shift Pi2(sr);
        1.b.6] Assign Pi = Pi1 or Pi = Pi2 (the faster).

Unfortunately, for large n (thousands) the incremental method is slow. Is there any possible speed improvement or a better method exists? The most effort is spent with the unnecessary shifts and checks...

The Voronoi tesselation of polygons may help with the movent of polygons inside the cells... We also may check, which Voronoi cells are affected adding a new cell (generator is represented by the polygon)... Maybe, the movement can be computed as the average vector of Pi centroid and centroid of polygons in affected cells.

Thank you very much for your help.

@n.m To avoid the significant reshuffle of objects the relative position of them should be preserved as far as possible. Using the differential evolution, I tried to minimize the objective function containing the square of shifts and overlapping area. — justik
@n.m A simple method, adding Pi outside convex hull of S leads to large residuals between the old and new positions... — justik
some general ideas: * try using the 'best' separation direction, which can be approximated as a perpendicular to the line between the 2 intersection points * if you are concerned about speed, optimize the hell out of your intersection checking code, use some broad-phase collision optimization (2d hash grid, sweep-and-prune, etc) * to get nice 'close to the global minimum' results, instead of full unprojection at each step, try 'relaxing' them, i.e. move them apart only by a fraction of it, kind of like if you were simulating them as physical objects — Anton Knyazyev
@Anton: Thanks for your comments and advices... However, in some specific cases, using the approximated separation direction may lead to the stuck. Adding a new rectangle between two rectangles leads to the infinite movement between them. Changing the direction randomly after passing several steps may help... — justik

Yves Daoust Yves Daoust · Accepted Answer · 2015-12-08T09:41:11

Choose one vertex of every polygon, making sure that none of the chosen ones coincide. (If this isn't possible, you are in trouble.) Determine the tightest bounding square for all polygons, and divide the side of the largest square by the shortest horizontal/vertical distance between the chosen vertices.

Multiply the coordinates of all chosen vertices by this factor, and translate the remaining vertices accordingly (without rescaling). This will take all polygons apart while keeping their placement very similar.

Maybe this solution will be too "sparse" to your taste; it can be used as a starting point for re-packing, without creating overlaps again.

Non-overlapping non-convex polygons

1 Answers