Как я могу эффективно определить, является ли многоугольник выпуклым, невыпуклым или сложным?

ПРИМЕЧАНИЕ: вычисление выпуклой оболочки набора точек совершенно не нужно, если вы просто хотите определить, является ли список точек, представляющих многоугольник, выпуклым многоугольником.

См. Алгоритм упаковки подарков :

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

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

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

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

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

  given p[k], p[k+1], p[k+2] each with coordinates x, y: dx1 = x[k+1]-x[k] dy1 = y[k+1]-y[k] dx2 = x[k+2]-x[k+1] dy2 = y[k+2]-y[k+1] zcrossproduct = dx1*dy2 - dy1*dx2 

Многоугольник выпуклый, если z-компоненты поперечных произведений либо все положительные, либо все отрицательные. В противном случае многоугольник невыпуклый.

Если есть N точек, убедитесь, что вы вычислили N кросс-продуктов, например, не забудьте использовать триплеты (p [N-2], p [N-1], p [0]) и (p [N-1], р [0], р [1]).

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

Следующая функция / метод Java – это реализация алгоритма, описанного в этом ответе .

 public boolean isConvex() { if (_vertices.size() < 4) return true; boolean sign = false; int n = _vertices.size(); for(int i = 0; i < n; i++) { double dx1 = _vertices.get((i + 2) % n).X - _vertices.get((i + 1) % n).X; double dy1 = _vertices.get((i + 2) % n).Y - _vertices.get((i + 1) % n).Y; double dx2 = _vertices.get(i).X - _vertices.get((i + 1) % n).X; double dy2 = _vertices.get(i).Y - _vertices.get((i + 1) % n).Y; double zcrossproduct = dx1 * dy2 - dy1 * dx2; if (i == 0) sign = zcrossproduct > 0; else if (sign != (zcrossproduct > 0)) return false; } return true; } 

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

Этот вопрос теперь является первым пунктом в Bing или Google, когда вы ищете «определить выпуклый многоугольник». Однако ни один из ответов не является достаточно хорошим.

Принятый ответ @EugeneYokota работает, проверяя, может ли неупорядоченный набор точек быть выпущенным выпуклым многоугольником, но это не то, о чем попросил ОП. Он попросил метод проверить, является ли данный многоугольник выпуклым или нет. («Многоугольник» в информатике обычно определяется [как в документации XFillPolygon ] как упорядоченный массив двумерных точек с последовательными точками, соединенными с боком, а также с последней точкой для первого.) Кроме того, алгоритм упаковки подарка в этом случае имела бы временную сложность O(n^2) для n точек, что намного больше, чем фактически необходимо для решения этой проблемы, в то время как вопрос требует эффективного алгоритма.

@ Ответ Джейсона , наряду с другими ответами, которые следуют его идее, принимает звездные полигоны, такие как пентаграмма или тот, что есть в комментарии @ zenna, но звездные полигоны не считаются выпуклыми. Как замечает @plasmacel в комментарии, это хороший подход к использованию, если у вас есть предварительное знание о том, что многоугольник не является самопересекающимся, но он может потерпеть неудачу, если у вас нет этого знания.

@ Ответ Сехата верен, но он также имеет сложность времени O(n^2) и, следовательно, неэффективен.

@ Добавленный ответ LorenPechtel после ее редактирования является лучшим здесь, но он неопределен.

Правильный алгоритм с оптимальной сложностью

Алгоритм, который я здесь представляю, имеет сложность времени O(n) , правильно проверяет, является ли многоугольник выпуклым или нет, и передает все тесты, которые я выбрал для него. Идея состоит в том, чтобы пересекать стороны многоугольника, отмечая направление каждой стороны и подписанное изменение направления между последовательными сторонами. «Подпись» здесь означает, что левая позиция положительная, а правая – отрицательная (или обратная) и прямолинейная – равна нулю. Эти углы нормализуются между минус-пи (эксклюзивными) и pi (включительно). Суммирование всех этих углов изменения направления (так называемых углов отклонения ) вместе приведет к плюс-минус один оборот (т.е. 360 gradleусов) для выпуклого многоугольника, тогда как звездный многоугольник (или самопересекающийся контур) будет иметь другая сумма ( n * 360 gradleусов, для n оборотов в целом, для полигонов, где все углы отклонения имеют один и тот же знак). Поэтому мы должны проверить, что сумма углов смены направления составляет плюс-минус один оборот. Мы также проверяем, что углы изменения направления все положительные или все отрицательные и не меняются (pi радиан), все точки являются действительными двумерными точками и что никакие последовательные вершины не совпадают. (Этот последний пункт является спорным – вы можете разрешить повторяющиеся вершины, но я предпочитаю, чтобы запретить их.) Сочетание этих проверок улавливает все выпуклые и не выпуклые многоугольники.

Вот код для Python 3, который реализует алгоритм и включает некоторые незначительные преимущества. Код выглядит длиннее, чем на самом деле, из-за строк комментариев и бухгалтерии, связанных с предотrotationм повторных точек доступа.

 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 

Вот тест, чтобы проверить, выпущен ли многоугольник.

Рассмотрим каждый набор из трех точек вдоль многоугольника. Если каждый угол составляет 180 gradleусов или меньше, у вас есть выпуклый многоугольник. Когда вы определяете каждый угол, также сохраняйте общее количество (180 – угол). Для выпуклого многоугольника это будет 360.

Этот тест проходит в O (n) времени.

Обратите также внимание, что в большинстве случаев этот расчет – это то, что вы можете сделать один раз и сохранить – большую часть времени у вас есть набор полигонов для работы с ними, которые не меняются все время.

Чтобы проверить, является ли многоугольник выпуклым, каждая точка многоугольника должна быть ровной или за каждой линией.

Вот пример картинки:

Ответ @RoryDaulton мне кажется лучшим, но что, если один из углов точно равен 0? Некоторым может потребоваться, чтобы в таком случае края возвращался True, и в этом случае измените «<=» на «<» в строке:

 if orientation * angle < 0.0: # not both pos. or both neg. 

Вот мои тестовые примеры, которые подчеркивают проблему:

 # A square assert is_convex_polygon( ((0,0), (1,0), (1,1), (0,1)) ) # This LOOKS like a square, but it has an extra point on one of the edges. assert is_convex_polygon( ((0,0), (0.5,0), (1,0), (1,1), (0,1)) ) 

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

Я реализовал оба алгоритма: тот, который был отправлен @UriGoren (с небольшим улучшением – только целая математика) и один из @RoryDaulton, на Java. У меня были некоторые проблемы, потому что мой многоугольник закрыт, поэтому оба алгоритма рассматривали второй как вогнутый, когда он был выпуклым. Поэтому я изменил его, чтобы предотвратить такую ​​ситуацию. Мои методы также используют базовый индекс (который может быть или не равен 0).

Это мои тестовые вершины:

 // concave int []x = {0,100,200,200,100,0,0}; int []y = {50,0,50,200,50,200,50}; // convex int []x = {0,100,200,100,0,0}; int []y = {50,0,50,200,200,50}; 

И теперь алгоритмы:

 private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton { final double TWO_PI = 2 * Math.PI; // 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. // needed for any bad points or direction changes // Check for too few points if (n <= 3) return true; if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex n--; // Get starting information int old_x = x[n-2], old_y = y[n-2]; int new_x = x[n-1], new_y = y[n-1]; double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction; double angle_sum = 0.0, orientation=0; // Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon): for (int i = 0; i < n; i++) { // Update point coordinates and side directions, check side length old_x = new_x; old_y = new_y; old_direction = new_direction; int p = base++; new_x = x[p]; new_y = y[p]; new_direction = Math.atan2(new_y - old_y, new_x - old_x); if (old_x == new_x && old_y == new_y) return false; // repeated consecutive points // Calculate & check the normalized direction-change angle double angle = new_direction - old_direction; if (angle <= -Math.PI) angle += TWO_PI; // make it in half-open interval (-Pi, Pi] else if (angle > Math.PI) angle -= TWO_PI; if (i == 0) // if first time through loop, initialize orientation { if (angle == 0.0) return false; orientation = angle > 0 ? 1 : -1; } else // if other time through loop, check orientation is stable if (orientation * angle <= 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 Math.abs(Math.round(angle_sum / TWO_PI)) == 1; } , private boolean isConvex1(int[] x, int[] y, int base, int n) // Rory Daulton { final double TWO_PI = 2 * Math.PI; // 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. // needed for any bad points or direction changes // Check for too few points if (n <= 3) return true; if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex n--; // Get starting information int old_x = x[n-2], old_y = y[n-2]; int new_x = x[n-1], new_y = y[n-1]; double new_direction = Math.atan2(new_y - old_y, new_x - old_x), old_direction; double angle_sum = 0.0, orientation=0; // Check each point (the side ending there, its angle) and accum. angles for ndx, newpoint in enumerate(polygon): for (int i = 0; i < n; i++) { // Update point coordinates and side directions, check side length old_x = new_x; old_y = new_y; old_direction = new_direction; int p = base++; new_x = x[p]; new_y = y[p]; new_direction = Math.atan2(new_y - old_y, new_x - old_x); if (old_x == new_x && old_y == new_y) return false; // repeated consecutive points // Calculate & check the normalized direction-change angle double angle = new_direction - old_direction; if (angle <= -Math.PI) angle += TWO_PI; // make it in half-open interval (-Pi, Pi] else if (angle > Math.PI) angle -= TWO_PI; if (i == 0) // if first time through loop, initialize orientation { if (angle == 0.0) return false; orientation = angle > 0 ? 1 : -1; } else // if other time through loop, check orientation is stable if (orientation * angle <= 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 Math.abs(Math.round(angle_sum / TWO_PI)) == 1; } 

И теперь из Ури-Горена

 private boolean isConvex2(int[] x, int[] y, int base, int n) { if (n < 4) return true; boolean sign = false; if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex n--; for(int p=0; p < n; p++) { int i = base++; int i1 = i+1; if (i1 >= n) i1 = base + i1-n; int i2 = i+2; if (i2 >= n) i2 = base + i2-n; int dx1 = x[i1] - x[i]; int dy1 = y[i1] - y[i]; int dx2 = x[i2] - x[i1]; int dy2 = y[i2] - y[i1]; int crossproduct = dx1*dy2 - dy1*dx2; if (i == base) sign = crossproduct > 0; else if (sign != (crossproduct > 0)) return false; } return true; } , private boolean isConvex2(int[] x, int[] y, int base, int n) { if (n < 4) return true; boolean sign = false; if (x[base] == x[n-1] && y[base] == y[n-1]) // if its a closed polygon, ignore last vertex n--; for(int p=0; p < n; p++) { int i = base++; int i1 = i+1; if (i1 >= n) i1 = base + i1-n; int i2 = i+2; if (i2 >= n) i2 = base + i2-n; int dx1 = x[i1] - x[i]; int dy1 = y[i1] - y[i]; int dx2 = x[i2] - x[i1]; int dy2 = y[i2] - y[i1]; int crossproduct = dx1*dy2 - dy1*dx2; if (i == base) sign = crossproduct > 0; else if (sign != (crossproduct > 0)) return false; } return true; } 

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

Для массива вершин:

 vertices = [(0,0),(1,0),(1,1),(0,1)] 

Следующая реализация python проверяет, имеет ли компонент z всех кросс-продуктов один и тот же знак

 def zCrossProduct(a,b,c): return (a[0]-b[0])*(b[1]-c[1])-(a[1]-b[1])*(b[0]-c[0]) def isConvex(vertices): if len(vertices)<4: return True signs= [zCrossProduct(a,b,c)>0 for a,b,c in zip(vertices[2:],vertices[1:],vertices)] return all(signs) or not any(signs) 

Адаптировал код Uri в matlab. Надеюсь, это поможет.

Имейте в виду, что алгоритм Ури работает только для простых полигонов ! Поэтому, убедитесь, что полигон прост первым!

 % M [ x1 x2 x3 ... % y1 y2 y3 ...] % test if a polygon is convex function ret = isConvex(M) N = size(M,2); if (N<4) ret = 1; return; end x0 = M(1, 1:end); x1 = [x0(2:end), x0(1)]; x2 = [x0(3:end), x0(1:2)]; y0 = M(2, 1:end); y1 = [y0(2:end), y0(1)]; y2 = [y0(3:end), y0(1:2)]; dx1 = x2 - x1; dy1 = y2 - y1; dx2 = x0 - x1; dy2 = y0 - y1; zcrossproduct = dx1 .* dy2 - dy1 .* dx2; % equality allows two consecutive edges to be parallel t1 = sum(zcrossproduct >= 0); t2 = sum(zcrossproduct <= 0); ret = t1 == N || t2 == N; end