Разработка векторного редактора на 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:
    Выложена вторая часть истории о создании редактора, в том числе со ссылкой на исходники.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 15

      +3
      А как же код? А репозиторий на гитхаб?
        0
        поскольку в итоге нашел заказчика на коммерческий продукт, то полноценных исходников, к сожалению, не будет

        Одно из условий заказчика, не выкладывать исходники в открытый доступ. В принципе, мне было бы достаточно идей и описания ошибок, которые не стоит повторять.
          0
          А дать ссылку на сайт, где это всё реализовано? Можно в ЛС.
        +1
        Возможно, пригодится для оптимизации контуров: github.com/mourner/simplify-js
          0
          Спасибо огромное, то, что нужно! Я на эти расчеты кучу времени угробил, поскольку даже не знал, в какую сторону копать.
            0
            Надеюсь, что все же получится увидеть ваш редактор в открытом доступе когда-нибудь. :-)
              0
              Переписал процедуру «чистки» точек на алгоритм, используемый по вашей ссылке — точность практически совпадает для контуров любой сложности. Спасибо огромное еще раз!
          0
          Зачем планируете переводить работу с объектами на SVG?
            0
            Потому что как показала практика, работа с объектами в CANVAS дико геморройная.

            Пример: чтобы определить, что мы навели мышку на контур сложной формы, нарисованный в canvas, необходим вагон плясок с бубном. Либо мы должны хранить данные в MAP для картинки, которая лежит поверх canvas (но тогда проблемы с фиксацией наведения собственно на canvas и оформление различных подсветок), либо сойти с ума и писать на JS проверку на попадание точки в контур самостоятельно. В случае же с SVG, вешаем на готовый контур-объект любые события, хоть подсветку, хоть переход по ссылке, описываем оформление в CSS и все, готово. Кроме того, если объектов будет много — их обработчик на JS тачнет ощутимо томрозить, а в случае с SVG, мы работаем только с текущим объектом и не паримся.

            Но в итоге ситуация выглятит так: вся работа с объектами, например, выбор, подсветка — проходит через SVG, редактирование же происходит в canvas, поскольку там реально проще получить кусок картинки и/или перевести кусок в массив для дальнейшей работы.
              0
              Когда то давно писал подобный редактор
                0
                Да, я видел ваши статьи и вот цитата из одной из них:
                «Почти всё готово, осталось немножко всякой фигни по мелочам». Прошло три года. Сейчас в голове — «Вот теперь точно почти всё готово!».

                Понятно, что вы не 3 года без отрыва работали над редактором, но у меня не было ни времени, ни особого желания биться головой о canvas, когда под руками лежит SVG, где все гораздо проще.
                +1
                Конечно, если писать велосипед на каждый маленький алгоритм, то работа с канвасом будет гемморойной. Почему было не взять один из готовых фреймворков, которые дают возможность работать с более продвинутыми примитивами? Например KineticJS. Такой редактор пишется за пару дней.
                  0
                  Да, если знать, например, про KineticJS. Именно поэтому я и написал этот пост, чтобы получить как можно больше полезной информации и чтобы читающие избежали моих ошибок.
              +2
              Делал похожий редактор на основе проекта: github.com/summerstyle/summer, но без автоопределения контуров. Интересно было бы потыкать в демо вашего редактора. :)
                +1
                В этом редакторе мне понравился не только функционал, но и то, что его разработчик — девушка. А так — да, SVG редактор, все что нужно типовое — поддерживает, включая выгрузку в HTML. Я его, кстати, всерьез рассматривал как основу, но в итоге отказался, слишком тяжеловесный, мне нужно было что-то легче.

              Only users with full accounts can post comments. Log in, please.