Development of a vector editor on JavaScript (complexity and ideas)

Background:

The name is a great experience in website development (about 15 years) and being a programmer, I really dislike routine work, I try to either avoid it or optimize it in some way. In other words, if at some point I need to fill the site with content (yes, I know, it’s not a royal business for a programmer to fill a site, but there are different cases), then I would prefer to spend a couple of hours writing the incoming data parser than 4 hours data manually. And long ago, I was tormented by the problem of the lack of a convenient editor for creating image maps. Of course, you can draw a map in Corel Draw or similar, upload to SVG and quickly convert it to the desired format, but I was interested for a long time in the possibility of creating a certain editor that allows you to quickly upload an image directly on the site, without loading third-party programs. on it the desired card. For example, there is a certain image of a building on which you need to select the outline of the floor and attach some JavaScript-events to it or just a link, like this:




Also, in addition to manually selecting the contour of the object, I would like to have a tool similar to the Magic Wand in Photoshop, so that I would poke the mouse and you would have a ready-made contour. Despite the fact that for several years I’ve come across various map editors (both on-line and off-line), I haven’t found a similar function in them. Well, if not, we will write it ourselves.
')
I would like to immediately warn you, because as a result I found a customer for a commercial product, unfortunately there will be no full source code, but I will try to describe the ideas and difficulties encountered in the development in as much detail as possible, and I do not specialize in the development of graphics and interfaces. therefore, some “revelations” may seem ridiculous or even stupid, however:

Definition of editor functionality:

1. Creating a contour manually, as well as being able to edit previously created contours;
2. Although the HTML MAP - AREA - SHAPE tag supports several types of forms of the selected area, it was decided to stop only on creating complex contours using POLY;
3. Actually, what was interesting to me, as a programmer, is the selection of an area with similar colors, with a single mouse click.

CANVAS - what you need?

Since I already had experience with the CANVAS tag and presented its capabilities, it was decided to stop at it (as it turned out, this was a mistake, the development of the editor was slow for a decent amount of time).

Select contour traversal algorithm:

Having tried several variants of contour traversal algorithms, I finally chose the Moor Neighborhood . In my opinion, this algorithm successfully combines the speed of work and sufficient ease of implementation.

So:


Test image for working with the contour


Outline selection with straight sides


Curved contour selection

As you can see, the contour traversal algorithm does an excellent job and highlights everything that is needed, while we see that a relatively small contour requires almost 300 points for straight lines and for some reason less than 50 points if the contour is rotated around its axis.

In principle, now this contour can be memorized and worked with it, but the large amount of data confuses even for a small contour.

Optimization of the finished circuit:

The following scheme of work with the contour was chosen: first we create a contour from points and delete unnecessary ones, with the exception of the nodal points (or points of change of direction). On the one hand, double work occurs, on the other hand, this scheme simplifies debugging the mechanism for removing unnecessary points.

Selection of nodal points:

Surface solution:

1. Take a point, add it to an array of node points (not contour points);
2. Sequentially we go around the point from the starting one, measuring the angular distance between the original and the current one, if the angular distance is more or less than some (determined experimentally), then this point is a new starting one, add it to the array \ nodal points;

This solution works, but here the calculation of the angular distance tormented the soul with the presence of "heavy" functions of working with angles. Therefore, it was decided to look at the existing "bikes" and here is the forgotten solution from school mathematics: the scalar product of vectors .

We take it as a basis - the algorithm works fine and much faster.

See the result:

13 points - quite satisfied.


61 points ?! But why?!

But why: I somehow forgot that, in spite of the large resolutions of monitors, retina, etc., the line on the screen is in fact a broken set of points (after all, 20 years ago, I stuck my tongue out and mastered drawing lines using the Bresenham algorithm ...):


Bold highlighted theoretical straight, and the difference beats in the eye.

The problem was temporarily solved by introducing a certain multiplier, which allowed proportionally increasing the distance between points (while preserving the angular distance), which allowed smoothing the difference between points and making the calculation more accurate, resulting in 23 points instead of 61, more than for straight lines, but for my purposes for now enough.

To summarize:

The editor is ready, allows you to load an image, scale it, move it with a mouse, add new objects and edit existing ones, everything works on a strange mixture of SVG and Canvas.

In the future, I plan to describe my torment with CANVAS and the translation of work with objects on SVG, about combining objects on the map and in the list, as well as about what all this was needed for.

UPD:
I used the Rahmer-Douglas-Pecker algorithm to minimize the number of points, the result was much better, the nodal points are determined more accurately. Thanks LevshinO for the idea!

UPD:
The second part of the story about the creation of the editor is published, including with reference to the source code.