Как определить суперпозицию двух геометрических тел?

Доброго времени суток.

Столкнулся с интересной проблемой, хотелось бы спросить мнения у Хабрасообщества.

Есть геометрические объекты, определенные какой-то точкой (Положением, в простых фигурах типа прямоугольника или окружности это будет центром масс, в более сложных — неясно) и списком векторов, указывающих на углы этой фигуры, исходя от точки положения. Например, для прямоугольника длинной 10 и шириной 6 с положением (0, 0) векторы будут:
[-5, -3];
[-5, 3];
[5, 3];
[5, -3];

Вопрос: как определить (в общем случае, для любых фигур), наложились ли две фигуры друг на друга?

У меня есть идея: Если минимальное расстояние от положения фигуры 1 до углов фигуры 2 меньше чем какое — либо расстояние от положения фигуры 1 до углов фигуры 1, то они перекрываются (ну и соответственно та же проверка для фигуры 2). Но мне она не нравится, слишком большая сложность, не красиво… Есть ли у вас решения лучше?

Заранее спасибо
  • Вопрос задан
  • 3371 просмотр
Пригласить эксперта
Ответы на вопрос 3
Arktos
@Arktos
1. Проверить все отрезки на пересечение. Найдем, пересекаются ли фигуры. Осталось найти, вложены ли фигуры. Одна фигура вложена в другую, если все точки фигуры вложены в другую (задача сводится к определению, находится ли точка внутри многоугольника)
2. Алгоритм сканирующей прямой. В качестве событий: вершины многоугольников, точки пересечения отрезков (есть подозрение, что можно обойтись без них). Во множестве храним стороны многоугольников, пока перемещаем прямую, их положение по вертикали меняется, но взаимное расположение не должно меняться
Ответ написан
Комментировать
nickme
@nickme
Тогда уж проще проверить, пересекаются ли какие-нибудь две стороны (из разных многоугольников) или нет. Тупой алгоритм будет квадратичным. Можно воспользоваться методом выметающей прямой (sweep line algorithm), который работает за время O(nlogn). Есть описание на русском в книжке Препараты и Шеймоса (издание 1989 г.) «Вычислительная геометрия» стр. 341 и ниже.
PS: прямоугольник из вашего примера будет иметь длину 10 и ширину 6, а не 5 и 3…
Ответ написан
VanDamM
@VanDamM
Software Developer
Ответ здесь - algolist.ru/maths/geom
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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