Markers are a good thing. Useful in reasonable quantities. When there are too many of them, the benefits disappear. What to do if you want to mark on the map the search results, in which tens of thousands of objects? In the article I will tell how we solve this problem on the WebGL-card without prejudice to its appearance and performance.

Prehistory

In 2016, 2GIS launched its first project on WebGL - Floors: three-dimensional floor plans of buildings.

Floors of the Novosibirsk shopping center Aura

Immediately after the release of the Floors, our team began developing a full-fledged three-dimensional mapping engine on WebGL. The engine was developed in conjunction with the new version of 2gis.ru and is now in the status of a public beta .

Red Square, drawn on WebGL. Building plans are now built right into the map.

The task of the generalization of signatures

Anyone who wants to write their own mapping engine, sooner or later will face the problem of placing signatures on the map. There are many objects on the map, and it is impossible to sign each one so that the signatures do not overlap with each other.

What will happen if in Novosibirsk to sign all objects at once?

To solve this problem, generalization of signatures is necessary. Generalization in a general sense - the transformation of map data in such a way that they are suitable for display on small scales. It can be done by different methods. For signatures, the method of selection is usually used: from the total number, a subset of the highest priority signatures is chosen that do not overlap with each other.

Signature priority is determined by its type, as well as the current scale of the map. For example, with a small scale, signatures of cities and countries are needed, and with a large scale, signatures of roads and house numbers become more important. Often the priority of the name of a settlement is determined by the size of its population. The larger it is, the more important the signature.

Generalization is required not only for signatures, but also for markers that mark search results on the map. For example, when searching for "store" in Moscow there are more than 15,000 results. To mark them all on the map at once is obviously a bad idea.

All shops of Moscow on the map. Without generalization can not do here

Any user interaction with the map (movement, zooming, rotation and tilt) changes the position of the markers on the screen, so the generalization must be able to recalculate on the fly. Therefore, it must be fast.

In this article, using the example of generalization of markers, I will show different ways to solve this problem, which were used in our projects at different times.

General approach to generalization

1. Project each marker into the screen plane and calculate the sound for it - a rectangular area that it occupies on the screen.
2. Sort the markers by priority.
3. Sequentially examine each marker and place it on the screen if it does not intersect with other markers placed in front of it.

With paragraph 1, everything is clear - it's just a calculation. With point 2, we are also lucky: the list of markers that comes to us from the backend is already ordered by the priority of the search algorithms. At the top of the issue get the most relevant results that are most likely to be of interest to the user.

The main problem is in point 3: the time it takes to calculate the generalization can strongly depend on how it is implemented.

To search for intersections between markers, we need some data structure that:

1. Stores bounds of markers added to the screen.
2. It has a insert(marker) method to add a marker to the screen.
3. It has a collides(marker) method to check the marker for intersection with those already added to the screen.

Consider several implementations of this structure. All further examples will be written in TypeScript, which we use in most of our projects. In all examples, markers will be represented by objects of the following form:

 interface Marker { minX: number; maxX: number; minY: number; maxY: number; } 

All considered approaches will be implementations of the following interface:

 interface CollisionDetector { insert(item: Marker): void; collides(item: Marker): boolean; } 

For performance comparison, the execution time of the following code will be measured:

 for (const marker of markers) { if (!impl.collides(marker)) { impl.insert(marker); } } 

The markers array will contain 100,000 30x50 items randomly placed on a 1920x1080 size plane.

Performance will be measured on Macbook Air 2012.

The tests and code samples provided in the article are also posted on GitHub .

Naive implementation

To begin, consider the simplest option when the marker is checked for intersection with the rest in a simple cycle.

 class NaiveImpl implements CollisionDetector { private markers: Marker[]; constructor() { this.markers = []; } insert(marker: Marker): void { this.markers.push(marker); } collides(candidate: Marker): boolean { for (marker of this.markers) { if ( candidate.minX <= marker.maxX && candidate.minY <= marker.maxY && candidate.maxX >= marker.minX && candidate.maxY >= marker.minY ) { return true; } } return false; } } 

Calculation time of generalization for 100,000 markers: 420 ms . Too much. Even if the calculation of generalization goes in the web worker and does not block the main thread, such a delay will be noticeable, especially since this operation must be performed after each movement of the map. Moreover, on mobile devices with a weak processor, the delay can be even greater.

Implementation using R-tree

Since in a naive implementation, each marker is checked for intersection with all the previous ones, in the worst case, the complexity of this algorithm is quadratic. You can improve it by applying the R-tree data structure. As an implementation of an R-tree, take the RBush library:

 import * as rbush from 'rbush'; export class RTreeImpl implements CollisionDetector { private tree: rbush.RBush<Marker>; constructor() { this.tree = rbush(); } insert(marker: Marker): void { this.tree.insert(marker); } collides(candidate: Marker): boolean { return this.tree.collides(candidate); } } 

Calculation time of generalization for 100,000 markers: 173 ms . Much better. We applied this approach in the Floors (this was mentioned in my previous article ).

Visualize the storage of points in the R-tree. Hierarchical division of the plane into rectangles allows you to quickly narrow the search area and not to iterate over all objects

Implementing with a collision buffer

Drawing a map is a much more difficult task than drawing a plan for one building. This is manifested in generalization. Even in the largest shopping centers in the world, there are rarely 1,000 organizations on one floor. At the same time, a simple search query in a large city can return tens of thousands of results.

When we started developing the WebGL map, we began to think: is it possible to further accelerate the generalization. An interesting idea was then suggested to us by the stellarator working for us: instead of an R-tree, use a buffer in which to store the state of each pixel of the screen (busy or not busy). When inserting a marker on the screen, “paint over” the corresponding place in the buffer, and when checking the possibility of insertion, check the pixel values ​​in the required area.

 class CollisionBufferByteImpl implements CollisionDetector { private buffer: Uint8Array; private height: number; constructor(width: number, height: number) { this.buffer = new Uint8Array(width * height); this.height = height; } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { buffer[i * this.height + j] = 1; } } } collides(candidate: Marker): boolean { const { minX, minY, maxX, maxY } = candidate; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { if (buffer[i * this.height + j]) { return true; } } } return false; } } 

Calculation time of generalization for 100,000 markers: 46 ms .

Why so fast? At first glance, this approach seems to be naive, and the nested loops in both methods are not similar to fast code. However, if you take a closer look at the code, you will notice that the execution time of both methods does not depend on the total number of markers. Thus, at a fixed size of the WxH markers, we obtain the labor intensity O (W * H * n), that is, linear!

Optimized collision buffer approach

It is possible to improve the previous approach both in speed and memory, if we make it so that one pixel is represented in memory not by one byte, but by one bit. The code after this optimization, however, is noticeably more complicated and overgrown with some amount of bitwise magic:

 export class CollisionBufferBitImpl implements CollisionDetector { private width: number; private height: number; private buffer: Uint8Array; constructor(width: number, height: number) { this.width = Math.ceil(width / 8) * 8; this.height = height; this.buffer = new Uint8Array(this.width * this.height / 8); } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; if (start === end) { buffer[start] = buffer[start] | (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { buffer[start] = buffer[start] | (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { buffer[i] = 255; } buffer[end] = buffer[end] | (255 << (8 - (maxX & 7))); } } } collides(marker: Marker): boolean { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; let sum = 0; if (start === end) { sum = buffer[start] & (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { sum = buffer[start] & (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { sum = buffer[i] | sum; } sum = buffer[end] & (255 << (8 - (maxX & 7))) | sum; } if (sum !== 0) { return true; } } return false; } } 

Calculation time of generalization for 100,000 markers: 16 ms . As we see, the complication of logic justifies itself and allows us to accelerate the calculation of generalization almost three times more.

Collision Buffer Limitations

It is important to understand that the collision buffer is not a complete replacement for the R-tree. It has much less features and more restrictions:

1. It is impossible to understand exactly what the marker intersects with. The buffer only stores data on which pixels are occupied and which are not. Therefore, it is impossible to implement an operation that returns a list of markers intersecting with the given.
2. Cannot delete previously added marker. The buffer does not store data about how many markers are in a given pixel. Therefore, it is impossible to correctly implement the operation of removing the marker from the buffer.
3. High sensitivity to the size of the elements. If you try to add to the collision buffer markers that occupy the entire screen, the performance drops sharply.
4. Works in a limited area. The size of the buffer is set when it is created, and it is impossible to place a marker in it that goes beyond this size. Therefore, when using this approach, it is necessary to manually filter out markers that do not fall on the screen.

All these restrictions did not prevent the solution of the task of generalization of the markers. Now this method is successfully used for markers in beta 2gis.ru.

However, to generalize the main signatures on the map, the requirements are more complex. For example, for them it is necessary to do so that the POI icon could not “kill” its own signature. Since the collision buffer does not distinguish exactly with what intersection occurred, it does not allow implementing such logic. Therefore, they had to leave the decision with RBush.

Conclusion

The article shows the path we have gone from the simplest solution to the one used now.

The use of the R-tree was the first important step that allowed us to speed up the naive implementation. It works fine in Floors, but in fact we use only a small part of the capabilities of this data structure.

By abandoning the R-tree and replacing it with a simple two-dimensional array, which does exactly what we need, and nothing but this, we have an even greater increase in productivity.

This example showed us how important it is, choosing a solution for a problem from several options, to understand and be aware of the limitations of each of them. Restrictions are important and useful, and you should not be afraid of them: if you skillfully limit yourself to something irrelevant, you can get great benefit in return where you really need it. For example, to simplify the solution of a problem, or to protect yourself from a whole class of problems, or, as in our case, at times improve performance.