Hwdtech blog
"Зачем мне математика?!"
на примере реального проекта - агронавигатора
А действительно - зачем??? Отвечаем на главный вопрос студентов IT-специальностей.
16-04-2021
кейс, математика, алгоритмы, агронавигатор
Время чтения: 5 минут
Продолжаем цикл публикаций о нашем проекте "Agroved". Напомним, это приложение-агронавигатор, которое мы разрабатываем с нуля. Почитать о проектировании приложения и создании дизайн-концепции можно здесь. А сегодня поговорим о том, насколько важно, необходимо и незаменимо при создании такого продукта знание математики.
Что такое агронавигатор?
Суть проекта такова: наш пользователь управляет некой сельскохозяйственной техникой (например, комбайном, сеялкой, трактором с прицепом и т.д.). На своем агрегате он едет по полю и, казалось бы, зачем ему навигатор - ведь заблудиться там невозможно! Но все дело в экономической выгоде.

Во-первых, если агрегат два раза проедет по одному и тому же участку - мы получим лишний расход удобрения, топлива, химикатов, семян и т.д. Во-вторых, если какой-то участок будет случайно не обработан - уменьшится наш урожай. И то и другое довольно сложно отследить глазами, особенно находясь за рулем комбайна. И то и другое - это деньги, которые можно потерять, а можно и сохранить. Главный вопрос: как?

Берем планшет, создаем приложение, которое будет отслеживать путь трактора по полю и подсказывать пользователю, какие участки он проехал, где пропуски и т.д. + возможно, собирать статистику о пройденных километрах, отработанных часах и др., чтобы это сказывалось на зарплате водителя.
Вот он, наш агронавигатор: так выглядит рабочий режим приложения.
Причем тут математика?
При работе над проектом возник ряд вопросов, решить которые без применения математики попросту невозможно. Про самые интересные моменты мы сейчас расскажем.
1) Как вы знаете, навигатор (любой) ориентируется в пространстве благодаря спутниковому сигналу. Но сигнал со спутника приходит с определенной погрешностью. Да, в инструкции говорится, что все в пределах нормы, но если вы неверно подключили антенну или с ней возникли проблемы - появляются погрешности. Из-за них стоящее неподвижно устройство постоянно получает разные координаты своего местоположения, поэтому на экране оно отображается некорректно - как будто постоянно "прыгает" на месте.

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

Но! Планшет с приложением по-прежнему как стоял, так и стоит на тракторе. А траекторию агронавигатор должен учитывать с точки зрения самого прицепного оборудования. При различных разворотах пути "трактора" и "сеялки" будут отличаться. Поэтому здесь мы решаем нетривиальную задачу: как по маршруту движения агрегата определить маршрут движения прицепа? Без знания математики и механики - да никак!
Отображение агрегата и прицепа в настройках приложения
3) При отображении траектории движения агрегата в приложении (хоть с прицепом, хоть без него) тоже возникает много вопросов "как?".

Если мы просто напрямую отрисовываем маршрут на экране, то количество точек этого маршрута постоянно растет и в конце концов становится очень велико (например, в течении дня трактор работает около 12 часов - и все эти точки фиксируются в нашем агронавигаторе). Отрисовав всю эту массу как есть, "в лоб", мы получим серьезную проблему: количество точек негативно скажется на производительности.

Здесь перед нами алгоритм линейной сложности: количество отображаемых кадров в единицу времени заметно падает по мере роста количества точек - и в итоге мы начнем показывать менее одного кадра в секунду (только представьте, как при этом будет выглядеть работа приложения!).

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

Давайте поговорим об этом поподробнее. Как вы понимаете, наша задача состоит в том, чтобы формировать изображение на планшете и желательно делать это по 60 раз за секунду. Но, если мы рисуем точки непрерывно, это занимает все больше и больше времени. Рано или поздно количество времени на отрисовку точек становится больше, чем мы можем заложить на отрисовку 1 кадра.

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

Как? Каждая точка попадает в какой-то определенный квадрант - и мы формируем их список по каждому квадранту. А затем из массива, допустим в 10 000 точек, выбираем только те, которые находятся в нужном квадранте - а не все подряд. Предполагается, что водитель агрегата не будет намеренно проезжать много раз по одному и тому же месту - и не создаст нам кучу "лишних" точек в одном квадранте.

Кроме того, в данном случае нам пригождается канторовская нумерационная функция и ее вариации - преобразование таблички в сплошной массив и обратно невозможно без нее. Это основа основ, ее обязательно нужно знать для работы с квадрантами.
Рабочий процесс: отображение участка пути на экране.
4) Еще пара крайне важных математических решений для агронавигатора - это алгоритм поиска пересечений и алгоритм поиска островов.

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

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

Здесь мы говорим, что то, что находится "внутри" наших траекторий движения агрегата является "пропуском". Чтобы находить пропуски, мы решили использовать алгоритм поиска островов - он достаточно трудоемкий, но, к счастью, его применение не очень часто требуется при разработке приложения. Для нечастого запуска и размеров наших полей он подходит даже при условии своей большой сложности.

Жизненно важно обращать внимание на построение системы координат: мы не всегда стартуем из идеальной точки "ноль", координаты нашего трактора могут быть и отрицательными. Но, чтобы "запихнуть" их в алгоритм островов, придется перейти к другой системе координат - к относительной. Тогда алгоритм заработает - и эта задача тоже требует от разработчика в первую очередь математических познаний.
Пересечения и пропуски - наглядно.
5) Алгоритм Брезенхема - алгоритм рисования линии - необходим на этом проекте для корректной работы детектора коллизий (это внутренний термин, обозначающий ситуацию, когда трактор - если он не поменяет траекторию движения - заедет на уже обработанную поверхность).

Что говорит нам Вики:

Алгоритм Брезенхе́ма — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике.


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

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


Те, кто работает с графикой должны знать алгоритм островов (он отвечает за "заливку") и алгоритм Брезенхема (он помогает рисовать линии и окружности). Если в вузе изучается предмет "машинная графика", то, по идее, миновать их изучение вы никак не сможете.
Резюме
Можно, наверное, помечтать о том, что кто-то вот прямо сейчас разрабатывает вместо подобного приложения целые агронавигаторы-беспилотники. И сказать: "Зачем вы это делаете? За ними будущее!". Но! Во-первых, мы решаем бизнес-задачу заказчика, которая тоже существует и актуальна вот прямо сейчас. А во-вторых, беспилотники, конечно, появятся, но сегодня мы предоставляем более быстрое и бюджетное решение, чем эти системы.

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

Да, математика нужна. Надо понимать, что основной вопрос, который встанет перед вами, если вы разработчик, не в том, чтобы запрограммировать тот или иной алгоритм (в Сети можно найти их уже реализованными!), а в том, чтобы догадаться, что в вашей задаче можно применить один из множества существующих - и выбрать правильно.


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

Говоря на эту тему, мы как бы наблюдаем следствие эффекта Даннинга-Крюгера: если мы не знаем какого-то алгоритма, то мы не можем догадаться о необходимости его применения. У нас остается один вариант - придумать! Но все алгоритмы не изобретешь, а для конкретной задачи это будет долгий и очень дорогой способ разработки.


Для справки:


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


Может ли такое происходить с программистом? Да запросто! Если квалификации недостаточно, то догадаться, что решение не работает т.к. не используется правильный алгоритм, согласно этому эффекту, крайне затруднительно. Можно только знать. Когда вам понадобится то или иное математическое знание, оно либо будет у вас в голове, либо вы изобретете его заново, либо у вас ничего не получится. Что лучше, быстрее, эффективнее? Делайте выводы!
Спасибо за внимание!
Раз в месяц мы делаем рассылку с анонсом новых кейсов и статей, опубликованных на сайте.
Подпишитесь на обновления.
Гарантируем - никакого спама. Нажимая на кнопку, вы даете согласие на обработку персональных данных и соглашаетесь c политикой в отношении обработки персональных данных.