|
Weight of added points:
|
Randomize weights of new points:
Draw Delaunay triangulation, extra hyperbolas, intersection points:
Click to place sites with weight specified by text box, starting from one of 7 test cases (test case 0 is empty). The additively weighted Voronoi diagram (or Apollonius graph) is calculated, which is a modification of the regular Voronoi diagram in which the curves dividing regions are equidistant from disks in the corresponding regions rather than sites. The weight of a site equals the radius of its disk. This leads to segments of hyperbolas between sites instead of straight lines.
My algorithm is buggy and fails for diagrams with more than a few points. The CGAL link above has a working implementation that is more efficient as well. My implementation is brute-force, taking the following steps for each site added:
Remove any sites with a weight that is too low -- less than the weight of another site minus the distance to that site -- these are colored blue
Find all points equidistant from any triplet of disks corresponding to weighted sites
For sites i,j,k, this is done by finding the intersection of the hyperbolic segment between i and j and the segment between i and k
Finding this intersection requires solving a quartic (4th order) polynomial equation
Sort sites by weight (descending order) and loop through all sites i having intersection points calculated above
Sort intersection points by angle, and pick the closest one p
Note that each intersection point is a junction of 3 hyperbolic segments between sites, so for site i, the intersection point has clockwise and counterclockwise neighbor sites corresponding to segments equidistant from i and the respective sites
Iterate through other intersections in clockwise order, finding the next intersection that has the clockwise neighbor site of p as a counterclockwise neighbor (so we know they are connected)
Do the same in the counterclockwise direction, and combine the two lists, keeping track of intersection points and neighbors (being careful about the possibility of complete loops as well)
Draw the hyperbola segments by using intersection points as lower and upper bounds (in rotated coordinate system)
Note: a given site can have multiple disjoint connected sets of neighbor sites
This runs into problems with isolated sites that may only have one hyperbola segment in the diagram because of a large-weight neighbor, but because of intersections with other small-weight sites, extraneous segments are drawn (and the single desired segment is not -- test case 4 shows an example of this).