Как это делают приложения для векторного рисования?

Question

В Illustrator вы можете перетащить прямоугольник, и он выделит все объекты в нем. Он выходит за рамки ограничивающего прямоугольника, поскольку обеспечивает его соприкосновение с реальной частью многоугольника. Как это эффективно сделать это тогда? (Реализация на C или C ++ была бы предпочтительнее)

Спасибо

Answer 1

Если вы хотите проверить, находится ли какая-либо часть многоугольника P внутри прямоугольника R, то вы можете сделать это:

• Если какая-либо вершина P находится в пределах R, вернуть TRUE;
• Если какая-либо вершина из R находится в P, вернуть TRUE;
• Если любое ребро P (линия между смежными вершинами) пересекает ребро R, вернуть TRUE.
• В противном случае верните FALSE.

Answer 2

Вы также можете просто построить пересечение прямоугольника с объектом (функция, которую программы, такие как Illustrator, уже имеют для многих других целей) и проверить, что он не пустой.Доступны более эффективные алгоритмы (см. Ответ caf), но у меня есть одно преимущество: он не требует дополнительного кода.