2

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.)

Community
  • 1
  • 1
mknecht
  • 1,205
  • 11
  • 20
  • 1
    A good google search term is "planar point location data structure." Unfortunately, I've never learnt about a planar point location data structure that isn't completely horrifying. – tmyklebu Jul 16 '14 at 03:35
  • 1
    Point location Voronoi finds pointers to Kirkpatrick's algorithm which apparently does not have great constant factors but is not completely horrifying to me see http://cm.bell-labs.com/who/clarkson/cis677/lecture/5/ – mcdowella Jul 16 '14 at 04:57
  • @mcdowella: The horrifying part of Kirkpatrick's algorithm is contained in a single word: "Retriangulate." – tmyklebu Jul 16 '14 at 07:01
  • You may be able to combine [quadtrees](https://github.com/mbostock/d3/wiki/Quadtree-Geom) with this, i.e. use that to figure out which voronoi polygons are relevant. – Lars Kotthoff Jul 16 '14 at 09:04

1 Answers1

0

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.

rostok
  • 2,057
  • 2
  • 18
  • 20
  • He wants to use it to find letters. – Micromega Jul 16 '14 at 16:22
  • "How can I efficiently search a number of polygons for the ones containing a point?" - come on, this is search for a polygon and reason for doing it (finding letters) is irrelevant. – rostok Jul 17 '14 at 14:06
  • Good idea that. Finally got around to implement it, with a 1:1 mapping. An (irrelevant) downside of this approach is, that it takes ages to initialize, because I don't have an efficient way to iterate over all pixels of a polygon. Unfortunately, for some reason, it's actually slower than my grid-search. But must be my implementation. – mknecht Jul 23 '14 at 10:15