Location-based search

In many applications, it is essential to search for cells based on their spatial properties. For example, you might want to find all cells within a given rectangle. A typical approach is to iterate over all cells and check if they intersect with the rectangle.

JointJS+ provides a SearchGraph class that is optimized for spatial queries. You can read about technical specification of the class in the API documentation.

What is SearchGraph?

It's a drop-in replacement for the dia.Graph class that is optimized for querying and searching cells based on their spatial properties.

If you need to improve the performance of spatial queries in your application, you can simply replace the dia.Graph class with the SearchGraph class. Since the search API is widely used internally, this swap can boost your application's performance without requiring changes to your existing code

Here’s a list of features that can benefit from using the SearchGraph class:

• to find elements under the element being dragged (e.g., for embedding)
• to find elements under the link being dragged (e.g., for snapLinks)
• to find elements and links under the selection region (e.g., in ui.Selection)
• the findCellViewsAtPoint() and findCellViewsInArea() paper methods (and its element and link counterparts)

How does SearchGraph work?

The SearchGraph class uses a quadtree to index cells by their bounding boxes. The quadtree is a tree data structure in which each internal node has exactly four children. The tree is used to partition a two-dimensional space into smaller regions. This allows for more efficient search operations (e.g., finding all cells within a given area).

Lazy vs Eager mode

In the eager mode (default) the quadtree is updated automatically when the graph is modified and it is ready for search queries at any time. In the lazy mode, the quadtree updates are postponed until the first search is performed.

You can switch the modes to optimize the performance of your application.

• Use eager mode when queries are frequent and data needs to be constantly up-to-date.
• Use lazy mode when changes are frequent, but queries are less common, or you want to delay the cost of updating until necessary.

You can enter the lazy mode of the quadtree by calling the setQuadTreeLazyMode() method.

// enter `lazy` mode
searchGraph.setQuadTreeLazyMode(true);

// enter `eager` mode
searchGraph.setQuadTreeLazyMode(false);

This is a list of methods that triggers the quadtree update:

• findCellsInArea()
• findCellsAtPoint()
• findCellsUnderElement()
• findElementsInArea()
• findElementsAtPoint()
• findElementUnderElement()
• findLinksInArea()
• findLinksAtPoint()
• findLinkUnderElement()

The quadtree is invalidated when the graph is modified (e.g., a cell is added or removed).

• add and remove events
• change event with position, size, angle, ports, source, target or vertices attribute changes.
• the invalidateQuadTree() method is called

Here is an example of how the lazy mode works:

/* Lazy mode */

// Rebuilds the quadtree and query the cells in the area
graph.findCellsInArea({ x: 0, y: 0, width: 100, height: 100 });

// Queries the cells in the area
graph.findCellsInArea({ x: 0, y: 0, width: 110, height: 110 });

// Invalidates the quadtree
graph.addCell(myElement1);

// Rebuilds the quadtree and query the cells in the area
graph.findCellsInArea({ x: 0, y: 0, width: 120, height: 120 });

// Does not invalidate the quadtree
el.attr('body/fill', 'red');

// Invalidates the quadtree
el.position(20, 20);

Complexity

While the search operations in the dia.Graph class have a time complexity of O(n), the SearchGraph class improves this to O(log n) by using a quadtree.

However, building the quadtree introduces some overhead, making the SearchGraph class particularly useful when you need to perform multiple spatial queries on the same graph.

In lazy mode, the quadtree is built on the first query, with a complexity of O(n log n). In eager mode, insert and remove operations are O(log n), and the update operation, which involves both removing and re-inserting, also has a complexity of O(log n). Note that in the current implementation, the nodes in the quadtree are not merged when cells are removed, so the quadtree may become unbalanced over time (invalidating will force a rebuild).

The memory overhead of the quadtree is O(n).

Examples

Find all elements in a given area

A common use case for the SearchGraph class is in a diagram editor, where you need to continuously find all elements within the selection region as the user drags the mouse.

Open Sandbox

Find the nearest element

Finding nearby elements is also useful in applications that require collision detection or snapping elements to a grid.

Open Sandbox