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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

   if (* iter1! = * Iter2) вернуть false;

3. вернуть true;