2

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

bool convex(point *poligon_)
{
    double k = ((double)poligon_[3].y - poligon_[1].y) / (poligon_[3].x - poligon_[1].x);
    double a = poligon_[1].y - k*poligon_[1].x;
    double s1, s2;
    for (int i = poligon_[1].x; i <= poligon_[3].x; i += 0.001)
    {
        int y2 = k*i + a;
        s1 = (y2 - poligon_[3].y)*(i - poligon_[1].x);
        s2 = (poligon_[1].y - y2)*(poligon_[3].x - i);
        cout<< s1<<' '<< s2<<endl;

    }
    return true;
}

Разумеется не сработало, многоугольник задаю таким образом:

struct polygon {
    size_t size_polygon;
    point poligon_[];

    polygon()
    {
        while (true)
        {
            cout << "Пожалуйста введите количество вершин прямоугольника:" << endl;
            size_polygon = input_double(">>>");

            if (size_polygon < 3) continue;

            for (int i = 1; i < size_polygon +1; i++)
            {
                cout << "Координаты " << i << " точки"<<endl;
                poligon_[i].x = input_double("Введите координату x:" );
                poligon_[i].y = input_double("Введите координату y: ");
            }

            bool success = convex(poligon_);

            break;
        }
    }
};

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

4
  • 3
    Что тут думать-то? Обходите границу полигона, вектора-сегменты соседних отрезков должны все время поворачивать в одну сторону. Не забудьте проверить вектор, соединяющий последнюю точку с первой.
    – user176262
    15 ноя 2017 в 15:20
  • А чтобы проверить, в ту же сторону или нет, нужно проверить знаки псевдоскалярного произведения соседних сторон.
    – VladD
    15 ноя 2017 в 15:28
  • Ответы по вычисленю углов между векторами даны, только разберитесь, подходят ли под вашу задачу мнгогоугольники с пересечениями, например, такой пятиугольник как пятиконечная звезда.
    – Alex Titov
    15 ноя 2017 в 16:26
  • Не понятно. Что значит обходить направо, налево? Если векторы это стороны многоугольника, то где начало и где считать конец вектора? Например, имеем квадрат(многоугольник) ABCD. Правильно ли я понимаю, что если обходим по часовой стрелке, то сначала делаем вычисления , например, для точки A, потом B, потом С, и, наконец ,D. Для точки А вектора будут AD и AB, соответственно. И координаты , для выражения Х1*У2-Х2*У1, будут, соответственно, не начала, а концы векторов: Х1,У1 это точка D, а Х2,У2, точка В? Практическое вычисление показало, что у двух соседних углов знак разный. 3 авг в 5:34

2 ответа 2

6

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

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

AB.x * BC.y - AB.y * BC.x

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

Это дает нам алгоритм определения выпуклости. Для каждой вершины i нам надо вычислить

point ab = 
{ 
  poligon_[i].x - poligon_[i - 1].x, 
  poligon_[i].y - poligon_[i - 1].y
};

point bc = 
{ 
  poligon_[i + 1].x - poligon_[i].x, 
  poligon_[i + 1].y - poligon_[i].y
};

double product = ab.x * bc.y - ab.y * bc.x;

(Разумеется, надо быть аккуратным при вычислении индексов соседних точек i - 1 и i + 1 на краях массива)

По поведению знака величины product на всех вершинах многоугольника мы и получим ответ на наш вопрос о выпуклости.

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

Если направление обхода заранее неизвестно, то придется проверить все вершины и убедиться, что знаки величины product везде одинаковы (и не забыть аккуратно обработать нулевое значение).

1

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

Это означает, что у векторного произведения этих векторов координаты z должны быть одного знака.

Не забудьте проверить вектор, соединяющий последнюю точку с первой.

P.S.

Пожалуйста введите количество вершин прямоугольника:

сюда я добавил бы список допустимых значений :).