Действительно. Мне, почему-то показалось, что на Raspberry получилось быстрее видеокарты. Тем не менее, даже 10 секунд для Raspberry - хороший результат.
На счет линейного алгоритма с поворотами. У меня не получилось придумать такой алгоритм, который бы с одной стороны хорошо работал, с другой работал не зависимо от числа нарисованных точек.
Последний хорошо работающий вариант такого алгоритма был основан на алгоритме распознавания ломанной линии из статьи — распознаем среднюю точку последнего отрезка, по мере добавления точек пользователем рассчитываем расстояние до каждой точки фигуры до последнего отрезка. Если оно превышает пород — разбиваем его в этой точки и считаем последний отрезок текущим. После разбиения новый отрезок можно преобразовывать в кривую безье. Его проблема в том, что до тех пор пока пользователь рисует прямую он пересчитывает расстояние до всех предыдущих точек.
С углами до следующей точки я не смог придумать ничего хорошо работающего. Если у вас есть идея как это реализовать, хотя бы общие шаги. Я могу попробовать реализовать ваш алгоритм.
Я старался чтобы ни один алгоритм не выполнялся с квадратичной сложностью. Если я правильно посчитал, то общая сложность для всех фигур — N * log(N), плюс несколько одиночных проходов по всем точкам, плюс константа зависящая от размера внутренного массива, сейчас это 1024, но его можно уменьшить.
Технически, сам массив точек от пользователя можно прореживать, если их слишком много. Например, выбирая, каждую вторую точку.
Мой расчет сложности
Для всех фигур выполняется преобразование масива точек в массив из 1024 чисел. Преобразование состоит из следующих стадий:
расчет центра фигуры (один проход по всем точкам);
расчет расстояния до каждой точки фигуры (тоже один проход);
сортировка точек по расстоянию (N * log(N) от числа точек);
заполнение массива расстояний по углам с использованием двоичного поиска (1024 * log(N));
В общей сложности на подготовку нужно N * log(N). Далее для каждый алгоритм идет своим путем:
эллипс — сглаживает данные (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;
многоугольник — строит корреляцию с ядром (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;
ломанная линия — единственный алгоритм проходящий по всем точкам несколько раз, максимальное число проходов равно максимальному точек в линии. Итого N * const.
В общем случае в худшем случае, сокращая константы будет N * log(N). Далее нужно посчитать отклонение от рисунка пользователя для каждой фигуры.
эллипс — один проход по всем точкам пользователя. Итого - N;
многоугольник и ломанная линия — проход по всем точкам, нарисованным пользователем. Итого - N.
В конечном счете, без сокращения, получается: N * log(N) + 5 N + 1024 log(N) + несколько проходов по фиксированному массиву с расстояниями.
Возможно это имело значение встарых версиях java. Сейчас подобные конструкции компилируются в одинаковый байткод (ссылка на пример в godbolt), так что это скорее вопрос удобства восприятия, чем скорости работы. У меня в коде причина использования += чисто субъективная, связана она с тем, что я пишу не только на java.
Код класса с различными инкрементами
public class Test {
public static void increment1() {
for (int index = 0 ; index < 10; index += 1) {}
}
public static void increment2() {
for (int index = 0 ; index < 10; index++) {}
}
public static void increment3() {
for (int index = 0 ; index < 10; ++index) {}
}
}
Если я правильно понимаю, то gammu просто пишет AT команды в/dev/ttyUSB0. Гипотетически, если UART от SIM800 пробросить в/dev/ttyS0 и указать его в конфиге gammu, то оно должно работать.
Смотрю я на таких роботов и у меня возникает вопрос - у всех роботов ноги находятся в изогнутом на 90 градусов положении, зачем это сделано?
Например, представленный робот в положении по умолчанию сгибает ноги на 45 градусов в плече и на 90 градусов в локте. Мне кажется было бы эффективнее располагать ноги более вертикально, как это делают кошки/собаки/лошади. Это и снимает нагрузку с моторов и позволяет эффективнее перемещаться. Мне не совсем пепонятно почему все роботы используют именно согнутые ноги.
Это был очень упрощенный пример. В жизниf1может быть некой оберткой, выполняющей дополнительные проверки.
Например,f1может проверять, чтохявляется сущностью классаenemy(которых не более 100 на сцену), аf2— может "убивать" переданный объект по индексу. Тогда при вызовеf2на объекте 9999 может происходить запись за пределы массива объектов.
Как я это понимаю. Пусть функцияf1определена какf1(int8 x) = f2(x), а функцияf2 — f2(int16 x) -> bool. Тогда, в тестах, включающихf1,f2будет тестироваться только с парамерамиint8, не смотря на то, что одно из значений int16 может привести к багу.
Например у вас есть серия устройств на дешевом микроконтроллере, заказчик хочет добавить еще одно устройство с поддержкой BlueTooth. В такой ситуации, возможно, проще будет добавить модем в готовое устройство, чем полностью переделывать его на другой контроллер.
Еще вариант — для самообразования, поотправлять в ручную команды, чтобы разобраться в работе протокола / посмотреть что отправляют другие устройства.
Спасибо за пояснение. Я думал, что вы имеете в виду какой-то классический алгоритм.
На основании вашего предыдущего комментария я написал что-то более-менее рабочее. Постараюсь описать результат своего творчества в следующей части статьи.
Мне не удалось найти понятное описание этого алгоритма. Поэтому мне сложно представить как реализовать описанный вами аглоритм в коде, чтобы проверить его на реальных данных. Буду благодарен, если вы сможете дать ссылку на соответствующую статью или литературу. Боюсь, что без понимания этого алгоритма я не готов к дальнейшей дискусии.
Мне кажется, что такой эффект будет наблюдаться в любом алгоритме, использующем пороговые значения. Например, если пользователь достаточно криво нарисовал ребро, то, в зависимости от фильтра, ребро может разделяться дополнительной вершиной или оставаться прямым (как в примере с трапецией). Тем не менее насчет доработки я с вами согласен — здесь еще есть над чем работать.
На момент написания статьи, ядро с квадратом — третий вариант, первые два работали хуже. Сейчас я изменил его такой вариант: , рассчитанный на 3-5 угольники.
выглядит так (немного более острый пик)
К сожалению, ядро с ярко выраженным пиком плохо различает тупые углы, из-за чего трапеции часто распознаются как треугольники.
Спасибо. В репозитории я уже добавил простое распознавание эллипсов. Позже добавлю отдельное ядро, чтобы алгоритм точнее выбирал их размер и угол поворота.
Действительно, выбор эллипс/многоугольник лучше делать на основании того, что больше похоже на закорючку пользователя. После реализации эллипсов, постараюсь добавить выбор по лучшей аппроксимации.
Изначально у меня не было задачи распознавать сложные фигуры вроде звезд. Поэтому я выбрал алгоритм хорошо работающий на выпуклых многоугольниках. Однако, если это будет интересно сообществу, я могу попробовать реализовать алгоритм с определением точек поворота.
Да, и не зависит от того, что происходит на луне. Более формально - лампочка "горит" если на стороне переключателя был переходный процесс 1/с секунд назад. И чем дальше в прошлом был импульс тем тусклее горит лампочка.
Можете посмотреть вот это видео - https://www.youtube.com/watch?v=OSkudhqU3Ck , там более менее наглядно показано как это работает
Очень упрощенно - при включении провода работают как антенны, при этом первый передает часть импульса на второй за 1/с (по воздуху), а через секунду приходит основной сигнал (по проводу). Если на луне поставить резистор, то наводка останется прежней, но резисторе мы узнаем только через секунду.
Действительно. Мне, почему-то показалось, что на Raspberry получилось быстрее видеокарты. Тем не менее, даже 10 секунд для Raspberry - хороший результат.
Хотелось бы услышать историю о том, почему на Raspberry Pi модель работала быстрее чем на видоекарте и как она вообще там работала.
На счет линейного алгоритма с поворотами. У меня не получилось придумать такой алгоритм, который бы с одной стороны хорошо работал, с другой работал не зависимо от числа нарисованных точек.
Последний хорошо работающий вариант такого алгоритма был основан на алгоритме распознавания ломанной линии из статьи — распознаем среднюю точку последнего отрезка, по мере добавления точек пользователем рассчитываем расстояние до каждой точки фигуры до последнего отрезка. Если оно превышает пород — разбиваем его в этой точки и считаем последний отрезок текущим. После разбиения новый отрезок можно преобразовывать в кривую безье. Его проблема в том, что до тех пор пока пользователь рисует прямую он пересчитывает расстояние до всех предыдущих точек.
С углами до следующей точки я не смог придумать ничего хорошо работающего. Если у вас есть идея как это реализовать, хотя бы общие шаги. Я могу попробовать реализовать ваш алгоритм.
Я старался чтобы ни один алгоритм не выполнялся с квадратичной сложностью. Если я правильно посчитал, то общая сложность для всех фигур — N * log(N), плюс несколько одиночных проходов по всем точкам, плюс константа зависящая от размера внутренного массива, сейчас это 1024, но его можно уменьшить.
Технически, сам массив точек от пользователя можно прореживать, если их слишком много. Например, выбирая, каждую вторую точку.
Мой расчет сложности
Для всех фигур выполняется преобразование масива точек в массив из 1024 чисел. Преобразование состоит из следующих стадий:
расчет центра фигуры (один проход по всем точкам);
расчет расстояния до каждой точки фигуры (тоже один проход);
сортировка точек по расстоянию (N * log(N) от числа точек);
заполнение массива расстояний по углам с использованием двоичного поиска (1024 * log(N));
В общей сложности на подготовку нужно N * log(N). Далее для каждый алгоритм идет своим путем:
эллипс — сглаживает данные (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;
многоугольник — строит корреляцию с ядром (по фиксированному массиву из 1024 элемента, окно фиксированного размера) + один проход по массиву. Итого N * log(N) для эллипа;
ломанная линия — единственный алгоритм проходящий по всем точкам несколько раз, максимальное число проходов равно максимальному точек в линии. Итого N * const.
В общем случае в худшем случае, сокращая константы будет N * log(N). Далее нужно посчитать отклонение от рисунка пользователя для каждой фигуры.
эллипс — один проход по всем точкам пользователя. Итого - N;
многоугольник и ломанная линия — проход по всем точкам, нарисованным пользователем. Итого - N.
В конечном счете, без сокращения, получается: N * log(N) + 5 N + 1024 log(N) + несколько проходов по фиксированному массиву с расстояниями.
Возможно это имело значение встарых версиях java. Сейчас подобные конструкции компилируются в одинаковый байткод (ссылка на пример в godbolt), так что это скорее вопрос удобства восприятия, чем скорости работы. У меня в коде причина использования
+=чисто субъективная, связана она с тем, что я пишу не только на java.Код класса с различными инкрементами
Полученный байт код
Версия java
Если я правильно понимаю, то gammu просто пишет AT команды в
/dev/ttyUSB0. Гипотетически, если UART от SIM800 пробросить в/dev/ttyS0 и указать его в конфиге gammu, то оно должно работать.Смотрю я на таких роботов и у меня возникает вопрос - у всех роботов ноги находятся в изогнутом на 90 градусов положении, зачем это сделано?
Например, представленный робот в положении по умолчанию сгибает ноги на 45 градусов в плече и на 90 градусов в локте. Мне кажется было бы эффективнее располагать ноги более вертикально, как это делают кошки/собаки/лошади. Это и снимает нагрузку с моторов и позволяет эффективнее перемещаться. Мне не совсем пепонятно почему все роботы используют именно согнутые ноги.
Это был очень упрощенный пример. В жизни
f1может быть некой оберткой, выполняющей дополнительные проверки.Например,
f1может проверять, чтохявляется сущностью классаenemy(которых не более 100 на сцену), аf2— может "убивать" переданный объект по индексу. Тогда при вызовеf2на объекте 9999 может происходить запись за пределы массива объектов.Как я это понимаю. Пусть функция
f1определена какf1(int8 x) = f2(x), а функцияf2—f2(int16 x) -> bool. Тогда, в тестах, включающихf1,f2будет тестироваться только с парамерамиint8, не смотря на то, что одно из значенийint16может привести к багу.Например у вас есть серия устройств на дешевом микроконтроллере, заказчик хочет добавить еще одно устройство с поддержкой BlueTooth. В такой ситуации, возможно, проще будет добавить модем в готовое устройство, чем полностью переделывать его на другой контроллер.
Еще вариант — для самообразования, поотправлять в ручную команды, чтобы разобраться в работе протокола / посмотреть что отправляют другие устройства.
Спасибо за пояснение. Я думал, что вы имеете в виду какой-то классический алгоритм.
На основании вашего предыдущего комментария я написал что-то более-менее рабочее. Постараюсь описать результат своего творчества в следующей части статьи.
Мне не удалось найти понятное описание этого алгоритма. Поэтому мне сложно представить как реализовать описанный вами аглоритм в коде, чтобы проверить его на реальных данных. Буду благодарен, если вы сможете дать ссылку на соответствующую статью или литературу. Боюсь, что без понимания этого алгоритма я не готов к дальнейшей дискусии.
Мне кажется, что такой эффект будет наблюдаться в любом алгоритме, использующем пороговые значения. Например, если пользователь достаточно криво нарисовал ребро, то, в зависимости от фильтра, ребро может разделяться дополнительной вершиной или оставаться прямым (как в примере с трапецией). Тем не менее насчет доработки я с вами согласен — здесь еще есть над чем работать.
На момент написания статьи, ядро с квадратом — третий вариант, первые два работали хуже. Сейчас я изменил его такой вариант:
, рассчитанный на 3-5 угольники.
выглядит так (немного более острый пик)
К сожалению, ядро с ярко выраженным пиком плохо различает тупые углы, из-за чего трапеции часто распознаются как треугольники.
Пример неправильного распознавания трапеции
Спасибо. В репозитории я уже добавил простое распознавание эллипсов. Позже добавлю отдельное ядро, чтобы алгоритм точнее выбирал их размер и угол поворота.
Действительно, выбор эллипс/многоугольник лучше делать на основании того, что больше похоже на закорючку пользователя. После реализации эллипсов, постараюсь добавить выбор по лучшей аппроксимации.
Изначально у меня не было задачи распознавать сложные фигуры вроде звезд. Поэтому я выбрал алгоритм хорошо работающий на выпуклых многоугольниках. Однако, если это будет интересно сообществу, я могу попробовать реализовать алгоритм с определением точек поворота.
.
Да, и не зависит от того, что происходит на луне. Более формально - лампочка "горит" если на стороне переключателя был переходный процесс 1/с секунд назад. И чем дальше в прошлом был импульс тем тусклее горит лампочка.
Можете посмотреть вот это видео - https://www.youtube.com/watch?v=OSkudhqU3Ck , там более менее наглядно показано как это работает
Очень упрощенно - при включении провода работают как антенны, при этом первый передает часть импульса на второй за 1/с (по воздуху), а через секунду приходит основной сигнал (по проводу). Если на луне поставить резистор, то наводка останется прежней, но резисторе мы узнаем только через секунду.
Спасибо. Попробовал этот сервис, очень похоже на то, что нужно.