Проверить, симметричен ли многоугольник

Question

Учитывая многоугольник (не обязательно выпуклый) в декартовой координате, мне интересно, есть ли способ проверить симметричность этого многоугольника?

Я могу придумать решение O (N): использование вращающихся штангенциркулей, чтобы проверить, параллельна ли каждая пара противоположных кромок и равна ли она по размеру.Однако я не могу доказать правильность этого алгоритма.Можете ли вы предложить лучшее решение?

Answer 1

• Вы вычисляете центр тяжести своего многоугольника.
• Вы переводите его в начало координат так, чтобы ваш центр тяжести имел координату (0,0).
• Затем для каждой вершины с координатами (i, j) вы проверяете, что существует вершина с координатами (-i, -j).

Это докажет, что ваш многоугольник действительно симметричен.

Сложность: N, при условии, что вы можете получить прямой доступ к своим вершинам по их координатам.

Answer 2

Вы должны прояснить, какая симметрия разрешена.Центральная симметрия (также известная как поворот на 180 градусов)?Зеркальная симметрия по одной из осей?Вращение на любую степень?В некоторых приложениях разрешено вращение только на 0,90,180,270 + зеркалирование ... В каждом случае ответ будет другим.

Только для центральной симметрии, если вы предполагаете, что многоугольник хорошо репрезентативен (т.е. на ребрах нет лишних вершин, а вершины удерживаются в операторе forward, то центрально-симметричный многоугольник будет иметь четное число 2 * N вершин., и вы можете сделать это:

1. Установите для iter1 ссылку на 0-ю вершину, а для iter2 - для ссылки на N-ю вершину.

2. Повторить N раз:

   if (* iter1!= * iter2) return false;

3. return true;

Answer 3

Сначала вам нужно определить тип симметрии, которую вы хотите проверить (при каком преобразовании ваш многоугольник должен быть инвариантным).Предоставленный вами алгоритм проверит центральную симметрию для выпуклых многоугольников (поскольку вращающиеся штангенциркули работают только с выпуклыми многоугольниками).