Comments 13
Для первого раза может, и неплохо. Я бы разбавил код простыми оптимизациями:
// всë начинается со структуры
int n;
Point vertices [];Тогда память нужно выделять один раз, а не дважды.
// в цикле обхода вершин
a = vertices[i];
//... вычисления
c = b;
b = а;Код короче и быстре.
Смысл приводить код в статье дважды?
Большие числа обработать отдельно, если они есть. И ещë много чего найти можно. Заметил, что LLMка часто так пишет, не особо задумываясь.
Спасибо за обратную связь!
Вы правы, такие оптимизации возможны. Однако в данном случае они несколько усложняют код и делают его менее очевидным для новичков. У меня была цель показать решение максимально понятно, поэтому я сознательно сделал выбор в пользу читаемости.
Что касается LLM — да, они часто генерируют шаблонные решения, но не всегда учитывают такие вещи, как контроль переполнения, корректная работа с памятью и обработка ошибок. В этом коде я как раз старался эти моменты проработать.
В любом случае, спасибо за замечания — есть над чем подумать и что улучшить.
Хм, я новичёк в этом деле, но нельзя ли за счёт упрощения обьектов до простых геометрических форм и данной функции определять их структурную целостность, например ?
Хороший вопрос, спасибо!
На практике сложные формы действительно часто разбиваются на более простые, потому что с ними проще работать. В этом контексте проверка выпуклости полезна — она позволяет понять, является ли фигура уже «простой» или её стоит дальше разбивать.
Но важно, что данная функция отвечает только на вопрос выпуклости и не проверяет структурную целостность фигуры в целом. Для этого нужны дополнительные проверки: самопересечения, корректный порядок вершин и другие случаи.
Так что это скорее часть решения, а не универсальный инструмент. Возможно, в следующих материалах разберу эти проверки подробнее.
# загрузка переменных
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-инструкциях: параллельное вычисление разницы координат и их произведения...
Хороший вариант, спасибо.
Действительно, через SIMD можно ускорить такие вычисления. Однако в рамках данной задачи операции выполняются последовательно для троек точек, и основное время уходит скорее на обход вершин, чем на сами арифметические вычисления. В этом контексте выигрыш от SIMD будет ограниченным.
Кроме того, переход на float может привести к потере точности, что критично для геометрических задач — особенно в случаях, когда определяется знак поворота при значениях, близких к нулю.
Также SIMD-реализация заметно усложняет код и снижает его читаемость, тогда как цель статьи — показать базовый и понятный алгоритм.
Тем не менее, для высоконагруженных сценариев такой подход вполне оправдан.
Это у меня в телефоне браузер глючит или на самом деле последний спойлер ("подводные камни") дублирует последние абзацы.
Операция % не бесплатная. Хвостик можно обработать вне цикла. И вы дважды считаете одни и те-же разницы. Их можно считать один раз, а потом определять знак угла между векторами разницы развернув цикл на пары
Да, операция % действительно не бесплатная, и в более оптимизированной реализации хвост следует вынести из цикла, чтобы избежать лишних вычислений.
Также вы правы, что разности координат сейчас пересчитываются несколько раз. Это можно оптимизировать, если заранее работать с векторами рёбер и затем проверять знак угла между соседними рёбрами.
В рамках данной статьи я сознательно выбрал более прямолинейный вариант, чтобы не усложнять восприятие и сохранить связь с геометрическим объяснением (через тройки точек).
Текущая реализация защиты от переполнения просто выводит 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)
}Спасибо за такой подробный разбор.
Вы правы, текущая реализация с проверкой переполнения — это в первую очередь защитный механизм, а не способ сохранить корректность вычислений в общем случае. Предложенные вами варианты действительно позволяют получить более точный и строгий результат без риска переполнения.
В рамках статьи я сознательно выбрал более простой и наглядный подход, чтобы не перегружать материал деталями, которые выходят за пределы базового алгоритма.
Как определить выпуклость многоугольника на C: от геометрии к коду