How much math does it take to sign a polygon in the Yandex.Maps JS API

    In the Yandex.Maps JS API, it is possible to create various objects on the map. One of them is the polygon, with which you can improve the interactivity of the user map: highlight individual areas or display the location of a non-point object. For example, this way you can show the construction plan of a new quarter or pizza delivery area.

    Users of the Yandex.Maps API have long had a question about adding signatures on top of polygons. People offered tricky solutions to add a signature to the object in the right place, hide it, repaint it, etc., but such decisions turned out to be complex and inflexible.

    For example, the Yandex Research Department came to us with a request to write a convenient tool for signing polygons after they did some research on a world map.


    Mappings of regional words from the Dahl dictionary, that is, words that are searched much more often than the Russian average.

    In fact, the task turned out to be nontrivial. Just imagine, for each polygon you need to determine a well-suited center for displaying the signature, on each scale to determine whether the signature fits, whether it should be hidden on the selected zoom, change the styles on each zoom, again recalculate everything. That is, to make infographics not very complicated, you need to sweat a lot and prepare a lot of additional data.

    Creating labels for polygons is one of the routine tasks. You can sit and draw everything in Photoshop, but it turns out as flexible as possible:

    • Any changes to the content (values ​​in the signatures, color) will lead to a change in all signatures, it will be necessary to draw each one again.
    • Full interaction with the map includes a change of scale, for which it is not always possible to place readable text on the map in a polygon. The size of the polygon may not be enough to fully display the signature at certain scales, therefore it is necessary for each to draw signatures of different sizes.

    In image editors, it’s quite difficult to make the signature interactive, it’s much easier to specify an array of points for polygons, a template for the future signature and get a ready visualization.

    Displaying the most popular words in queries about different countries

    As a result, we decided to create a module that will solve the problems of users with signing polygons and provide freedom in its customization.

    Choosing an Algorithm to Determine the Right Signature Center


    One of the main tasks facing us was to determine the most suitable center for displaying a signature, so that the user can get a finished result without additional settings.

    There are several algorithms for solving the center search problem:

    Calculation of the centroid position


    This is the very first thing that comes to mind. In mathematics and physics, the centroid (the geometric center of a plane figure) is the arithmetic mean of all points.
    Implementing a centroid search is quite simple and the algorithm itself is fast. That would seem to be all, but if the figure is not a convex polygon or has a hole, then the point may fall outside the figure or fall into the wrong place for the signature to be displayed.


    This is the result of determining the centroid. It can be seen that the points on the Khabarovsk and Kamchatka territories fell into a place unfavorable for displaying the signature.

    Pole of inaccessibility or the point of the largest inscribed circle




    The problem of finding such a point has already arisen for many, therefore, there are various algorithms for finding the pole of inaccessibility, but, unfortunately, the published solutions require complex implementations and work too slowly to be able to put them into practice.

    The first thing, after studying the theory, you are always looking for ready-made solutions. So, we were lucky to find interesting things from the developers of Mapbox .

    They looked at several solutions for finding the inaccessibility pole, faced a number of problems and, inspired by one of the algorithms, were able to create their own, which eliminates errors, speeds up the search and increases the accuracy of obtaining a high-quality result.

    How is the search


    The algorithm is based on a tree of quadrants . That is, for the studied polygon, a region (quadrant) is constructed in which the polygon is completely placed. Further, this region is divided into four equal parts, and so on recursively with each quadrant.



    Research continues only in cells satisfying the condition. A cell is considered suitable if the sum of the distance from its center to the edge of the polygon and the radius of the circle describing the cell are greater than the previous calculations in quadrants.



    The centroid algorithm is also used inside this module as a fallback: if the found inaccessibility pole does not satisfy the required accuracy.
    Details are described here .

    The result of the algorithm




    You can see how the accuracy of the algorithms differs: the “center” on the “problem” polygons has become much better suited for the location of the signature:

    • Red dots - centroid
    • Greens - Pole of Inaccessibility



    After choosing an algorithm for finding the “center” of the polygon, we began work on the signing module.

    Module operation algorithm


    Signing a polygon occurs in several stages.
    The module is given an input to the collection, in which there are vertices of the polygons for signing.

    First, the coordinates of each polygon are passed through the module for finding the inaccessibility pole, and the coordinates of the point where the signature will be located are obtained at the output. The module will apply this center to all zooms if there was no redefinition of the center using a special option. The values ​​of the center of the polygon are cached together with the status on the signature capacity, so as not to calculate them more than once on the same zoom.



    Next, we are faced with the task of understanding whether the signature fits into the polygon.
    The module takes out a signature template and creates an HtmlElement based on it .

    objectManager.add({
          ...
          options: {
                labelLayout: '

    {{properties.name}}

    ' }, properties: { name: 'nameOfMyPolygon' } });



    Then the module waits for the images to be loaded from the tags, if any, and using getBoundingClientRect (), the sizes of this signature are calculated. Unfortunately, there are no methods that could tell about the size of an element not inserted into the DOM. Therefore, you must first render the signature. And in order to prevent “flickering” (showing and hiding the signature) when receiving the size, it is drawn in a special container that is hidden from the eyes of users.



    Since the module supports various options, such as a center offset or display error, they are applied first, and then it is checked whether the signature fits.

    objectManager.add({
          ...
          options: {
                labelLayout: '

    {{properties.name}}

    ', labelOffset: [80, -50] }, properties: { name: 'nameOfMyPolygon' } });



    The center of the signature is presented in the form of geographical coordinates, and the dimensions of the signature element in pixels, therefore, the geographical coordinates of the center are translated.
    Further from this center the width and height of the element are laid aside, the error in the calculation is applied, if it was indicated.

    objectManager.add({
          ...
          options: {
                labelLayout: '

    {{properties.name}}

    ', labelOffset: [80, -50], labelPermissibleInaccuracyOfVisibility: 10 }, properties: { name: 'nameOfMyPolygon' } });



    The resulting coordinates are translated into geographical ones and it is checked whether the signature fits into the polygon.



    All this happens for each zoom and for two types of signatures, which are described in more detail in the next part.

    Module features


    After looking at the most unpleasant problems that webmasters face, we made a number of options that will help you conveniently configure the module to suit your personal needs.

    One of the important tasks was to make a convenient way to insert a layout into a polygon. Using a special option, you can specify an HTML layout as a string that supports the basic syntax of the Twig / Django Templates template languages.

    Each polygon has two types of signatures: main and small.



    This is done in order to display a small copy of the main signature, in case it does not fit.

    Each signature belongs to one polygon through which the signature parameters are managed.

    In order to be able to control the signature settings at various scales, additional options were introduced. If the user is not satisfied with the standard definition of the signature center, then you can set the necessary coordinates in which you want to see the signature.


    On the left - the automatic center, on the right - set to the coordinates [72, 92]

    You can also set the indentation from the position of the signature and the display error, the value of which means how much signature is allowed to go beyond the boundaries of the polygon.


    Indent by 30px from above and to the left.


    Accuracy at 25px.

    It was not without styles, it is possible to change the size and color of the text or set the value of the class attribute.

    All these signature parameters can be configured for each zoom or set one value for all scales.

    All this is necessary so that the user can customize the behavior of the module.
    Here is the entire list of possible options.

    The events did not go unnoticed . All events that happened with the signature (clicking, hovering ...) are forwarded to the parent polygon and correspond to the basic events in the API, you just need to add a “label” in front of them .

    To quickly change the signature visibility, a special state was created , which every polygon has. Having received it through an instance of the module, we can change the type of signature, or even hide it completely. For example, you want to appear on polygons in which the main signature did not fit, when you hover over its reduced copy.
    Also, through this state, you can get the current type of the displayed signature or the coordinates in which the signature is located.

    Solution Design and Interface


    Often, the text is one of the main parts of the signature, so we paid special attention to it.

    In order for the signature to be well read at the intersection with the borders of regions and on translucent polygons, it was necessary to separate it from the background by a stroke. We made two standard styles that are suitable in most cases:


    Images on top: plain text, no strokes
    Images on the bottom: two standard styles of the module

    Multi-line labels are not very readable when aligning text to the left, so the center alignment was set to default.



    Since the signature layout can be set as an arbitrary html, it is not difficult to add images to the signatures - this is useful, for example, to create a weather forecast on a map or to visualize data with charts.



    A flexible layout of signatures is also useful for infographics, for example, showing flags of countries of the world or coats of arms of regions.



    So what did we get


    • The module can accept any kind of signature.
    • The module itself can determine the appropriate place for the signature and allows the user to control its position using indents or exact coordinates.
    • The signature can be customized style, color and size of the text.
    • The user can change the visibility of signatures.
    • The user can set custom parameters for all acceptable scales, as well as for individual ones.

    Conclusion


    We decided to dwell on the basic usage scenarios that could satisfy the basic needs for convenient signature creation, but if you have any wishes for the module to work, we will definitely consider them.

    For those who became interested


    To start using the module, you need to perform a couple of points from the instructions in this repository .

    Example


    jsfiddle.net/51qtdx3a/5

    We are always happy to receive suggestions and feedback, for all questions write to us in technical support or leave suggestions in the comments. We hope that our tools will make the life of the webmaster a little easier and open up new horizons for you in the visualization of data on the map.

    Also popular now: