Search code examples
algorithmd3.jsvoronoispatial-index

Efficiently find the polygon in a Voronoi diagram that contains a point

I am projecting images on a Voronoi diagram. For each non-black pixel of the image, I find the corresponding polygon in the diagram and color it. (The site, to get an idea what I mean.) With a few hundred polygons, a brute force approach is feasible. With a few thousands, it's not.

My question: How can I efficiently search a number of polygons for the ones containing a point? I am interested in the general case, without making assumptions about the polygons distribution or size.

enter image description here

Two existing answers (that I found) relate:

Finding out if a point is inside a voronoi cell It elegantly leverages the fact that Voronoi polygons are convex. Hence, the polygon, whose center is nearest, must also be the containing polygon. Unfortunately, to determine the minimum, still all polygons are searched. That's what does not scale.

Finding the polygon in a 2D mesh which contains a point It mentions a 2d interval tree. (According to these slides on the topic it should be a segment tree.) One property of Voronoi diagrams, however, is that the polygons are non-overlapping, while segment trees don't make that assumption. Hence, if indeed these trees are the best option(?), is there an approach that includes this assumption, enabling it to be more efficient?

I am building this as JavaScript purely client-side, using D3, so I am interested in an algorithm, a library or a change of modeling. A spatial database such as MySQL or MongoDB, for example, does not help me.

What I tried so far: I built a sufficiently efficient index for exactly my use case that relies on assumptions I can make, see below.

The solution for my specific case is basically a hash of the polygons' center point.

Building the index:

  1. The diagram is divided into a uniformly sized grid.
  2. Each polygon is assigned to a cell by its center point.

When searching for the polygon that contains a given point:

  1. The cell for the point is determined.
  2. All polygons for this cell are tested.
  3. If none matches, the surrounding cells are searched, breadth-first, until the polygon is found.

This works, because I make a few assumptions:

  1. The polygons are uniformly distributed. This means, a uniform grid is fine. A uniform grid allows to determine the cell for a point by translating the coordinates.
  2. The polygons are convex. This means that the center point is actually near the bulk of its area.
  3. The polygons have largely the same size. By choosing a cell-size close to the average polygon-size, it is very likely that either the direct cell or one of the neighboring cells is associated with the wanted polygon.
  4. Basically always, there is a polygon that contains the point. (I.e. little time is wasted on searching all cells.)

So, while this works for exactly my use case, I would like to loosen some restrictions. This question is about discarding assumptions 1 and 3, if possible. (2 and 4 are given for a Voronoi diagram, as I understand it.)

Solution

  • If this is not purely geometrical problem then I would go for the lookup bitmap. Just paint all the polygons in a secondary bitmap (canvas) using integer ids for color. To find poly's id you just check the pixels color on the corresponding position. One position - one fetch. It should be ultra fast yet not geometrically perfect. Note that you can scale the lookup bitmap to increase accuracy.