Рад представить вашему вниманию еще одну крохотную, но полезную open-source-утилиту своего авторства — Simplify.js.



Simplify.js — очень быстрая реализация упрощения ломаных линий на JavaScript. Изначально написав ее для Leaflet (библиотеки для интерактивных карт), после небольшого эксперимента по оптимизации захотелось выпустить ее в качестве отдельной библиотеки без зависимостей, которую можно использовать как в браузере, так и на серверных платформах, таких, как Node.js, и применять и для 2D, и для 3D-точек.

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

Задачу решают со времен Древней Греции, а звучит она так: c помощью только циркуля и линейки требуется разделить произвольный угол на три равные части. При этом делений на линейке не должно быть, а в процессе построения никаких отметок на ней делать не допускается. Пользоваться можно только простым циркулем и линейкой без засечек и обеспечить идеальную точность построения для всех видов углов. В 1837 году французский математик Пьер Лоран Ванцель доказал нерешаемость трисекции угла в таком виде.

Недавно друг озадачил меня своим вариантом решения. Самое странное, что не смотря на его простоту, ошибку в нём у нас найти так и не получилось. Сразу оговорюсь, что альтернативные варианты решения, которые публиковались ранее (и оказались не правильными), были изучены. Иллюзий, что вот так просто нашлось решение задачи, которую человечество пыталось решить больше 2000 лет, никто не строит. Тем не менее, мы с другом будем очень благодарны Хабрасообществу за помощь в поиске ошибки.

Аннотация

Эта статья написана в продолжении первой части статьи про работу с бинарными изображениями, в которой рассказывается как подсчитывать объекты. Однако от одного подсчета толку мало, часто хочется узнать некоторые геометрические параметры распознаваемых объектов. Кажется, что тут считать — узнал количество восьмерок — площадь равна 19, посчитал количество семерок — площадь равна 7 (см. картинку в Аннотации).
Делая так, мы будем вынуждены использовать дополнительный проход по изображению, желательно этого избегать — в пользу повышения эффективности реализации. Как и было запланировано, в этом топике рассказывается о подсчете геометрических характеристик объектов без дополнительного прохода.
А так же: фактор формы и розы Гвидо-Гранди и чем отличается квадрат от прямоугольника, а он от звезды.

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

Начнем с того, почему не SVG или Canvas, а именно DOM. Потому что DOM-элементы отрисуют даже самые старые браузеры, да и целью является не само рисование фигуры, а алгоритм преобразования (мысли пользователя+движения рукой) в фигуры на экране, прямо в окне браузера. А способ рисования можно выбрать любой.

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

Не оригами, но всё же. У меня не так давно произошел случай. Я что-то слушал, о чем то думал, и сгибал лист бумаги формата А4. В результате я офигел от того, что получился равносторонний треугольник. Взял линейку, обмерил — всё верно.

Хочу спросить у Вас, мои дорогие: существуют ли такие способы уже? Вряд ли я первый.

P.S. Спрашивал у интернетов — они сказали не знают.

=========================================================
UPD: В сявзи с минусующими и тем кто в поисках смысла:

Ещё раз о задаче:

Есть лист А4. Используя только сгибы сделать равносторонний треугольник.

Вопрос: кто каким путем придет к решению задачи?

Это не просто, не сложно. Это не зачем.
Я спрашиваю о последовательности действий only.

Вспомнилась интересная пространственная задачка с одного собеседования:

Есть 2 проекции фигуры (нет скрытых линий, т.е не шар внутри куба),
надо найти третью проекцию или нарисовать всю фигуру. Удачи.