Jak skutecznie określić, czy wielokąt jest wypukły, nie wypukły czy złożony?

Możesz sprawić, że rzeczy będą o wiele łatwiejsze niż algorytm Pakowania Prezentów... to dobra odpowiedź, gdy masz zbiór punktów bez żadnej konkretnej granicy i musisz znaleźć wypukły kadłub.

Dla kontrastu, rozważmy przypadek, w którym wielokąt nie jest samo-przecinający się i składa się ze zbioru punktów na liście, gdzie kolejne punkty tworzą granicę. W tym przypadku o wiele łatwiej jest ustalić, czy wielokąt jest wypukły, czy nie (i nie musisz obliczać żadnych kątów, albo): {]}

Dla każdej kolejnej pary krawędzi wielokąta (każdej trójki punktów) Oblicz składową z iloczynu krzyżowego wektorów zdefiniowanych przez krawędzie skierowane ku punktom w rosnącej kolejności. Weźmy iloczyn krzyżowy tych wektorów:

 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

Wielokąt jest wypukły, jeśli składniki z produktów krzyżowych są albo wszystkie dodatnie, albo wszystkie ujemne. W przeciwnym razie wielokąt nie jest wypukły.

Jeśli jest N punktów, upewnij się, że obliczysz N krzyż produkty, np. należy stosować Trójniki (p [N-2],p[N-1],p[0]) I (p[N-1],p[0], p[1]).

Jeśli wielokąt jest samo-przecinający się, to nie spełnia technicznej definicji wypukłości nawet jeśli jego kąty skierowane są w tym samym kierunku, w którym to przypadku powyższe podejście nie przyniosłoby prawidłowego wyniku.

Następująca funkcja/metoda Java jest implementacją algorytmu opisanego w tej odpowiedzi .

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;
}

Algorytm ma gwarancję działania tak długo, jak wierzchołki są uporządkowane (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara) i nie ma przecinających się krawędzi (tzn. działa tylko dla prostych wielokątów ).

To pytanie jest teraz pierwszym elementem w Bing lub Google podczas wyszukiwania "określ wielokąt wypukły."Jednak żadna z odpowiedzi nie jest wystarczająco dobra.

Zaakceptowana odpowiedź przez @ EugeneYokota sprawdza, czy nie uporządkowany zbiór punktów można przekształcić w wielokąt wypukły, ale nie o to prosi OP. Poprosił o metodę sprawdzania, czy dany wielokąt jest wypukły, czy nie. ("Wielokąt" w informatyce jest zwykle definiowany [jak w dokumentacja XFillPolygon ] jako uporządkowana tablica punktów 2D, z kolejnymi punktami połączonymi bokiem, a także ostatnim punktem do pierwszego.) Również algorytm pakowania prezentów w tym przypadku miałby złożoność czasową O(n^2) dla n punktów - która jest znacznie większa niż faktycznie potrzebna do rozwiązania tego problemu, podczas gdy pytanie prosi o skuteczny algorytm.

@odpowiedź Jasona, wraz z innymi odpowiedziami, które podążają za jego pomysłem, akceptuje wielokąty gwiazd takie jak pentagram lub ten w komentarzu @zenna, ale wielokąty gwiazd nie są uważane za wypukłe. Jako @plasmacel notuje w komentarzu, jest to dobre podejście do użycia, jeśli masz wcześniej wiedzę, że wielokąt nie jest samo-przecinający się, ale może się nie udać, jeśli nie masz tej wiedzy.

@odpowiedź Sekhata jest poprawna, ale ma również złożoność czasową O(n^2) i dlatego jest nieefektywna.

@LorenPechtel ' s dodano odpowiedź po jej edycji jest najlepszy tutaj, ale jest niejasny.

Poprawny algorytm o optymalnej złożoności

Algorytm, który tu przedstawiam, ma złożoność czasową O(n), poprawnie sprawdza, czy wielokąt jest wypukły, czy nie, i przechodzi wszystkie testy, które na niego rzuciłem. Chodzi o to, aby trawersować boki wielokąta, zwracając uwagę na kierunek każdej strony i podpisaną zmianę kierunku między kolejnymi bokami. / Align = "left" / dodatnia i prawostronna jest ujemna (lub odwrotna), a prosta jest zerowa. Kąty te są znormalizowane jako między minus-pi (exclusive) i pi (inclusive). sumując wszystkie te kąty zmiany kierunku (a.K.A ugięcie kąty) razem spowoduje plus-minus jeden obrót (tj. 360 stopni) dla wielokąta wypukłego, podczas gdy wielokąt podobny do gwiazdy (lub samo przecinająca się pętla) będzie miał inną sumę (n * 360 stopni, dla N obraca się całkowo, dla wielokątów, gdzie wszystkie kąty ugięcia są tego samego znaku). Musimy więc sprawdzić, czy suma kątów zmiany kierunku jest plus-minus jeden obrót. Sprawdzamy również, czy kąty zmiany kierunku są wszystkie dodatnie lub wszystkie ujemne, a nie odwrotne (radiany pi), wszystkie punkty są rzeczywistymi punktami 2D i że żadne kolejne wierzchołki nie są identyczne. (Ten ostatni punkt jest dyskusyjny-możesz chcieć dopuścić powtarzające się wierzchołki, ale wolę je zakazać.) Połączenie kontrole te obejmują wszystkie wypukłe i nie wypukłe wielokąty.

Oto kod Pythona 3, który implementuje algorytm i zawiera kilka drobnych usprawnień. Kod wygląda na dłuższy niż jest w rzeczywistości ze względu na linie komentarza i księgowość związaną z unikaniem powtarzających się dostępu do punktów.

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

Aby sprawdzić, czy wielokąt jest wypukły, każdy punkt wielokąta powinien być równy z lub za każdą linią.

Oto przykładowe zdjęcie:

Oto test sprawdzający, czy wielokąt jest wypukły.

Rozważmy każdy zbiór trzech punktów wzdłuż wielokąta. Jeśli każdy kąt wynosi 180 stopni lub mniej, masz wielokąt wypukły. Po ustaleniu każdego kąta, również zachować bieg łącznie (180-kąt). Dla wielokąta wypukłego będzie to razem 360.

Ten test przebiega w czasie O (n).

Zauważ również, że w większości przypadków obliczenia te można wykonać raz i zapisać - przez większość czasu masz zestaw wielokątów praca z tym nie zmienia się cały czas.

The answer by @ RoryDaulton wydaje mi się najlepszy, ale co, jeśli jeden z kątów jest dokładnie 0? Niektórzy mogą chcieć, aby taki przypadek na krawędzi zwrócił True, w takim przypadku zmień "

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

Oto moje przypadki testowe, które podkreślają problem:

# 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)) )

Drugie twierdzenie nie powiodło się w oryginalnej odpowiedzi. A powinno? W moim przypadku użytkowania wolałbym, aby nie.

Zaimplementowałem oba algorytmy: ten opublikowany przez @UriGoren (z niewielką poprawką - tylko matematyka całkowita) i ten z @ RoryDaulton, w Javie. Miałem pewne problemy, ponieważ mój wielokąt jest zamknięty, więc oba algorytmy traktowały drugi jako wklęsły, gdy był wypukły. Więc zmieniłem go, aby zapobiec takiej sytuacji. Moje metody również używają indeksu bazowego(który może być lub nie 0).

Oto moje wierzchołki testowe:

// 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};

A teraz algorytmy:

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;
}

A teraz Od Uri Goren

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;
}

Ta metoda działa na prostych wielokątach (bez przecinających się krawędzi) zakładając, że wierzchołki są uporządkowane (zgodnie z ruchem wskazówek zegara lub przeciwnie)

Dla tablicy wierzchołków:

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

Następująca implementacja python sprawdza, czy składnik z wszystkich produktów krzyżowych ma ten sam znak

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)

Zaadaptował Kod Uri do Matlaba. Mam nadzieję, że to pomoże.

Należy pamiętać, że algorytm Uri działa tylko dla proste wielokąty ! Dlatego najpierw sprawdź, czy wielokąt jest prosty!

% 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