Clip d3 voronoi with d3 hull

Question

I would like to draw a d3 voronoi diagram and clip it like d3 hull borders do bound a collection of nodes or any similar clipping.

The red line in this Screenshot shows what i would like to achieve.

How can it be done ?

Answer 1

The d3.geom.hull function will find a polygon that contains all your nodes tightly, with no extra spacing. That of course would cancel out much of the purpose of the Voronoi regions, which are intended to add some active space around the nodes. So what you need to calculate is a polygon that is a certain padding distance larger than the convex hull polygon on all sides.

My recommended algorithm:

• Use d3.geom.hull(nodes) to calculate the array of vertices that define the tight boundary of your nodes.

• Use those vertices to create a d3 polygon object.

• Calculate the center of that polygon with .centroid().

• For each vertex in your convex hull, calculate a point that is padding distance farther away from the center of the polygon.

• Use this expanded polygon to clip all the polygons in the array returned by Voronoi function.

Sample code:

var hullFunction = d3.geom.hull()
                     .x(/*x accessor function*/)
                     .y(/*y accessor function*/);

var tightHull = hullFunction(nodes); //returns an array of vertices

var centerPoint = d3.geom.polygon(tightHullArray).centroid();

var expandedHull = tightHullArray.map( function(vertex) {
             //Create a new array of vertices, each of which is the result
             //of running this function on the corresponding vertex of the
             //original hull.
             //Each vertex is of the form [x,y]

             var vector = [vertex[0] - centerPoint[0], 
                           vertex[1] - centerPoint[1] ];
             //the vector representing the line from center to this point

             var vectorLength = Math.sqrt(vector[0]*vector[0] 
                                          + vector[1]*vector[1]);
             //Pythagorus' theorem to get the length of the line

             var normalizedVector = [vector[0] / vectorLength, 
                                     vector[1] / vectorLength];
             //the vector scaled down to length 1, but with the same angle
             //as the original vector

             return [vertex[0] + normalizedVector[0]*padding,
                     vertex[1] + normalizedVector[1]*padding ];
             //use the normalized vector to adjust the vertex point away from
             //the center point by a distance of `padding` 

         });

var clippedVoronoi = voronoiPolygons.map(function(voronoi) {
       //voronoiPolygons would be the array returned by the voronoi function

              return expandedHull.clip(voronoi);
              //I think this is correct; if you get weird results, try
              // return voronoi.clip(expandedHull);
         });

Answer 2

I recently made an example to illustrate to myself how polygon clipping works: http://tributary.io/inlet/8263747

You can see the clipping code in the update function, and the rendering code in the process function. drag the points around to see how the clipping will be affected.

A couple things to watch out for:

1. the order of the points in the "hull" (or clipping path in my example) matters. Your polygon has to be counter-clockwise as well as convex (no caves). If these conditions aren't met there is no error, you just get back an empty array.

2. the polygon operations manipulate your point arrays in place, if you don't want your geometry itself clipped, but want a copy you need to make a copy first.