Как определить тип полигона

Question

Пользователь вводит n-ые точки. Мне нужно проверить, существует ли многоугольник, а затем определить тип - вогнутый или выпуклый многоугольник. Я знаю, что многоугольник выпуклый, если каждый его угол находится под углом 180 градусов. Таким образом, проблема сводится к поиску каждого внутреннего угла многоугольника. Я искал формулу или алгоритм, но без успеха.

Пример:

Входной сигнал: п = 4;

Point1: (5; 6)

Point2: (4; -5)

Point3: (-5; 4)

Point4: (-5; 5)

Ожидаемый результат: многоугольник выпуклый

Это код до сих пор: Ri ght теперь он находит только максимальное и минимальное расстояние между точками плоскости.

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

int main() 
{ 
    double a[15][2]; 
    int n; 
    cin >> n; 
    if (n <= 0 && n > 15) 
     return 1; 

    for (int i = 0; i < n; i++) 
    { 
     cout << "x" << i << " = , y" << i << " = "; 
     cin >> a[i][0] >> a[i][1]; 
    } 

    double maxDistance = 0.0; 
    double minDistance = 0.0; 
    double maxpoint1[2]; 
    double maxpoint2[2]; 
    double minpoint1[2]; 
    double minpoint2[2]; 

    for (int i = 0; i < n; i++) 
    { 
     for (int j = 0; j < n; j++) 
     { 
      if (j != i) 
      { 
       double x1 = a[i][0]; 
       double x2 = a[j][0]; 
       double y1 = a[i][1]; 
       double y2 = a[j][1]; 
       double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); 

       if (currentDistance > maxDistance) 
       { 
        maxDistance = currentDistance; 
        maxpoint1[0] = x1; 
        maxpoint1[1] = y1; 
        maxpoint2[0] = x2; 
        maxpoint2[1] = y2; 

       } 

       if (minDistance > currentDistance) 
       { 
        currentDistance = minDistance; 
        minpoint1[0] = x1; 
        minpoint1[1] = y1; 
        minpoint2[0] = x2; 
        minpoint2[1] = y2; 
       } 

       cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2; 
       cout << endl << "Distance is " << currentDistance; 
       cout << endl; 
      } 
     } 
    } 

    cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1]; 
    cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1]; 


    return 0; 
} 

Answer 1

Чтобы найти, если многоугольник выпуклый или вогнутый, просто проверить признаки перекрестных продуктов для всех последовательных точек троек CrossProduct(P[0], P[1], P[2]) etc. В качестве примера

CrossProductSign(A, B, C) = 
       SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X)) 

Для выпуклых, все поперечные продукты должны иметь один и тот же знак (+ или -).

Как это работает: для выпуклого полигона каждый триплет превращается в ту же сторону (или CW, или CCW в зависимости от направления ходьбы). Для вогнутых некоторые знаки будут отличаться (где внутренний угол превышает 180 градусов). Обратите внимание, что вам не нужно вычислять значения угла.

Answer 2

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

a dot b = | a || b | сов (angle_between_vectors) = а [0] * б [0] + а [1] * б [1] + а [2] * б [2]

внутренний угол будет (пи - angle_between_vectors)

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

Это не единственный способ определить, является ли многоугольник выпуклым и, вероятно, одним из самых богатых вычислений? Проблема с точечным продуктом заключается в том, что его знак будет показывать, если угол меньше или больше, чем pi/2. Правильный способ определить, не является ли ваш многоугольник сложным или невыпуклым, проверить, изменилось ли направление поворота. Для этого вам понадобится перекрестный продукт. Для 2d векторов результат их перекрестного произведения получил только z-компонент (перпендикулярно плоскости), его знак определяет, каким образом происходит поворот.

Вопрос был здесь уже.

How do determine if a polygon is complex/convex/nonconvex?