This article has participated in the good article call order activity, click to see: [back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!]

preface

Dear coder, I again come, like a graphics programmer 👩 💻, before a few articles have been teaching you how to draw maps, HuaShe chart, fireworks 🎆, do graphics is such, of course not, a very simple question, if I drew 100000 points in the canvas, move the mouse on the canvas, which close to the point, Which point is highlighted. I know you can loop through it. You can loop through hundreds of points. If it’s tens of thousands or even millions of points you can loop through it. You want the user to die? And that brings us to our hero of the day here he is Rbush

RBUSH

So let’s look at the definition, what problem does rbush solve for us?

RBush is a high performanceJavaScript library for indexing points and rectangles in two dimensions. It is based on an optimized R-Tree data structure and supports large volume inserts. A spatial index is a special data structure for points and rectangles that allows you to perform queries like “all items in this bounding box” very efficiently (for example, hundreds of times faster than looping over all items). It is most commonly used for mapping and data visualization.

Look at the definition it’s based on the optimized R-Tree data structure, so what is r-tree?

R-trees are tree data structures for spatial access methods, that is, for indexing multidimensional information, such as geographic coordinates, rectangles, or polygons. A common use of R-Tree in the real world might be to store spatial objects, such as restaurant locations or polygons that make up a typical map: Streets, buildings, lakes, outline, coastline, etc., and then quickly find an answer to your query, for example, “find me all within the scope of the current position 2 km museum”, “I retrieve location 2 km within the scope of all sections” (to display them in the navigation system) or “find the nearest gas station” (although not road into account).

The key idea of R-Tree is to group nearby objects and represent them at the next higher level of the tree with their smallest bounding rectangle; R in r-tree stands for rectangle. Because all objects are inside this bounding rectangle, queries that do not intersect the bounding rectangle cannot intersect any of the contained objects. At the leaf level, each rectangle describes an object; At higher levels, aggregation includes more and more objects. This can also be seen as an increasingly rough approximation of the data set. This is a little abstract, but let’s look at a picture:

Let me elaborate on this picture:

0. First of all, we assume that all data are points in two-dimensional space. Let’s start with the region R8 in the figure, that is, the shape of data object. Don’t think of that piece of irregular shape as a single piece of data, we think of it as an area of data. In order to implement the R-tree structure, we use a minimum boundary rectangle to exactly frame the irregular region, so we construct a region: R8. R8 has the obvious feature of framing all the data in this area. The same is true for other solid lines, such as R9, R10, R12, etc. So we have a total of 12 very basic minimum rectangles. These rectangles are going to be stored in the child nodes.
1. The next step is to proceed to a higher level of processing. We find that R8, R9, and R10 are closest to each other, so we can use a larger rectangle, R3, to exactly frame those three rectangles.
2. In the same way, R15, R16 is exactly framed by R6, R11, R12 is exactly framed by R4, and so on. After all the basic minimum-bounding rectangles are framed into larger rectangles, iterate again to frame those rectangles with larger boxes.

algorithm

insert

To insert an object, the tree traverses recursively from the root node. At each step, all rectangles in the current directory node are examined and candidates are selected using a heuristic, such as selecting the rectangle that requires the least magnification. The search then descends to the page until it reaches the leaf node. If the leaf node is full, it must be split before insertion. Similarly, since exhaustive search is too expensive, heuristic methods are used to split the nodes in two. The newly created node is added to the previous layer, which can overflow again, and the overflow can be propagated up to the root node; When this node also overflows, a new root node is created and the height of the tree is increased.

search

In a range search, the input is a search rectangle (query box). The search starts at the root of the tree. Each inner node contains a set of rectangles and Pointers to the corresponding child nodes, and each leaf node contains a rectangle of the spatial object (a pointer to some spatial object can be there). For each rectangle in the node, you must determine whether it overlaps the search rectangle. If so, you must also search for the appropriate child nodes. Search recursively until all overlapping nodes have been traversed. When the leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle, and if they are within the search rectangle, their objects (if any) are placed in the result set.

Read the complex, but the community must have a big guy for us to encapsulate, do not have to write their own hand, write the estimate is not necessarily right ha ha ha.

The usage RBUSH

usage

// as a ES module
import RBush from 'rbush';
​
// as a CommonJS module
const RBush = require('rbush');
Copy the code

Create a tree 🌲

const tree = new RBush(16);
Copy the code

The next 16 is an optional, and an optional argument to RBush defines the maximum number of entries in the tree node. 9 (the default) is a reasonable choice for most applications. Higher values mean faster inserts and slower searches, and vice versa.

Insert data 📚

const item = {
    minX: 20,
    minY: 40,
    maxX: 30,
    maxY: 50,
    foo: 'bar'
};
tree.insert(item);
Copy the code

Deleting data 📚

tree.remove(item);
Copy the code

By default, RBush removes objects by reference. However, you can pass a custom equals function to compare by deletion value, which is useful when you only have a copy of the object that needs to be deleted (for example, loading from the server) :

tree.remove(itemCopy, (a, b) => {
    return a.id === b.id;
});
Copy the code

Delete all data

tree.clear();
Copy the code

Search 🔍

const result = tree.search({
    minX: 40,
    minY: 20,
    maxX: 80,
    maxY: 70
});
Copy the code

API introduction ends below 👇 begins to enter actual combat link a simple small case – canvas canvas search 🔍.

Fill the canvas with pictures

In the process of filling the canvas, here and you introduce a Canvas point API – createPattern

Canvasrenderingcontext2d.createpattern () is the method by which the Canvas 2D API creates the pattern using the specified image (CanvasImageSource). It repeats the meta image in the specified direction with the repetition parameter. This method returns a CanvasPattern object.

The first parameter is to fill the canvas with a data source which can be as follows:

• HTMLImageElement
• HTMLVideoElement
• HTMLCanvasElement
• CanvasRenderingContext2D.
• ImageBitmap.
• ImageData.
• Blob.

 class search { 
     constructor() { 
         this.canvas = document.getElementById('map') 
         this.ctx = this.canvas.getContext('2d') 
         this.tree = new RBush() 
         this.fillCanvas() 
     } 
​
     fillCanvas() { 
         const img = new Image() 
         img.src ='https://ztifly.oss-cn-hangzhou.aliyuncs.com/%E6%B2%B9%E7%94%BB.jpeg' 
         img.onload = () => { 
             const pattern = this.ctx.createPattern(img, '') 
             this.ctx.fillStyle = pattern
             this.ctx.fillRect(0, 0, 960, 600) 
         } 
    } 
 } 
Copy the code

randomRect() {
  const rect = {}
  rect.minX = parseInt(Math.random() * 960)
  rect.maxX = rect.minX + parseInt(Math.random() * 20)
  rect.minY = parseInt(Math.random() * 600)
  rect.maxY = rect.minY + parseInt(Math.random() * 20)
  rect.name = 'rect' + this.id
  this.id += 1
  return rect
}
Copy the code

loadItems(n = 100000) {
  let items = []
  for (let i = 0; i < n; i++) {
    items.push(this.randomRect())
  }
  this.tree.load(items)
}
Copy the code

memCanva() { this.memCanv = document.createElement('canvas') this.memCanv.height = 600 this.memCanv.width = 960 This.memctx = this.memcanv. getContext('2d') this.memctx. strokeStyle = 'rgba(255,255,255,0.7)'} loadItems(n = 10000) { let items = [] for (let i = 0; i < n; i++) { const item = this.randomRect() items.push(item) this.memCtx.rect( item.minX, item.minY, item.maxX - item.minX, item.maxY - item.minY ) } this.memCtx.stroke() this.tree.load(items) }Copy the code

this.ctx.drawImage(this.memCanv, 0, 0)
Copy the code

this.canvas.addEventListener('mousemove', This.handle.bind (this)) // mouseMove event handler(e) {this.clearRect() const x = e.ffsetx const y = e.ffsety this.bbox.minX = x - 20 this.bbox.maxX = x + 20 this.bbox.minY = y - 20 this.bbox.maxY = y + 20 const start = performance.now() const res = this.tree.search(this.bbox) this.ctx.fillStyle = this.pattern this.ctx.strokeStyle = 'rgba(255,255,255,0.7)' res.foreach ((item) => {this.drawrect (item)}) this.ctx.fill() this.res.innerhtml = 'Search Time  (ms): ' + (performance.now() - start).toFixed(3) }Copy the code

ctx.fillStyle = color;
ctx.fillStyle = gradient;
ctx.fillStyle = pattern;
Copy the code