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

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

    Теория

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

    Геометрический смысл — это отрезок на плоскости, для которого важна длина и направление, но не важно положение. То есть параллельный перенос не меняет вектора. Часто полезно отождествлять вектор с точкой (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), но он нам и не нужен: стрелка легко рисуется и так.

    Заключение

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

    Подробнее
    Реклама
    Комментарии 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
                                                      Главный вопрос — не можно ли, а нужно ли. Как правило, в большинстве случаев не нужно. Если вам кажется, что нужно, возможно, вы что-то не учли.

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