Какие существуют алгоритмы поиска равноудаленных прямоуголиников?

Question

[Gruberhoff]

Я ищу алгоритм или библиотеку для рисования линий связи между равноудаленными прямоугольниками. Мне нужно реализовать такую возможность в редакторе, написанном на javascript. Все прямоугольники могут перетаскиваться, и алгоритм должен быть максимально эффективным.

Конечный результат реализации можно увидеть в некоторых редакторах, таких как Keynote или PowerPoint.


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

Я попробовал реализовать следующий алгоритм:

1. Поиск всех прямоугольников по осям X и Y относительно перетаскиваемого (выделенного) прямоугольника
   
2. Разделить найденные множества на подмножества: "top", "bottom", "left", "right" и найти ближайший прямоугольник к выбранному прямоугольнику в каждом подмножестве
   
3. вычислить расстояния (D) между перетаскиваемым и ближайшим прямоугольником
   
4. Повторить процедуру, начиная с шага 1, для прямоугольников, найденных на шаге 2. Но вместо поиска ближайшего, искать прямоугольник на расстоянии D
   
5. Повторять шаг 4 рекурсивно, пока прямоугольники на расстоянии D не будут найдены
   

Я не могу вычислить точки равноудаленности для фичи примагничивания при перетаскивания прямоугольника. Также меня беспокоит производительность, так как все вычисления и сортировки должны выполняться по событию "ondrag" (многократно в секунду).

Есть ли способ оптимизировать мой алгоритм?

Answer 1

[Wataru]

Ваш алгоритм надо лишь немного доработать.

1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

Если есть пересечения то можно или выбрасывать прямоугольники, пересекающиеся с текущим, или остановится, как будто следующего прямоугольника нет.

Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.

Answer 2

[Stalker_RED]

Стройте сетку к которой хотите "примагнитится" и при приближении к ней - подталкивайте в нужную сторону.

Примеры можно нагуглить как-то так