Неперекрывающиеся невыпуклые многоугольники

Question

Предположим, что на плоскости набор из n случайно распределенных невыпуклых многоугольников P={Pi}, n = |P|, некоторые из них перекрываются (примерно 50% перекрывают друг друга).

1] Переместите полигоны так, чтобы не происходило перекрытие.

2] Допускаются только "небольшие" сдвиги (относительное положение объектов Pi сохраняется в максимально возможной степени).

На мой взгляд, проблема NP-сложная. Я попробовал несколько подходов (стохастическая оптимизация, минимизирующая область перекрытия + сдвиги), перемещение все в одном (случайное встряхивание), добавление вне выпуклой оболочки (хорошо работает для выпуклых многоугольников, но для невыпуклых страдает от больших сдвигов),...

Наиболее перспективным является инкрементальный метод с использованием простой эвристики (движение в 2 направлениях).

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).

К сожалению, для больших n (тысяч) инкрементный метод медленный. Есть ли возможное улучшение скорости или существует лучший метод? Больше всего усилий затрачивается на ненужные смены и проверки...

Тесселяция многоугольников Вороного может помочь с движением многоугольников внутри ячеек... Мы также можем проверить, на какие ячейки Вороного влияют, добавив новую ячейку (генератор представлен многоугольником)... Возможно, движение можно вычислить как средний вектор пироцентриков и центроидов многоугольников в пораженных клетках.

Большое спасибо за Вашу помощь.

Answer 1

Выберите одну вершину каждого многоугольника, убедившись, что ни одна из выбранных не совпадает. (Если это невозможно, у вас проблемы.) Определите самый плотный ограничивающий квадрат для всех многоугольников и разделите сторону самого большого квадрата на самое короткое расстояние по горизонтали / вертикали между выбранными вершинами.

Умножьте координаты всех выбранных вершин на этот коэффициент и переведите остальные вершины соответствующим образом (без масштабирования). Это разделит все полигоны, оставляя их расположение очень похожим.

Возможно, это решение будет слишком "редким" на ваш вкус; его можно использовать в качестве отправной точки для переупаковки без повторного наложения.