1

Currently I am working on a Javascript program that plots a Voronoi diagram and am trying to find all of the points that form the points that form the region around a point. To make this clearer, here is an example of a potential scenario:

Image of graph

Point D affects the region around point A if the mid-segment of these points intersects rays cast from the intersection of the mid-segments of points B and C. To break this down, here's what I'm saying in relation to the previous diagram:

Edited image of graph

Using rough approximations of the mid-segments, D does not intersect the Voronoi boundaries of point A. Using A as the current point, B and C as points known to affect the region, and D as the point checked for it's effect on the region; and knowing the angles and distances of B, C, and D relative to the first point, how can I find if D has an effect on the region?

Brendon Shaw
  • 63

1 Answers1

1

The Delaunay triangulation is the dual graph of the Voronoi diagram. Two points have adjacent Voronoi regions if and only if they are connected by an edge in the Delaunay triangulation [1]. Thus it suffices to compute the Delaunay triangulation.

See also Is it possible to compute only the adjacencies of Voronoi cells in the Voronoi diagram efficiently?, which describes a linear programming approach.

user76284
  • 5,967