Когда не нужна тригонометрия

    Просматривая различный код по выводу на экран какой-нибудь даже примитивной графики, я заметил чрезмерную любовь некоторых программистов к тригонометрии. Часто код пестрит синусами, косинусами и арктангенсами там, где без них можно обойтись. Этим грешат даже хорошие программисты, которые способны спроектировать сложную систему, но почему-то не освоили вектора в объёме школьной программы. Буквально азов векторной алгебры хватает для решения многих насущных проблем. В этом топике я хочу провести краткий ликбез, напомнить основные действия с векторами на плоскости и в качестве примера решить две задачи без тригонометрии: поиск отражённого луча по падающему лучу и произвольно расположенному зеркалу, а также рисование наконечника стрелки. Если вы можете представить в голове рисование произвольно направленной стрелки без синусов и косинусов, смело пропускайте этот топик. Для остальных постараюсь объяснять попроще.

    Теория

    Итак, вектором (рассматриваем только двумерный случай) называется пара чисел:

    Геометрический смысл — это отрезок на плоскости, для которого важна длина и направление, но не важно положение. То есть параллельный перенос не меняет вектора. Часто полезно отождествлять вектор с точкой (x,y) на плоскости — это всё равно что провести вектор из точки (0,0) в точку (x,y). Рассмотрим основные операции.
    Сложение векторов:

    Геометрический смысл изображён на картинке — мы перемещаем второй вектор, чтобы его начало совпало с концом первого, и результатом считаем вектор от начала первого до конца второго:

    Умножение вектора на скаляр (число):

    Геометрический смысл — удлинение вектора в соответствующее число раз, не меняя направление (разве что на противоположное, если a отрицательно). Умножение на -1 перевернёт вектор на 180°, не меняя длину. Деление вектора на число a — это умножение на 1/a.
    Скалярное произведение векторов:

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

    Вектор называют нормированным или единичным, если его длина равна единице. Нормировать произвольный ненулевой вектор — это поделить его на длину. Получится единичный вектор, сонаправленный исходному.
    Скалярное произведение произвольного вектора на единичный даст точную длину проекции этого вектора на направление единичного. Чтобы получить не просто длину, а сам вектор-проекцию, надо умножить эту длину на наш единичный вектор:

    В скобках скалярное произведение векторов a и e, а затем умножение вектора e на скаляр.
    Что делать, если нам нужна проекция на ненормированный вектор? Чтобы нормировать, надо извлечь корень, а это долго и грустно. Однако, если мы приглядимся к формуле, то поймём, что нам нужно поделить результат на квадрат длины, то есть просто на скалярное произведение вектора на себя. То есть проекция a на произвольный ненулевой b будет вычисляться так:

    Скалярное произведение двух единичных векторов — это косинус угла между ними. Если вдруг вам всё-таки потребовался угол между направлениями, проверьте, может, вам вовсе не угол нужен, а его косинус (или синус, который в ряде случаев можно получить из основного тригонометрического тождества). Тогда вам не потребуется ковыряться с арктангенсами.
    Вот, собственно, вся базовая теория. Теперь попробуем её применить.

    Вычисление отражённого луча

    Отражённый луч может пригодиться не только для оптических задач, а ещё, скажем, при моделировании упругого столкновения объекта со стенкой, что незаменимо при программировании анимированных красивостей. Тогда вектор скорости объекта изменится как раз по закону отражения. Итак, у нас есть падающий вектор l и некоторая произвольная прямая, от которой производится отражение. Прямая может быть задана, к примеру, двумя точками. Требуется определить отражённый вектор r той же длины, что и l:

    Зная, что угол падения равен углу отражения, можно придумать какой-то такой наивный алгоритм:
    • Посчитать разность координат точек прямой, взять арктангенс их отношения — получим наклон прямой к оси x.
    • Аналогично определить наклон падающего луча к оси x.
    • Посчитать разность этих углов, вычесть её из 90° — получим угол падения.
    • Добавить угол падения дважды и ещё 180° к углу наклона падающего луча — получим угол наклона отражённого луча.
    • Вычислить длину падающего луча и умножить на синус и косинус угла наклона отражённого луча — получим результирующий вектор.
    Итого: два арктангенса, синус, косинус и квадратный корень.
    Однако если мыслить векторами, то простое геометрическое построение даёт существенно более быстрое решение:

    Две проекции вектора l на нормаль со знаком минус да плюс ещё один вектор l в точности дадут нам результат:

    Делить не надо, если нормаль уже нормирована. Кстати, я не рассказал, как её определить. Если прямая задана двумя точками (x1,y1) и (x2,y2), то вектор нормали (ненормированый) легко определяется вот так:

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

    Рисование стрелки

    Пусть заданы концы стрелки (x1,y1) и (x2,y2). Надо нарисовать усики фиксированного размера на конце (x2,y2). Посмотрим рисунок:

    Здесь точка (x2,y2) обозначена буквой P. Необходимо вычислить координаты точек A и B, чтобы провести отрезки PA и PB. Будем считать, что нам задана продольная и поперечная длины усиков h и w. Внимательный читатель уже может сам предложить алгоритм: чтобы найти точку O, надо вычесть из P h, умноженное на единичный вектор вдоль стрелки (тут, похоже, без корня не обойтись, но он нужен всего один раз!). А затем A и B уже определяются, добавляя к O вектор нормали, домноженный на w и −w. Заметьте, что мы нигде не определяли угол раствора стрелки (вообще это арктангенс отношения w и h), но он нам и не нужен: стрелка легко рисуется и так.

    Заключение

    В целом тригонометрия пригождается не так часто. Без тригонометрических функций вычисляется преломлённый луч по закону Снеллиуса. Если вам нужно повернуть сложный чертёж на определённый угол, вам потребуется только синус и косинус этого самого угла. Из них составляется матрица вращения, и на неё домножаются по очереди все точки. Тригонометрия на самом деле медленная, особенно когда её много. Поэтому не используйте её там, где она не нужна.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 66
    • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Тригонометрия часто нужна тем кто пишет игры и различные редакторы для окон мебели и прочее а всем остальным она скорее всего и не нужна…
      • 0
        а графические редакторы и ГИС?
      • +1
        Сеошникам и создателям дейтинг-стартапов точно не нужна!
      • 0
        Действительно полезная статья!
        • 0
          На чём основывается утверждение, что sin(0.3) считается медленее, чем 1.2/0.33? И то и то FPU.
          • +8
            Синусы считаются с помощью разложения в ряд, так что FPU придется произвести деление много раз, прежде чем получится результат. Сомневаюсь, что в современных FPU используются тригонометрические таблицы. Или все же используются?
            П.С. По опыту олимпиад очень хорошо знаю, что решения на векторной алгебре практически всегда быстрее.
            • –1
              Ну вы просто заставляете меня сделать тесты самому.

              1.c:

              #include <stdio.h>
              #include <math.h>
              void main(){
              double a;
              double b;
              for(a=0;a<1000000000;a++){
                      b=sin(a);
              }
              }
              


              time ./a.out

              real 0m1.412s
              user 0m1.400s
              sys 0m0.012s

              2.c
              #include <stdio.h>
              #include <math.h>
              void main(){
              double a;
              double b;
              for(a=0;a<1000000000;a++){
                      b=a/0.3;
              }
              }
              


              time ./a.out

              real 0m1.413s
              user 0m1.408s
              sys 0m0.004s

              Итого — синус и деление выполняются за строго ОДИНАКОВОЕ время.
              • +4
                кэш процессора активно работает здесь.
                как мне кажется — точнее было бы использовать разные коэфициенты, дабы исключить особенности процессоров
                • –4
                  При чём тут кеш? О чём вы? Это строго одинаковый код, в котором в одном случае выполняется инструкция fdiv, а во втором fsin. Какие особенности каких процессоров?

                  Если вы хотите предложить свой метод сравнить скорость деления и вычисления sin на современных FPU, приводите.
                • +3
                  >>> def sinus():
                  … last = time.clock()
                  … for i in xrange(1000000):
                  … x = math.sin(i)
                  … return time.clock() — last

                  >>> print sinus()
                  0.436118277602

                  >>> def delit():
                  … last = time.clock()
                  … for i in xrange(1000000):
                  … x = i/0.3
                  … return time.clock() — last

                  >>> print delit()
                  0.15221040663

                  В питонах деление быстрее

                  • –1
                    Это всего лишь означает, что в питоне хреновая работа с float стилем. В gсс sin и / для double просто разворачивается в ассемблерную инструкцию. Что происходит в питоне — одному богу известно, а на скорость выполнения программы может влиять, например, смена [] на функцию map и т.д.

                    Вот ассемблерный код для 1.c (синус):
                    • –4
                      в идеале должно разворачиваться в машинные коды, а не в ассемблерную инструкцию.
                    • +3
                      Упс, вчитался в ассемблер. Был неправ, гцц просто сожрало ненужную инструкцию.
                    • +18
                      Вы не учитываете:
                      а) оптимизацию компилятора, который может отсекать некоторые ветви кода, когда видит, что результат нигде не используется;
                      б) то что у вас результат накапливается в переменной b, которая быстро стремится к нулю. Функция sin(x) обрабатывает ноль как особый случай.
                      Попробуйте потестировать следующие примеры:
                      #include <stdio.h>
                      #include <math.h>
                      
                      void main(){
                      	int a;
                      	double b = 1;
                      	for(a=0;a<50000000;a++){
                      		if(a&1) {
                      			b = sin(b);
                      		}
                      		else {
                      			b = sin(1-b);
                      		}
                      	}
                      	printf("%lf\n", b);
                      }
                      


                      #include <stdio.h>
                      #include <math.h>
                      
                      void main(){
                      	int a;
                      	double b = 1;
                      	for(a=0;a<50000000;a++){
                      		if(a&1) {
                      			b = b/0.3;
                      		}
                      		else {
                      			b = 0.3/b;
                      		}
                      	}
                      	printf("%lf\n", b);
                      }
                      • +10
                        real 0m1.534s
                        user 0m1.520s
                        sys 0m0.016s

                        real 0m0.306s
                        user 0m0.308s
                        sys 0m0.000s

                        Да, ок, убедили, был неправ.
                        • 0
                          кстати, причина даже не в fdiv, а в том, что при делении gcc юзает mmx во все поля:

                          .L9:
                                  addl    $1, %eax
                                  divsd   %xmm1, %xmm0
                                  cmpl    $50000000, %eax
                                  je      .L8
                          .L4:
                                  testb   $1, %al
                                  jne     .L9
                                  movapd  %xmm1, %xmm2
                                  addl    $1, %eax
                                  cmpl    $50000000, %eax
                                  divsd   %xmm0, %xmm2
                                  movapd  %xmm2, %xmm0
                                  jne     .L4
                          .L8:
                                  movl    $.LC2, %edi
                                  movl    $1, %eax
                                  jmp     printf
                          


                          сравнить с sin-версией, у которой таки call sin.

                          .L4:
                                  testb   $1, %bl
                                  jne     .L7
                                  movsd   .LC0(%rip), %xmm1
                                  subsd   %xmm0, %xmm1
                                  movapd  %xmm1, %xmm0
                          .L7:
                                  addl    $1, %ebx
                                  call    sin
                                  cmpl    $50000000, %ebx
                                  jne     .L4
                                  popq    %rbx
                                  movl    $.LC1, %edi
                                  movl    $1, %eax
                                  jmp     printf
                                  .cfi_endproc
                          
                          • +2
                            добавь -ffast-math -m32 — получишь fsin и никаких xmm, а всё равно синус медленнее.
                          • 0
                            … т.е. даже не mmx, а штатные AMD64 инструкции:

                            siyobik.info/index.php?module=x86&id=75
                          • +3
                            Надо все же понимать как оптимизируют компиляторы, прежде чем приводить такие тесты.
                            И зачем double? Если float быстрее и часто достаточен.
                            • +4
                              А-а-а! Хочу такой же процессор, как у Вас, чтобы миллиард синусов вычислял за 1 секунду! :))
                              А то мой Core i7 сто миллионов итераций секунд 5 крутит!

                              Если серьезно, боюсь, Ваш тест неправилен. Похоже, компилятор выкинул неиспользуемые вычисления в обоих случаях. На самом деле, тест с синусом работает в 6-7 раз медленнее, чем с делением.
                              • 0
                                а вы уверены, что Ваши программы вообще работают?
                                в этих программах вычисляемое значение «b» в конечном итоге нигде не используется. Компилятор вполне мог скомпилировать программу без цикла вообще.

                                сделайте хотя бы вот так:

                                #include <stdio.h>
                                #include <math.h>
                                void main(){
                                double a;
                                double b=0;
                                for(a=0;a<1000000000;a++){
                                b=b+a/0.3;
                                }
                                printf("%f\n",b);
                                }

                              • 0
                                Предполагать, что либо подобное заранее не имеет смысла. Оптимизировать нужно только тогда, когда профайлер Вам показал, что sin есть узкое место. Вы не можете знать как преобразует Ваш код компилятор, а следовательно и делать заявления, что этот код отработает быстрее, чем вот этот.
                                • 0
                                  Это справедливо только тогда, когда написание более эффективного алгоритма требует больше усилий от программиста или же больший обьем кода. Если вы выбираете между двумя алгоритмами с одинаковой сложностью реализации — почему бы не реализовать тот, который, очевидно, будет работать быстрее. Кроме того, существует целый класс вычислительных задач, в которых сразу и без профайлера видно узкие места.
                                  • +1
                                    Статья не о низкоуровневой оптимизации, а о грамотном выборе алгоритмов. Из вас получится очень плохой архитектор.
                              • +3
                                Ну следующий шаг развития — целочисленные алгоритмы построения графики. Очень советую двинуться в этом направлении. Обещаю — вам понравится. Успехов! Отличная статья!
                                • +1
                                  Почему-то был уверен что в статье будет задача — определить выпуклость многоугольника. Простая задача, решив которую каждый поймет профит от использования векторов.
                                  • 0
                                    напомните решение?
                                    • +1
                                      Для каждой вершины многоугольника компонента Z векторного произведения векторов выходящих из этой вершины в две соседние имеет один и тот же знак.
                                      • 0
                                        Да, векторное произведение векторов — тоже очень нужная штука, просто я не хотел перегружать статью :-)
                                        • +1
                                          Забыл добавить: следует выбрать направление обхода вершин, и векторное произведение всегда брать в одном порядке, например вектор смотрящий против направления обхода умножать на вектор смотрящий по направлению.
                                  • 0
                                    Хорошая статья, но мне кажется, что программисты должны одинаково владеть обеими подходами,
                                    и выбирать их в зависимости от требований задач. Бывают классы задач, которые удобно решать в полярных или сферических координатах, например.
                                    • +3
                                      Спасибо!

                                      Еще по теме: некто Винни пишет о том же самом: что вместо сложных вычислений можно использовать простые и быстрые.
                                      Угол между двумя векторами: users.livejournal.com/_winnie/237714.html
                                      Пересечение двух отрезков: users.livejournal.com/_winnie/152327.html#cutid1
                                      • +2
                                        Спасибо за статью :) В последнее время веб-программирование утомляет и превращается в рутину, решил для разнообразия сделать игру в свободное время. И столкнулся с тем, что позабыл большую часть геометрии и алгебры :(

                                        Кто-нибудь может посоветовать книги, статьи, сайты по алогоритмам в играх и 2D графике? В 3D пока не лезу, делаю 2D, но в целом хочется и красивых частиц туда добавить и другие интересные фишки типа теней, света и т.д.
                                      • +2
                                        С помощью основного тригонометрического тождества вы сможете однозначно определить синус по косинусу и наоборот лишь в некоторых случаях, когда нам, например, известно, что угол от -pi/2 до pi/2. В общем случае вы не сможете определить знак другой функции…

                                        Для быстрого вычисления синуса и косинуса используется (и я использую) тангенс половинного угла, через который синус и косинус вычисляются с помощью обычных арифметических операций.
                                        • 0
                                          Да, вы правы. Результат вращения разный получится. Уберу про тождество.
                                          А с тангенсом надо аккуратно — он в бесконечность может уйти, если поворачивать на 180°.
                                        • 0
                                          Эх, объясняли бы в школе и университете векторы подобным же образом. А то ведь, помню, зачем это нужно и где может применяться никто не удосуживался прояснить. В результате народ что-то зазубривал, сдавал, и благополучно забывал.
                                          • 0
                                            у нас в универе тут же был курс «ком. графики» где все эти матрицы и повороты показывали на примерах.
                                            • 0
                                              у нас был просто курс «высшей математики». правда, факультет экономический, и потому часть задач имела отношение к бизнесу, но вот векторы прошли чем-то совершенно оторванным от реальности. пост сейчас прочла с большим интересом.
                                            • 0
                                              И объясняют. Естественно, не на экономических факультетах.
                                              • 0
                                                Почему же «естественно»?
                                                В хорошем учебном заведении любую излагаемую теорию должны иллюстрировать практикой. Если вам с учебным заведением/преподавателем повезло, я могу за вас лишь порадоваться.
                                                • 0
                                                  Потому что это выходит за рамки курса линейной алгебры. Линейная алгебра это чистая теория, которая применима в очень многих областях. Одна из этих областей — компьютерная графика, по которой есть отдельный курс. И вполне логично, что его не читают экономистам.
                                                  • 0
                                                    Статистики под рукой нет, но большинство людей, насколько мне известно, плохо воспринимают «чистую теорию». Наверняка и у вас были одноклассники, например, возмущавшиеся, что им необходимо изучать физику/химию/биологию, если им при поступлении в ВУЗ экзамены по этим предметам все равно сдавать не придется. Предположить как им могут пригодиться полученные знания в реальной жизни они не могли. Между тем, если бы преподаватель химии взяла бутылку «Спрайта» и вместе с учениками «расшифровала» состав, а преподаватель биологии обсудила преимущества подсолнечного масла с рекламным слоганом «не содержит холестерина», глядишь, мотивация была бы выше.
                                                    • 0
                                                      Простите, а насколько часто экономистам приходится писать программы для рисования стрелочек? И почему вы считаете, что пример использования линейной алгебры должен быть именно в рамках компьютерной графики? Вы знаете, что курс линейной алгебры читается всем техническим специалистам? И разные специалисты в будущем могут применять её в разных областях. Так что, примеры во всех возможных областях приводить? И сколько тогда будет занимать курс?
                                                      • 0
                                                        А с чего вы решили, что я просила примеры программ для рисования стрелочек или в рамках компьютерной графики? Наоборот, если уж преподаете линейную алгебру экономистам, будьте добры, поясните, где и как они ее смогут применять. Но наглядных примеров не было вообще, ни из какой области. Хотя, скажем, у преподавателя теории вероятностей с этим проблем не было, несмотря на то что вел курс у самых разных факультетов.
                                                        • +1
                                                          Ну если вопрос стоит таким образом… С теорией вероятности как-то проще. А где применять линейную алгебру экономистам я, например, придумать не могу.
                                            • +2
                                              Увы, далеко не всегда и не везде возможно отказаться от синусов и косинусов… Когда нужно быстро молотить косинусы и синусы в цикле — использую только таблицы до сих пор, ибо как заметили выше, fsin и fcos — тормозные операции даже на современных CPU.
                                              Вот кстати набросал пример небольшой — вращающийся тор. Вряд-ли можно вращать точки не через чинус-косинус: Пример 3D Tor
                                              • +2
                                                С помощью матриц вращения — легко. Конечно, зависит от того, как вы задаёте траекторию, но в любом случае вам нужно не больше одного синуса и одного косинуса на каждый кадр, а это уже нестрашно.

                                                Lookup tables — это тоже очень хорошо.
                                              • +1
                                                Как один из тех программистов который любит использовать тригонометрию:) Автору спасибо за статью, пойду векторную алгебру вспоминать:)
                                                • 0
                                                  Я бы посоветовал аналитическую геометрию, а не векторную алгебру. Во всяком случае нас учили решать задачки по геометрии и тригонометрии векторами именно там, а на алгебре были совсем другие материи, не смотря на то, что одно тесно связанно с другим.
                                                  • 0
                                                    Спасибо за совет.
                                                • 0
                                                  Ох, прям в тему пришлось, сейчас увлекся анаморфной живописью. Воспользовался предложением использовать векторы вместо тригонометрии — преобразования вышли более наглядны, а программа на их основе работает несколько быстрее своего аналога.
                                                  • 0
                                                    а угол вектора (0,0) -> (x,y) можно как-то вычислить не прибегая к atan2?
                                                    • 0
                                                      Главный вопрос — не можно ли, а нужно ли. Как правило, в большинстве случаев не нужно. Если вам кажется, что нужно, возможно, вы что-то не учли.

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

                                                    Самое читаемое