Разработка векторного редактора на JavaScript (сложности и идеи)
Предыстория:
Имя большой опыт в разработке веб-сайтов (около 15 лет) и являясь программистом, я очень не люблю рутинную работу, стараюсь ее либо избегать, либо каким-то образом оптимизировать. Другими словами, если мне в какой-то момент необходимо заниматься наполнением контентом сайта (да, знаю, не царское дело программисту наполнять сайт, но случаи разные бывают), то я предпочту потратить пару часов на написание парсера входящих данных, чем часа 4 вколачивать эти данные вручную. И давно меня терзала проблема отсутствия удобного редактора для создания карт изображения. Конечно, можно нарисовать карту в Corel Draw или подобном, выгрузить в SVG и по быстрому переконвертировать в нужный формат, но меня давно интересовала возможность создания некоего редактора, который позволит, не загружая сторонние программы, прямо на сайте, по-быстрому загрузить изображение и выделить на нем нужную карту. Например, есть некое изображение здания, на котором необходимо выделить контур этажа и привязать к нему какие-то JavaScript-события или просто ссылку, вот как здесь: 
Также, помимо ручного выделения контура объекта, мне бы хотелось иметь инструмент, аналогичный Magic Wand в Photoshop, чтобы ткнул мышкой и у тебя появился готовый контур. Несмотря на то, что уже несколько лет натыкаюсь на различные редакторы карт (как on-line, так и off-line), подобной функции в них не нашел. Ну, раз нет — будем писать сами.
Хочется сразу предупредить, поскольку в итоге нашел заказчика на коммерческий продукт, то полноценных исходников, к сожалению, не будет, но идеи и сложности, возникшие при разработке, постараюсь описать как можно более подробно, мало того, я не специализируюсь на разработке графики и интерфейсов, поэтому какие-то «откровения» могут показаться смешными или даже глупыми, тем не менее:
Определение функционала редактора: Создание контура вручную, а также иметь возможность редактировать ранее созданные контуры; Хотя HTML тег MAP — AREA — SHAPE поддерживает несколько типов форм выделенной области, было решено остановиться только на создании сложных контуров с помощью POLY; Собственно, что было интересно мне, как программисту, это выделение области со схожими цветами, с помощью одного клика мыши. CANVAS — то, что нужно? Поскольку я уже имел опыт работы с тегом CANVAS и представлял его возможности, было решено остановится на нем (как оказалось, это стало ошибкой, замедлившей разработку редактора на приличное время).Выбор алгоритма обхода контура: Перепробовав несколько вариантов алгоритмов обхода контура, в конечном итоге выбрал Moor Neighborhood. На мой взгляд, этот алгоритм удачно совмещает скорость работы и достаточную простоту реализации.Итак:
Тестовое изображение, для работы с контуром
Выделение контура с прямыми сторонами
Выделение искривленного контура
Как видим, алгоритм обхода контура отлично справляется и выделяет все, что нужно, при этом видим, что на относительно небольшой контур, требуется почти 300 точек для прямых линий и почему-то на 50 точек меньше, если контур повернут вокруг своей оси.
В принципе, уже сейчас данный контур можно запоминать и с ним работать, но вот сильно смущает большой объем данных даже для небольшого контура.
Оптимизация готового контура: Была выбрана следующая схема работы с контуром: сначала создаем контур из точек и удаляем ненужные, за исключением узловых точек (или точек смены направления). С одной стороны, происходит двойная работа, с другой стороны, эта схема упрощает отладку механизма удаления ненужных точек.Выбор узловых точек: Решение, лежащее на поверхности: Берем точку, добавляем ее в массив узловых точек (не точек контура); Последовательно обходим точки от стартовой, измеряя угловое расстояние между первоначальной и текущей, если угловое расстояние больше или меньше некоего (определенного опытным путем), то эта точка является новой стартовой, добавляем ее в массив\ узловых точек; Это решение работает, но вот расчет углового расстояния терзало душу наличием «тяжелых» функций работы с углами. Поэтому было решено посмотреть на существующие «велосипеды» и вот забытое решение из школьной математики: скалярное произведение векторов.Берем его за основу — алгоритм работает отлично и в разы быстрее.
Смотрим результат: 
13 точек — вполне устраивает.
61 точка?! Но почему?!
А вот почему: как-то забыл, что, несмотря на большие разрешения мониторов, ретины и прочее, линия на экране по факту представляет из себя ломаный набор точек (а ведь каких-то лет 20 назад, я, высунув язык, осваивал рисованием линий с помощью алгоритма Брезенхема…):
Жирным выделена теоретическая прямая, а разница бьет в глаз.
Проблему временно решил введением некоего множителя, позволившего пропорционально увеличить расстояние между точками (с сохранением угловых расстояний), что позволило сгладить разницу между точками и сделать расчет более точным, в результате получаем 23 точки вместо 61, больше чем для прямых линий, но для моих целей пока достаточно.
Подведя итог:
Редактор готов, позволяет загружать изображение, масштабировать, двигать мышкой, добавлять новые объекты и редактировать существующие, работает все на странной смеси SVG и Canvas.
В дальнейшем планирую описать свои мучения с CANVAS и перевода работу с объектами на SVG, о совмещениеи объектов на карте и в списке, а также о том, для чего все это было нужно.
