Этот вопрос теперь является первым элементом в Bing или Google при поиске слова «определить выпуклый многоугольник». Однако ни один из ответов не является достаточно хорошим.
Принятый ответ от @ EugeneYokota работает, проверяя, можно ли превратить неупорядоченный набор точек в выпуклый многоугольник, но это не то, что запрашивал OP. Он попросил метод проверки, является ли данный многоугольник выпуклым или нет. («Многоугольник» в информатике обычно определяется [как в XFillPolygon документация ] как упорядоченный массив 2D точек, с последовательными точками, соединенными стороной, а также последней точкой с первой.) Кроме того, алгоритм подарочной упаковки в этом случае будет иметь сложность по времени O(n^2) для n баллов - что намного больше, чем фактически необходимо для решения этой проблемы, в то время как вопрос требует эффективного алгоритма.
@ ответ Джейсона , наряду с другими ответами, которые следуют его идее, принимает звездных многоугольников , таких как пентаграмма или один в комментарии @ zenna, но звездные многоугольники не считаются выпуклыми. Как
@plasmacel отмечает в комментарии, что это хороший подход, если вы уже знаете, что многоугольник не является самопересекающимся, но он может потерпеть неудачу, если у вас нет этих знаний.
@ Ответ Секата правильный, но он также имеет сложность по времени O(n^2) и, следовательно, неэффективен.
@ Добавленный ответ LorenPechtel после ее редактирования - лучший здесь, но он расплывчатый.
Правильный алгоритм с оптимальной сложностью
Алгоритм, который я здесь представляю, имеет временную сложность O(n), корректно проверяет, является ли многоугольник выпуклым или нет, и проходит все тесты, которые я ему бросил. Идея состоит в том, чтобы пересечь стороны многоугольника, отмечая направление каждой стороны и подписанное изменение направления между последовательными сторонами. «Подпись» здесь означает, что левый положительный, а правый отрицательный (или обратный), а прямой - ноль. Эти углы нормализованы, чтобы быть между минус-пи (эксклюзив) и пи (включительно). Суммирование все эти углы изменения направления (иначе как отклонение углов) вместе приведут к плюс-минус одному повороту (то есть 360 градусов) для выпуклого многоугольника, тогда как звездообразный многоугольник (или самопересекающийся цикл) будет иметь другую сумму ( n * 360 градусов, для n поворотов в целом, для полигонов, где все углы отклонения имеют одинаковый знак). Таким образом, мы должны проверить, что сумма углов изменения направления плюс-минус один оборот. Мы также проверяем, что все углы изменения направления являются положительными или отрицательными, а не обратными (пи радиан), все точки являются фактическими 2D точками и что никакие последовательные вершины не являются идентичными. (Этот последний пункт является дискуссионным - вы можете разрешить повторные вершины, но я предпочитаю запрещать их.) Комбинация этих проверок охватывает все выпуклые и невыпуклые многоугольники.
Вот код для Python 3, который реализует алгоритм и включает некоторые незначительные преимущества. Код выглядит длиннее, чем на самом деле, из-за строк комментариев и ведения бухгалтерии, чтобы избежать повторного доступа к точкам.
TWO_PI = 2 * pi
def is_convex_polygon(polygon):
"""Return True if the polynomial defined by the sequence of 2D
points is 'strictly convex': points are valid, side lengths non-
zero, interior angles are strictly between zero and a straight
angle, and the polygon does not intersect itself.
NOTES: 1. Algorithm: the signed changes of the direction angles
from one side to the next side must be all positive or
all negative, and their sum must equal plus-or-minus
one full turn (2 pi radians). Also check for too few,
invalid, or repeated points.
2. No check is explicitly done for zero internal angles
(180 degree direction-change angle) as this is covered
in other ways, including the `n < 3` check.
"""
try: # needed for any bad points or direction changes
# Check for too few points
if len(polygon) < 3:
return False
# Get starting information
old_x, old_y = polygon[-2]
new_x, new_y = polygon[-1]
new_direction = atan2(new_y - old_y, new_x - old_x)
angle_sum = 0.0
# Check each point (the side ending there, its angle) and accum. angles
for ndx, newpoint in enumerate(polygon):
# Update point coordinates and side directions, check side length
old_x, old_y, old_direction = new_x, new_y, new_direction
new_x, new_y = newpoint
new_direction = atan2(new_y - old_y, new_x - old_x)
if old_x == new_x and old_y == new_y:
return False # repeated consecutive points
# Calculate & check the normalized direction-change angle
angle = new_direction - old_direction
if angle <= -pi:
angle += TWO_PI # make it in half-open interval (-Pi, Pi]
elif angle > pi:
angle -= TWO_PI
if ndx == 0: # if first time through loop, initialize orientation
if angle == 0.0:
return False
orientation = 1.0 if angle > 0.0 else -1.0
else: # if other time through loop, check orientation is stable
if orientation * angle <= 0.0: # not both pos. or both neg.
return False
# Accumulate the direction-change angle
angle_sum += angle
# Check that the total number of full turns is plus-or-minus 1
return abs(round(angle_sum / TWO_PI)) == 1
except (ArithmeticError, TypeError, ValueError):
return False # any exception means not a proper convex polygon