Зачем вообще определять, выпуклый ли многоугольник?
На практике это встречается гораздо чаще, чем кажется.
В разработке игр многоугольники используются для хитбоксов, зон урона и физики. При этом выпуклые фигуры обрабатывать проще и быстрее, поэтому сложные формы часто разбивают на набор выпуклых.
Похожая ситуация возникает в навигации (например, при построении маршрутов), робототехнике (проверка препятствий) и компьютерной графике. Во всех этих задачах работа с выпуклыми многоугольниками значительно упрощает алгоритмы.
Теперь перейдём к самой задаче и разберёмся, как это реализовать.
Итак, представим, что мы обходим вершины многоугольника по порядку. На каждом шаге мы совершаем поворот - либо влево, либо вправо.
Если все повороты происходят в одну и ту же сторону, многоугольник выпуклый (Convex).
Если направление хотя бы один раз меняется - он невыпуклый (Concave).
Таким образом, задача сводится к определению направления поворота для каждой тройки соседних точек.
Почему именно 3 точки?
Возникает логичный вопрос: почему мы рассматриваем именно тройки точек, а не, например, пары?
На самом деле все довольно просто. Так как две точки задают только отрезок, то по ним нельзя понять, куда происходит поворот.
А вот три точки уже образуют «угол» в вершине, и именно он определяет направление: влево или вправо.
Фактически мы рассматриваем два последовательных ребра многоугольника:
AB и BC.
И проверяем, как одно ребро поворачивается относительно другого.
Поэтому минимальный набор, позволяющий определить направление, - это три точки.
Иначе говоря, нас интересует не сами точки, а переход от одного ребра к следующему. И этот переход можно о��исать только через три вершины: начало, текущую точку и следующую за ней.
Допустим теперь у нас есть 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 → точки лежат на одной прямой
Откуда берется эта формула?
На самом деле это запись векторного произведения в координатах.
Если рассмотреть два вектора:
AB = (x₂ - x₁, y₂ - y₁)
AC = (x₃ - x₁, y₃ - y₁)
то выражение
(x₂ - x₁) (y₃ - y₁) - (y₂ - y₁) (x₃ - x₁)
равно ориентированной площади параллелограмма, построенного на этих векторах.
Важно не само значение, а его знак:
положительный → поворот в одну сторону
отрицательный → в другую
ноль → векторы лежат на одной прямой
Таким образом, эта формула позволяет определить направление поворота, что и нужно для проверки выпуклости.
Интуитивно это можно представить так: мы сравниваем, «поднимается» ли точка C относительно направления от A к B, или «опускается». Именно эта разница и зашита в формуле.
На самом деле нас интерисует не столько значение, сколько ее знак!
Теперь, когда стало понятно откуда берется формула, приступим к реализации. Но перед этим стоит учтонить о том, что каждая вершина многоугольника хранилась в виде структуры:
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).
Мой вариант избегания Overflow
Один из способов избежать переполнения — явно контролировать операции умножения.
Для этого можно реализовать вспомогательную функцию, которая проверяет, не выйдет ли результат за пределы типа long long:
#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("OVERFLOW\n"); return 0; } return p1 - p2; }
В текущей реализации при переполнении функция возвращает 0. Однако это значение также используется для обозначения коллинеарности.
В более строгой реализации такую ситуацию стоило бы обрабатывать отдельно (например, через дополнительный флаг ошибки или изменение сигнатуры функции).
Теперь, когда у нас есть функция для определения направления поворота, можно перейти к основной задаче - проверке выпуклости многоугольника.
Для начала, помимо структуры точки, нам нужно описать сам многоугольник. Опишем многоугольник при помощи вершин и их количества:
typedef struct { Point *vertices; int n; } Polygon;
Обьяснение структуы
Здесь:
vertices- указатель на массив точек (вершин многоугольника)n- количество вершин
Такое представление удобно, так как позволяет работать с многоугольниками произвольного размера. Важно, что память под массив вершин выделяется динамически, так как количество точек известно только во время выполнения программы.
Вернемся обратно к реализации программы. Как мы уже обсуждали ранее, выпуклый многоугольник характеризуется тем, что при обходе его вершин все повороты происходят в одну сторону.
Таким образом, алгоритм сводится к трём шагам:
пройти по всем тройкам соседних точек
вычислить для каждой значение
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; }
Обьяснение алгоритма
Разберём, как работает этот алгоритм.
Переменная sign фиксирует первое найденное направление поворота и служит эталоном для всех последующих.
Сначала sign = 0, так как мы ещё не встретили ни одного ненулевого поворота.
При обходе вершин:
- если cross == 0, точки лежат на одной прямой, и такой случай можно пропустить
- если sign == 0, мы запоминаем знак первого ненулевого поворота
- если знак текущего поворота отличается от сохранённого — многоугольник невыпуклый
Обратите внимание, что значения cross == 0 игнорируются. Это позволяет корректно обрабатывать случаи, когда несколько точек лежат на одной прямой.
Также следует заметить, что использование операции % p->n позволяет корректно «замкнуть» многоугольник и рассматривать последние вершины вместе с первыми.
Переполнение так же в реализации данной функции невозможно, так как нет прямого умножения сравнение происходит без умножения cross * sign.
Алгоритм выше проверяет, сохраняется ли направление поворота на всём протяжении обхода многоугольника. Если это условие выполняется, многоугольник является выпуклым.
Теперь, когда все геометрические функции реализованы, посмотрим на результат программы.
Функции по созданию многоугольника и его удалению
Для полноты картины стоит также показать, как создаётся и освобождается многоугольник.
Так как количество вершин известно только во время выполнения, память под них выделяется динамически:
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("OVERFLOW\n"); 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 ERROR\n"); return 1; } Polygon *p = CreatePolygon(n); if (!p) { printf("MEMORY ERROR\n"); return 1; } if (!ReadPolygon(p)) { printf("INPUT ERROR\n"); DestroyPolygon(p); return 1; } if (IsConvex(p)) printf("CONVEX\n"); else printf("NOT CONVEX\n"); DestroyPolygon(p); return 0; } int main() { return AnalyzePolygon(); }
Последнее о чем я хотел бы вам рассказать, это подводные камни.
В итоге, задача, которая на первый взгляд кажется сложной, сводится к простой проверке знака выражения.
Однако, как мы увидели, даже в таком базовом алгоритме есть нюансы, которые важно учитывать на практике.
В следующей части мы более подробно рассмотрим более сложный случай - проверку самопересечения и работу с произвольными наборами точек.
Комментарии (13)
Kinemato
22.03.2026 11:31Хм, я новичёк в этом деле, но нельзя ли за счёт упрощения обьектов до простых геометрических форм и данной функции определять их структурную целостность, например ?
Verse23 Автор
22.03.2026 11:31Хороший вопрос, спасибо!
На практике сложные формы действительно часто разбиваются на более простые, потому что с ними проще работать. В этом контексте проверка выпуклости полезна — она позволяет понять, является ли фигура уже «простой» или её стоит дальше разбивать.
Но важно, что данная функция отвечает только на вопрос выпуклости и не проверяет структурную целостность фигуры в целом. Для этого нужны дополнительные проверки: самопересечения, корректный порядок вершин и другие случаи.
Так что это скорее часть решения, а не универсальный инструмент. Возможно, в следующих материалах разберу эти проверки подробнее.
Alex283
22.03.2026 11:31# загрузка переменных movups xmm0, [rip + pointA] movups xmm1, [rip + pointB] movups xmm2, [rip + pointC] # вычисление по формуле subps xmm1, xmm0 subps xmm3, xmm0 pshufd xmm3, xmm3, 0x01 mulps xmm3, xmm2 hsubps xmm3, xmm3 # формирование возвращаемого результата # 0 - нулевой результат # 1 - положительный # 2 - отрицательный pxor xmm0, xmm0 pcmpeqd xmm0, xmm3 pmovmskb rax, xmm0 and al, 0x0F cmp al, 0x0F je 1f pmovmskb rax, xmm3 shr al, 3 inc al 1: movzx rax, al retЕсли представить координаты во float, то вычисления по формуле лучше реализовать на SIMD-инструкциях: параллельное вычисление разницы координат и их произведения...
Verse23 Автор
22.03.2026 11:31Хороший вариант, спасибо.
Действительно, через SIMD можно ускорить такие вычисления. Однако в рамках данной задачи операции выполняются последовательно для троек точек, и основное время уходит скорее на обход вершин, чем на сами арифметические вычисления. В этом контексте выигрыш от SIMD будет ограниченным.
Кроме того, переход на float может привести к потере точности, что критично для геометрических задач — особенно в случаях, когда определяется знак поворота при значениях, близких к нулю.
Также SIMD-реализация заметно усложняет код и снижает его читаемость, тогда как цель статьи — показать базовый и понятный алгоритм.
Тем не менее, для высоконагруженных сценариев такой подход вполне оправдан.
void-deref
22.03.2026 11:31Это у меня в телефоне браузер глючит или на самом деле последний спойлер ("подводные камни") дублирует последние абзацы.
Sdima1357
22.03.2026 11:31Операция % не бесплатная. Хвостик можно обработать вне цикла. И вы дважды считаете одни и те-же разницы. Их можно считать один раз, а потом определять знак угла между векторами разницы развернув цикл на пары
Verse23 Автор
22.03.2026 11:31Да, операция % действительно не бесплатная, и в более оптимизированной реализации хвост следует вынести из цикла, чтобы избежать лишних вычислений.
Также вы правы, что разности координат сейчас пересчитываются несколько раз. Это можно оптимизировать, если заранее работать с векторами рёбер и затем проверять знак угла между соседними рёбрами.
В рамках данной статьи я сознательно выбрал более прямолинейный вариант, чтобы не усложнять восприятие и сохранить связь с геометрическим объяснением (через тройки точек).
Sdima1357
22.03.2026 11:31Правда компиляторы уже достаточно умные, чтобы сделать все правильно в таких несложных случаях, а в компе доступ к памяти дороже вычислений .. Я просто очень старый и поэтому ворчу по привычке :)
wataru
22.03.2026 11:31Текущая реализация защиты от переполнения просто выводит overflow и возможно выдает неправильный результат, если умножение переполняется. Но не обязательно это делать, можно выдать корректный результат.
Вот вам надо проверить, что a*b >= c*d, т.е. знак у векторного произведения отрицательный. a,b,c,d в 64 бита помещаются.
Можно все еще достоверно проверить условие без переполнения.
Во-первых, можно реализовать простую длинную арифметику. Пусть ваше произведение возвращает пару int64 чисел - составляющих 128 битное число.
Так:
uint64_t al = a & 0xFFFFFFFF; uint64_t ar = a >> 32; uint64_t bl = b & 0xFFFFFFFF; uint64_t br = b >> 32; uint64_t resh = ar*br; uint64_t resl = al*bl; uint64_t resm1 = ar*bl; uint64_t resm2 = al*br; resl += resm1 >> 32 + resm2 >> 32; resm1 = (resm1 & 0xFFFFFFFF) << 32; resm2 = (resm2 & 0xFFFFFFFF) << 32; if (resm1 > std::numeric_limits<uint64_t>::max() - resl) { ++resh; } resl += resm1; if (resm2 > std::numeric_limits<uint64_t>::max() - resl) { ++resh; resl += resm2; return {resh, resl};В ассемблере это вообще можно вылизать со флагами переноса и половинами регистров.
Эту пару можно сравнивать потом. Только отдельно знаки сначала проверьте.
С другой стороны, есть еще красивое решение без длинной арифметики.
Вот надо вам проверить a*b <= c*d. Допустим нулей и отрицательных чисел нет, знаки и нули вы отдельно сначала проверили. Тогда можно переписать a/c <= d/b. Тут можно сравнить целые части от делений. Если они разные - можно сразу решить какой там знак в соотношении. Если же целые части совпали, их можно вычесть: a%c/c <= d%b/b.
А теперь трюк: перевернем дроби. И уже надо проверить c / a%c >= b/ d%b. Тут опять рекурсивно сравниваем целые части, вычитаем если совпало, переворачиваем и так далее. Это фактически 2 параллельных алгоритма эвклида, они за log (M) шагов получат в числителе 0, после чего можно сразу сказать, что там больше чего.
Т.е. у вас рекурсивная функция, которая сначала проверяет на нули в числителях, потом целые части, потом берет остатки, переворачивает дроби и рекурсивно вызывает себя, возвращая обратный результат.
// a*b <=> c*d int Compare(int a, int b, int c, int d) { if (b == 0 && c == 0) return 0; if (b == 0) return 1; if (c == 0) return -1; int l = a/c; int r = d/b; if (l < r) return 1; if (l > r) return -1; return -Compare(c, d%b, a%c, b) }Verse23 Автор
22.03.2026 11:31Спасибо за такой подробный разбор.
Вы правы, текущая реализация с проверкой переполнения — это в первую очередь защитный механизм, а не способ сохранить корректность вычислений в общем случае. Предложенные вами варианты действительно позволяют получить более точный и строгий результат без риска переполнения.
В рамках статьи я сознательно выбрал более простой и наглядный подход, чтобы не перегружать материал деталями, которые выходят за пределы базового алгоритма.
alcotel
Для первого раза может, и неплохо. Я бы разбавил код простыми оптимизациями:
Тогда память нужно выделять один раз, а не дважды.
Код короче и быстре.
Смысл приводить код в статье дважды?
Большие числа обработать отдельно, если они есть. И ещë много чего найти можно. Заметил, что LLMка часто так пишет, не особо задумываясь.
Verse23 Автор
Спасибо за обратную связь!
Вы правы, такие оптимизации возможны. Однако в данном случае они несколько усложняют код и делают его менее очевидным для новичков. У меня была цель показать решение максимально понятно, поэтому я сознательно сделал выбор в пользу читаемости.
Что касается LLM — да, они часто генерируют шаблонные решения, но не всегда учитывают такие вещи, как контроль переполнения, корректная работа с памятью и обработка ошибок. В этом коде я как раз старался эти моменты проработать.
В любом случае, спасибо за замечания — есть над чем подумать и что улучшить.