@Gruberhoff

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

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

Конечный результат реализации можно увидеть в некоторых редакторах, таких как Keynote или PowerPoint.
pdahx.jpg
5d31a53655647855587534.jpeg
Важно: алгоритм должен вычислять точки, в которых прямоугольник будет равноудален относительно ближайших братьев и сестер. Таким образом, при перетаскивании близко к равноудаленной точке можно будет примагнитить край прямоугольника к этой точке.

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


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

Есть ли способ оптимизировать мой алгоритм?
  • Вопрос задан
  • 335 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Ваш алгоритм надо лишь немного доработать.

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

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

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

Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Stalker_RED
@Stalker_RED
Стройте сетку к которой хотите "примагнитится" и при приближении к ней - подталкивайте в нужную сторону.

Примеры можно нагуглить как-то так
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы