Как определить выпуклость многоугольника на C: от геометрии к коду

Зачем вообще определять, выпуклый ли многоугольник?

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

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

Теперь перейдём к самой задаче и разберёмся, как это реализовать.

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

Если все повороты происходят в одну и ту же сторону, многоугольник выпуклый (Convex).
Если направление хотя бы один раз меняется - он невыпуклый (Concave).

Таким образом, задача сводится к определению направления поворота для каждой тройки соседних точек.

Допустим теперь у нас есть 3 точки: A(x₁, y₁), B(x₂, y₂), C(x₃, y₃)

Тогда вычисляется значение:

cross = (x₂ - x₁) * (y₃ - y₁) - (y₂ - y₁) * (x₃ - x₁)

Интерпретация результата:

- cross > 0 → поворот влево
- cross < 0 → поворот вправо
- cross = 0 → точки лежат на одной прямой

На самом деле нас интерисует не столько значение, сколько ее знак!

Теперь, когда стало понятно откуда берется формула, приступим к реализации. Но перед этим стоит учтонить о том, что каждая вершина многоугольника хранилась в виде структуры:

typedef struct
{
    int x;
    int y;
} Point;

Приступим к первой функции. Я назвал ее Orient (от слова Orientation):

long long Orient(Point a, Point b, Point c)
{
    return (long long)(b.x - a.x) * (c.y - a.y) -
           (long long)(b.y - a.y) * (c.x - a.x);
}

Можно заметить, что я просто перенес формулу, которую писал выше в код. Тут стоит обратить на используемый тип данных

Для вычислений используется тип long long, так как в формуле участвуют умножения координат. Даже при относительно небольших значениях (например, порядка 10⁵) результат может выйти за пределы типа int.

Использование long long позволяет избежать переполнения в большинстве практических случаев и корректно вычислять знак выражения.

Отдельно стоит отметить проблему переполнения.

На данном этапе мы не следим за переполнением. Да, к сожалению, long longтоже имеет свойство переполняться. На практике это встречается редко, обычно достаточно использование 64-битного типа. При необходимости можно использовать более широкий тип (например, __int128).

#include <limits.h>

int SafeMul(long long a, long long b, long long *res)
{
    if (a > 0 && b > 0 && a > LLONG_MAX / b) 
    {
        return 0;
    }
    if (a > 0 && b < 0 && b < LLONG_MIN / a) 
    {
        return 0;
    }
    if (a < 0 && b > 0 && a < LLONG_MIN / b) 
    {
        return 0;
    }
    if (a < 0 && b < 0 && a < LLONG_MAX / b) 
    {
        return 0;
    }

    *res = a * b;
    return 1;
}

long long Orient(Point a, Point b, Point c)
{
    long long p1, p2;

    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2))
    {
        printf("OVERFLOWn");
        return 0;
    }

    return p1 - p2;
}

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

Для начала, помимо структуры точки, нам нужно описать сам многоугольник. Опишем многоугольник при помощи вершин и их количества:

typedef struct 
{
    Point *vertices;
    int n;
} Polygon;

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

Таким образом, алгоритм сводится к трём шагам:

• пройти по всем тройкам соседних точек

• вычислить для каждой значение cross

• проверить, меняется ли его знак

Реализуем это в виде следующей функции:

int IsConvex(const Polygon *p)
{
    int sign = 0;

    for (int i = 0; i < p->n; i++)
    {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];

        long long cross = Orient(a, b, c);

        if (cross == 0)
            continue;

        if (sign == 0)
            sign = (cross > 0) ? 1 : -1; // 
        else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0))
            return 0;
    }

    return 1;
}

Алгоритм выше проверяет, сохраняется ли направление поворота на всём протяжении обхода многоугольника. Если это условие выполняется, многоугольник является выпуклым.

Теперь, когда все геометрические функции реализованы, посмотрим на результат программы.

Polygon *CreatePolygon(int n)
{
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;

    p->n = n;
    p->vertices = malloc(n * sizeof(Point));

    if (!p->vertices)
    {
        free(p);
        return NULL;
    }

    return p;
}

void DestroyPolygon(Polygon *p)
{
    if (!p) return;
    free(p->vertices);
    free(p);
}

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct
{
    int x;
    int y;
} Point;

typedef struct
{
    Point *vertices;
    int n;
} Polygon;

// Проверка умножения на переполнение
int SafeMul(long long a, long long b, long long *res)
{
    if (a > 0 && b > 0 && a > LLONG_MAX / b) return 0;
    if (a > 0 && b < 0 && b < LLONG_MIN / a) return 0;
    if (a < 0 && b > 0 && a < LLONG_MIN / b) return 0;
    if (a < 0 && b < 0 && a < LLONG_MAX / b) return 0;

    *res = a * b;
    return 1;
}

// Ориентация трёх точек
long long Orient(Point a, Point b, Point c)
{
    long long p1, p2;

    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2))
    {
        printf("OVERFLOWn");
        exit(1);
    }

    return p1 - p2;
}

// Проверка выпуклости
int IsConvex(const Polygon *p)
{
    int sign = 0;

    for (int i = 0; i < p->n; i++)
    {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];

        long long cross = Orient(a, b, c);

        if (cross == 0)
            continue;

        if (sign == 0)
            sign = (cross > 0) ? 1 : -1;
        else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0))
            return 0;
    }

    return 1;
}

// Создание многоугольника
Polygon *CreatePolygon(int n)
{
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;

    p->n = n;
    p->vertices = malloc(n * sizeof(Point));

    if (!p->vertices)
    {
        free(p);
        return NULL;
    }

    return p;
}

// Освобождение памяти
void DestroyPolygon(Polygon *p)
{
    if (!p) return;
    free(p->vertices);
    free(p);
}

// Чтение вершин
int ReadPolygon(Polygon *p)
{
    for (int i = 0; i < p->n; i++)
    {
        if (scanf("%d %d", &p->vertices[i].x, &p->vertices[i].y) != 2)
            return 0;
    }
    return 1;
}

// Логика Анализа многоугольника
int AnalyzePolygon()
{
    int n;

    if (scanf("%d", &n) != 1 || n < 3)
    {
        printf("INPUT ERRORn");
        return 1;
    }

    Polygon *p = CreatePolygon(n);
    if (!p)
    {
        printf("MEMORY ERRORn");
        return 1;
    }

    if (!ReadPolygon(p))
    {
        printf("INPUT ERRORn");
        DestroyPolygon(p);
        return 1;
    }

    if (IsConvex(p))
        printf("CONVEXn");
    else
        printf("NOT CONVEXn");

    DestroyPolygon(p);
    return 0;
}

int main()
{
    return AnalyzePolygon();
}

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

В итоге, задача, которая на первый взгляд кажется сложной, сводится к простой проверке знака выражения.

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

В следующей части мы более подробно рассмотрим более сложный случай - проверку самопересечения и работу с произвольными наборами точек.