Разработка векторного редактора на JavaScript (сложности и идеи)

Предыстория:

Имя большой опыт в разработке веб-сайтов (около 15 лет) и являясь программистом, я очень не люблю рутинную работу, стараюсь ее либо избегать, либо каким-то образом оптимизировать. Другими словами, если мне в какой-то момент необходимо заниматься наполнением контентом сайта (да, знаю, не царское дело программисту наполнять сайт, но случаи разные бывают), то я предпочту потратить пару часов на написание парсера входящих данных, чем часа 4 вколачивать эти данные вручную. И давно меня терзала проблема отсутствия удобного редактора для создания карт изображения. Конечно, можно нарисовать карту в Corel Draw или подобном, выгрузить в SVG и по быстрому переконвертировать в нужный формат, но меня давно интересовала возможность создания некоего редактора, который позволит, не загружая сторонние программы, прямо на сайте, по-быстрому загрузить изображение и выделить на нем нужную карту. Например, есть некое изображение здания, на котором необходимо выделить контур этажа и привязать к нему какие-то JavaScript-события или просто ссылку, вот как здесь:




Также, помимо ручного выделения контура объекта, мне бы хотелось иметь инструмент, аналогичный Magic Wand в Photoshop, чтобы ткнул мышкой и у тебя появился готовый контур. Несмотря на то, что уже несколько лет натыкаюсь на различные редакторы карт (как on-line, так и off-line), подобной функции в них не нашел. Ну, раз нет – будем писать сами.

Хочется сразу предупредить, поскольку в итоге нашел заказчика на коммерческий продукт, то полноценных исходников, к сожалению, не будет, но идеи и сложности, возникшие при разработке, постараюсь описать как можно более подробно, мало того, я не специализируюсь на разработке графики и интерфейсов, поэтому какие-то «откровения» могут показаться смешными или даже глупыми, тем не менее:

Определение функционала редактора:

1. Создание контура вручную, а также иметь возможность редактировать ранее созданные контуры;
2. Хотя HTML тег MAP – AREA – SHAPE поддерживает несколько типов форм выделенной области, было решено остановиться только на создании сложных контуров с помощью POLY;
3. Собственно, что было интересно мне, как программисту, это выделение области со схожими цветами, с помощью одного клика мыши.

CANVAS – то, что нужно?

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

Выбор алгоритма обхода контура:

Перепробовав несколько вариантов алгоритмов обхода контура, в конечном итоге выбрал Moor Neighborhood. На мой взгляд, этот алгоритм удачно совмещает скорость работы и достаточную простоту реализации.

Итак:


Тестовое изображение, для работы с контуром


Выделение контура с прямыми сторонами


Выделение искривленного контура

Как видим, алгоритм обхода контура отлично справляется и выделяет все, что нужно, при этом видим, что на относительно небольшой контур, требуется почти 300 точек для прямых линий и почему-то на 50 точек меньше, если контур повернут вокруг своей оси.

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

Оптимизация готового контура:

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

Выбор узловых точек:

Решение, лежащее на поверхности:

1. Берем точку, добавляем ее в массив узловых точек (не точек контура);
2. Последовательно обходим точки от стартовой, измеряя угловое расстояние между первоначальной и текущей, если угловое расстояние больше или меньше некоего (определенного опытным путем), то эта точка является новой стартовой, добавляем ее в массив\ узловых точек;

Это решение работает, но вот расчет углового расстояния терзало душу наличием «тяжелых» функций работы с углами. Поэтому было решено посмотреть на существующие «велосипеды» и вот забытое решение из школьной математики: скалярное произведение векторов.

Берем его за основу – алгоритм работает отлично и в разы быстрее.

Смотрим результат:

13 точек – вполне устраивает.


61 точка?! Но почему?!

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


Жирным выделена теоретическая прямая, а разница бьет в глаз.

Проблему временно решил введением некоего множителя, позволившего пропорционально увеличить расстояние между точками (с сохранением угловых расстояний), что позволило сгладить разницу между точками и сделать расчет более точным, в результате получаем 23 точки вместо 61, больше чем для прямых линий, но для моих целей пока достаточно.

Подведя итог:

Редактор готов, позволяет загружать изображение, масштабировать, двигать мышкой, добавлять новые объекты и редактировать существующие, работает все на странной смеси SVG и Canvas.

В дальнейшем планирую описать свои мучения с CANVAS и перевода работу с объектами на SVG, о совмещениеи объектов на карте и в списке, а также о том, для чего все это было нужно.

UPD:
Использовал алгоритм Рамера-Дугласа-Пекера для минимизации количества точек, результат стал гораздо лучше, узловые точки определяются точнее. Спасибо LevshinO за идею!

UPD:
Выложена вторая часть истории о создании редактора, в том числе со ссылкой на исходники.