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

Question

[Mgrin]

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

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

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

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

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

Заранее спасибо

Comments

[serso]

Фигуры выпуклые? Насколько я понял из вопроса речь идёт только у многоугольниках?

Answer 1

[Arktos]

1. Проверить все отрезки на пересечение. Найдем, пересекаются ли фигуры. Осталось найти, вложены ли фигуры. Одна фигура вложена в другую, если все точки фигуры вложены в другую (задача сводится к определению, находится ли точка внутри многоугольника)
2. Алгоритм сканирующей прямой. В качестве событий: вершины многоугольников, точки пересечения отрезков (есть подозрение, что можно обойтись без них). Во множестве храним стороны многоугольников, пока перемещаем прямую, их положение по вертикали меняется, но взаимное расположение не должно меняться

Answer 2

[nickme]

Тогда уж проще проверить, пересекаются ли какие-нибудь две стороны (из разных многоугольников) или нет. Тупой алгоритм будет квадратичным. Можно воспользоваться методом выметающей прямой (sweep line algorithm), который работает за время O(nlogn). Есть описание на русском в книжке Препараты и Шеймоса (издание 1989 г.) «Вычислительная геометрия» стр. 341 и ниже.
PS: прямоугольник из вашего примера будет иметь длину 10 и ширину 6, а не 5 и 3…

Comments

[Mgrin]

На счет прямоугольника — да, спасибо, ошибся =)
За алгоритм спасибо, гляну. Поп поводу пересечения двух сторон — тоже как-то не хочется, очень ресурсоемко будет получить сторону…

[nickme]

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

Answer 3

[Иван Калининский]

Ответ здесь - algolist.ru/maths/geom