5

Is there a simple way to find out if a point is inside a voronoi cell?

For example, the following code generates something like the diagram below:

using namespace boost::polygon;

point_data<int> p1(0, 0);
point_data<int> p2(-10, 10);
point_data<int> p3(-10, -10);
point_data<int> p4(10, -10);
point_data<int> p5(10, 10);

std::vector<point_data<int>> pts = { p1, p2, p3, p4, p5 };
construct_voronoi(pts.begin(), pts.end(), vd);

voronoi diagram

In this case, how can I found out if the point (5,5) is inside the central cell?

I could create a polygon out of each cell and find out using a point in polygon algorithm, but I'm interested in knowing the library offers something "for free".

genpfault
  • 51,148
  • 11
  • 85
  • 139
André Wagner
  • 1,330
  • 15
  • 26
  • probably easiest way is iterate over all polygons and verify the middle point 0,0 is in it and check for that specific polygon if the point you want to check is in it. – cageman Feb 01 '14 at 18:52
  • 1
    I'm not sure which result you want for the point `(5, 5)`, which is exactly on the border between two cells in your example data. Anyway, another approach, which doesn't use a point in polygon algorithm, is to check the distance from your test point to the point that defines each voronoi cell. The point closest to your test point tells you which cell your test point is in. – Magnus Hoff Feb 01 '14 at 19:11

3 Answers3

2

Like, @Magnus Hoff commented, the cell defined by the closest center to your query point must contain it (up to distance ties). In fact, this is from the definition of a Voronoii cell, i.e. the point set whose members are closer to the cell center than to any other centers. So, this query really doesn't require boost::polygon or the half-line algorithm:

//using namespace boost::polygon;
using namespace std;
#include <iostream>
#include <vector>
#include <limits>

template <typename T> 
using point_data = std::pair<T,T>;
point_data<int> p1(0, 0);
point_data<int> p2(-10, 10);
point_data<int> p3(-10, -10);
point_data<int> p4(10, -10);
point_data<int> p5(10, 10);

std::vector<point_data<int>> pts = { p1, p2, p3, p4, p5 };
//construct_voronoi(pts.begin(), pts.end(), vd);


double dist2(point_data<int> pt1,point_data<int> pt2) {
  return (pt1.first-pt2.first)*(pt1.first-pt2.first) + (pt1.first-pt2.second)* (pt1.first-pt2.second);
}

bool isInCell(point_data<int> point) {
  double d = numeric_limits<double>::max();

  point_data<int> ptClose;
  for (auto& pt:pts) {
    if (dist2(pt,point) < d)
      ptClose = pt;
  }
  return ptClose == point;
}

int main() {
  cout << isInCell(make_pair(5,5)) << endl;
}
thor
  • 21,418
  • 31
  • 87
  • 173
  • 1
    You may compare `square_dist` (to avoid `sqrt` (and `double`)). – Jarod42 Feb 01 '14 at 20:08
  • Thank you for your answer. One question though: wouldn't this method would be too slow if had, say, > 100000 cells? – André Wagner Feb 01 '14 at 21:15
  • There is a more efficient way of finding the closest point for a point in computational geometry if you really want to handle 100000 cells. Or you can have some spatial indexing if this query is a repeated one. They are a little bit more involved though. – thor Feb 02 '14 at 07:49
  • @Jarod42, Thanks for the correction. Typo corrected and distance square used. – thor Feb 02 '14 at 07:52
  • @TingL, thank you very much for your answer. That was exactly what I was looking for. My fault was that I didn't realized that the "point in polygon" wasn't the best route to follow. Turns out I don't even need boost for that. – André Wagner Feb 02 '14 at 16:11
  • This is brute-force algorithm with complexity N*K where N is number of sites and K is number of queries.I think the OP was on the right track constructing Voronoi diagrams. If the query points are known upfront there might be some benefit of building the querying into the Voronoi diagram (e.g. Fortune's) algorithm. – Marcin Jan 20 '18 at 03:23
0

You want point location test, especially a kirkpatrick data structure for point location test but it is a little bit complicated. Instead you can give each voronoi cell a color and check the color at the point.

Micromega
  • 12,486
  • 7
  • 35
  • 72
0

A good approach is to have the point sites backed by some space-partitioning data structure (such as a KD-tree) which provides easy (N-)nearest-neighbour search (in fact any decent voronoi diagram implementation should already be doing this for a nearest neighbour search during point site insertion).

So use your own data structure (tree) alongside the diagram: as points sites are inserted into the voronoi diagram, insert the same points into the tree. Query the tree to find the (N) nearest voronoi site(s). Then it's up to you about how to map that site coordinate to a voronoi cell object.

micycle
  • 3,328
  • 14
  • 33