Прямоугольники с привязкой при изменении размера и перемещении

Question

У меня есть холст, на котором я могу рисовать, изменять размер и перемещать прямоугольники вокруг.

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

Я пробовал разные подходы, но я не мог заставить работать один.

Все мои подходы основаны на простом цикле, который проверяет прямоугольник, который я редактирую (E), с другими прямоугольниками (O [n]).

Предотвращение перекрытия не является проблемой, моя проблема заключается в том, что он может изменить E во время итерации O.

Например, если я перемещу E рядом с O [1], он будет привязываться к нему, но эта привязка может создать перекрытие с O [0], перекрытие, которое не будет проверено.

Прежде чем я начал делать что-то рекурсивное или слишком наивное, мне было интересно, знает ли кто-нибудь лучший подход.

Answer 1

Поможет ли двухпроходный подход, например,

1. В первом проходе отметьте E относительно O и сгенерируйте короткий список кандидатов на защелки.1007 *

   Во втором проходе проверьте каждого из кандидатов на привязку для перекрытия с O.

Если сканирование всего списка O непомерно дорого (усилие растет сколичество объектов), рассмотрим квад-дерево для хранения объектов и / или их вершин.Quadtree позволяет вам сузить близлежащие точки гораздо быстрее.