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

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

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

Этот тест выполняется за время O (n).

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

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

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

Для каждой последовательной пары ребер многоугольника (каждой тройки точек) вычислите 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], p [0], p [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;
}

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

Адаптировал код Ури в 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

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

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

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)

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

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

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

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

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

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

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

Вот код для 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

ответ @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 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;
}