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

Question

У меня есть небольшая конкурсная задача, в которой задается набор точек в 2D, которые образуют треугольник. Этот треугольник может подвергаться произвольному повороту, может подвергаться произвольному перемещению (как в 2D-плоскости), так и отражаться от зеркала , но его размеры остаются неизменными Затем они дают мне набор точек на плоскости, и я должен найти 3 точки, которые образуют мой треугольник после одной или нескольких из этих геометрических операций.

Пример:

5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
Output:
5 17
10 5
15 20

Бьюсь об заклад, он должен применять какой-то известный алгоритм, но я не знаю, какой. Наиболее распространенными являются: выпуклый корпус, плоскость развертки, триангуляция и т. Д.

Может кто-нибудь дать совет? Мне не нужен код, только толчок, пожалуйста!

Answer 1

Треугольник однозначно определяется (игнорируя повороты, перевороты и сдвиги) по длине трех сторон. Пометьте вершины вашего исходного треугольника A, B, C. Ты смотришь для точек D, E, F таких, что | AB | = | DE |, | AC | = | DF |, и | BC | = | EF |. Длина дается формулой Пифагора (но вы можете сохранить операцию квадратного корня в каждом тесте, сравнивая квадраты длин отрезков ...)

Answer 2

Данный треугольник определяется тремя длинами. Вы хотите найти три точки в списке, разделенные именно этими длинами.

Квадрат заданной длины, чтобы не беспокоить sqrt.

Найдите квадрат расстояния между каждой парой точек в списке и отметьте только те, которые совпадают с заданными длинами: O (V ^ 2), но с низким коэффициентом, потому что большинство длин не будут совпадать.

Теперь у вас есть разреженный граф с O (V) ребрами. Найдите каждый цикл размера 3 за время O (V) и обрежьте спички. (Не уверен в лучшем способе, но здесь есть один способ с правильным big-O.)

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

Answer 3

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

Answer 4

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

1. Для исходного треугольника A, B, C рассчитайте произведение точек AB.AC, BA.BC и CA.CB
2. Для каждого набора из трех точек D, E, F рассчитайте точечное произведение DE.DF и сравните с тремя точечными произведениями из 1.

Это работает с AB.AC = | AB | x | AC | x cos (a), две длины и угол между ними определяют треугольник.

РЕДАКТИРОВАТЬ: Да, Джим прав, просто одного точечного продукта недостаточно, вам нужно будет выполнить все три, включая ED.EF и FD.FE. Таким образом, в конце концов, в этом вычислении используется то же количество вычислений, что и в методе квадратных расстояний.