4
\$\begingroup\$

I have a flat list of rectangles, in the following format (id, x co-ord, y co-ord, height and width):

[ { id: 4206, x: 360, y: 700, width: 60, height: 50 } ,
   { id: 6621, x: 1260, y: 1100, width: 60, height: 50 } ]

I want to index this by range of X values, and then use that indexed object to speed up a search for a point inside.

My full code is here:

// arbitrary setup, no need to review
const grid = [];
const height = 50;
const width = 60;
let index = 0;
for (let row = 0; row < 300; row++) {
  for (let col = 0; col < 300; col++) {
    grid[index] = {
      id: index,
      x: width * col,
      y: height * row,
      width,
      height
    };
    index++;
  }
}
// try and find these points
const points = [{
  x: 400,
  y: 700
}, {
  x: 1300,
  y: 1105
}]

// body - please review approach, style less important

const indexedGrid = grid.reduce((acc, curr) => {
  if (curr.x === undefined) return acc;
  if (acc[curr.x]) {
    acc[curr.x].shapes.push(curr);
    acc[curr.x].endEdge = Math.max(acc[curr.x].endEdge, curr.width + curr.x)
  } else acc[curr.x] = {
    shapes: [curr],
    startEdge: curr.x,
    endEdge: curr.width + curr.x
  };
  return acc;
}, {})
const indexedEdges = Object.values(indexedGrid).map(val => ({
  start: val.startEdge,
  end: val.endEdge
}));
const shapesContainingPoints = points.map(
  (point) => ({
    point,
    xRange: indexedEdges.filter(
      edge => (point.x >= edge.start && point.x < edge.end)
    )
  })
).map(
  pointWithRange => indexedGrid[pointWithRange.xRange[0].start].shapes.filter(
    shape => {
      return (pointWithRange.point.y >= shape.y && (pointWithRange.point.y < (shape.y + shape.height)))
    }
  )
);

//footer - purely to show results in the this question, no need to review
console.log(shapesContainingPoints)

I'm fully aware this code could be tidied up a lot, but the main thing I was hoping to ascertain, is if this 'index and search' pattern suits the following use case.

I'm drawing a load of rectangles in a html canvas element, and I want to be able to find which rectangle was clicked on using the x, y co-ords of the mouse. So I plan to create a flat list of the squares, and then index them by their X value. And from that X value, look along the row, filtering by Y value.

Currently the data only includes perfectly tiling rectangles, but in the future I may have to handle an alternating offset (every other row is shifted by a small value) or other less standard layouts.

Here are some example grids (all right angled) that I need to handle:
https://algorist.com/images/figures/bin-packing-R.png
https://i.stack.imgur.com/JG3iT.png
https://codeincomplete.com/articles/bin-packing/packed.png

I have no plans to have the number, size or position of the rectangles to change over time. I don't have a good grasp of quite how many total rectangles I will need to look over, but I'm expecting anything from 4 to 4000 say.

But it feels very clunky (overly complicated, and thus hard to comprehend/maintain), and that there should be a better approach to this problem? I'm also interested in performance, but that's secondary to maintainability at the moment.

If there is not a better alternative, is there anyway of improving my current approach?

\$\endgroup\$
12
  • \$\begingroup\$ @Peilonrayz, the rectangles are static and I'm aiming for maintainability over performance (but would like to keep an eye on both). No idea how many rectangles, so I've speculated at 4 to 4000. \$\endgroup\$ – Pureferret Mar 10 at 12:31
  • 2
    \$\begingroup\$ Are you looking for something like kd-trees? \$\endgroup\$ – Neil Mar 12 at 5:02
  • \$\begingroup\$ @neil I think so? \$\endgroup\$ – Pureferret Mar 12 at 8:35
  • 1
    \$\begingroup\$ @neil, I don't even mean arbitrary angles. here are some example grids (all right angled): algorist.com/images/figures/bin-packing-R.png i.stack.imgur.com/JG3iT.png codeincomplete.com/articles/bin-packing/packed.png I would edit them in, but I don't know if my algorithm works on those, so i worry it would change it from a code review problem to a code not working (aka Stackoverflow) problem \$\endgroup\$ – Pureferret Mar 14 at 12:39
  • 1
    \$\begingroup\$ They are already tiled; that's useful to know. Kd-tree seems like an even better suggestion. Maybe someone knows a better representation for your data. I would say that those images are relevant to the question. \$\endgroup\$ – Neil Mar 14 at 21:25
3
\$\begingroup\$

One way to solve the problem with trees

A simplified look at binary trees

the rectangles are static

[the rectangles] should never overlap

As such we can build a simple tree. Before looking at 2d points we can look at a solution for 1d points.

Say we have the following line segments. Beginnings are inclusive ends are not.

  • A: 0 - 2
  • B: 2 - 3
  • C: 3 - 4
  • D: 4 - 8

We could describe the values as a really simple binary tree.

Image of complete binary tree.

With the example I gave we can reduce the amount of leaf nodes to just 4.

Image of a truncated binary tree.

We do need to assign multiple leaves to the same node at times. For example if we had the following line segments:

  • A: 0 - 3
  • B: 3 - 8

Image of truncated binary tree with multiple leaf nodes with the same value.

An algorithm for the above

As such we can just use a simple binary tree. With two major changes:

  1. We need to make the intermediary nodes when building the leaves.
  2. We may need to add multiple leaf nodes to account for the end of the rect.

As such we can build a simple algorithm:

  • When building the nodes we need to know the index of the node.

    Each node has a range for the values the children can be. In our above 8 leaf node tree, the the values for node 4 can range from 0-8. Where the 2 node's range is 0-4 and the 5 node's range is 4-6.

  • If the range of the line segment is greater than the range of the node we can stop recursing.

  • Otherwise we need to recursively append to the left or right child node. (Can be both.)

    • If the start of the line segment's range is less than the node's index we recurse left.
    • If the end of the line segment's range is greater than the node's index we recurse right.

    Before recursing:

    • Build the child node if one doesn't exist. The index will be:

      Left: (node's index + node's start) // 2
      Right: (node's index + node's end) // 2

    • We also need to adjust one of the start or end of the child node's range.

      Left: The end of the child node's range is the current node's index.
      Right: The start of the child node's range is the current node's index.

    We then recurse into the children.

Here is an example implementation of such a binary tree in Python:

from __future__ import annotations

import dataclasses
import textwrap
from typing import Iterator, Optional, TypeVar, Generic

T = TypeVar("T")


@dataclasses.dataclass
class Node(Generic[T]):
    index: int
    left: Optional[Node[T]] = None
    right: Optional[Node[T]] = None
    value: Optional[T] = None

    def get_point(self, point: int) -> Optional[T]:
        if self.value is not None:
            return self.value
        child = self.left if point < self.index else self.right
        return child.get_point(point)

    def add_range(
        self,
        value: T,
        range_start: int,
        range_end: int,
        node_start: int,
        node_end: int,
    ) -> None:
        if range_start <= node_start and node_end <= range_end:
            self.value = value
            return
        if range_start < self.index:
            if self.left is None:
                self.left = Node((self.index + node_start) // 2)
            self.left.add_range(value, range_start, range_end, node_start, self.index)
        if self.index < range_end:
            if self.right is None:
                self.right = Node((self.index + node_end) // 2)
            self.right.add_range(value, range_start, range_end, self.index, node_end)

    # So I can show the code works
    def tree_format(self, join="──", top="  ", bottom="  ") -> Iterator[str]:
        if self.left is not None:
            for value in self.left.tree_format("┌─", bottom="│ "):
                yield top + value
        if self.value is None:
            yield f"{join}{self.index}"
        else:
            yield f"{join}{self.value}"
        if self.right is not None:
            for value in self.right.tree_format("└─", top="│ "):
                yield bottom + value


class Tree(Generic[T]):
    _size: int
    _root: Node

    def __init__(self, size: int) -> None:
        self._size = size
        self._root = Node(size // 2)

    def __str__(self) -> None:
        return "\n".join(self._root.tree_format())

    def add_range(self, value: T, start: int, stop: int):
        self._root.add_range(value, start, stop, 0, self._size)

    def get_point(self, point: int) -> Optional[T]:
        try:
            return self._root.get_point(point)
        except AttributeError:
            return None


if __name__ == "__main__":
    print("Tree1:")
    tree_1 = Tree(8)
    tree_1.add_range("A", 0, 2)
    tree_1.add_range("B", 2, 3)
    tree_1.add_range("C", 3, 4)
    tree_1.add_range("D", 4, 8)
    print(tree_1)
    print(3, "==", tree_1.get_point(3))

    print("\nTree2:")
    tree_2 = Tree(8)
    tree_2.add_range("A", 0, 3)
    tree_2.add_range("B", 3, 8)
    print(tree_2)
    print(3, "==", tree_2.get_point(3))

    print("\nTree3:")
    tree_3 = Tree(8)
    tree_3.add_range("A", 0, 3)
    tree_3.add_range("B", 4, 8)
    print(tree_3)
    print(3, "==", tree_3.get_point(3))
Tree1:
    ┌─A
  ┌─2
  │ │ ┌─B
  │ └─3
  │   └─C
──4
  └─D
3 == C

Tree2:
    ┌─A
  ┌─2
  │ │ ┌─A
  │ └─3
  │   └─B
──4
  └─B
3 == B

Tree3:
    ┌─A
  ┌─2
  │ │ ┌─A
  │ └─3
──4
  └─B
3 == None

We can abstract the binary tree (1D) to a quad tree (2D) and perform the same algorithm.

The quad tree will have a top-left, top-right, bottom-left and bottom-right but otherwise would work the same way.

Problems

The above solution isn't just rainbows and sunshine

  • The tree's size must never change.
    If the tree ever needs to resize you must build one from scratch again.

  • Currently the tree cannot have overlapping boxes.
    Adding the capability doesn't seem impossible however.

    1. You would need to change Node.value to a list and append to the list in Node.add_range.
    2. Adjust Node.get_point to not eagerly exit and return the children's values (if applicable) along with the current node's values.
  • Your tree can have lots of cruft leaf nodes because of bad index selection.

    (node_end + self.index) // 2
    

    Say you want to put 9 equally sized squares into a 3x3 grid, you won't have a nice 9 leaf nodes. You'd have 36 leaf nodes.

    We see a less severe version of the problem in "Tree2". Had we selected 3 to be the first index to split on, rather than 4, we'd only have 2 nodes not 4.

      ┌─A
    ──3
      └─B
    

    To solve the issue I'd move the index generation code out into a separate binary or quad tree. For example we could abstract the index generation as:

    class IndexNode:
        def __init__(self, index, start, end):
            self.index = index
            self.start = start
            self.end = end
    
        def left(self):
            start, end = self.start, self.index
            return Node((start + end) // 2, start, end)
    
        def right(self):
            start, end = self.index, self.end
            return Node((start + end) // 2, start, end)
    

    We can now easily change the index generation for the 3x3 grid without having to mangle the other tree.

    We could also manually define the tree. But you'd have to manually build the entire tree. Or have a hybrid where you define the top nodes and let the class generate the rest.

Maintainability

I'm aiming for maintainability over performance

As you can probably see using a tree can get you better performance. Since the tree could find the rects in \$O(\log(n))\$ time. To improve the performance and to get good memory usage may require more thought; depending on the intricate patterns you use.

However do you really get much from building an intricate quad-tree? Even my simple binary tree is double your line count. If you have come on CR without caring about speed then I can't imagine your current solution is performing poorly. As such the cost to maintainability doesn't really seem worth the gain in speed at the moment.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.