CODEWITHSUNDEEP
javascriptd3.jsvisualizationconvex-hull
meyer0095
meyer0095

Reputation: 137

D3.js Convex Hull With 2 Data Points

The API for Hull Geom states: "Assumes the vertices array is greater than three in length. If vertices is of length <= 3, returns []." (https://github.com/mbostock/d3/wiki/Hull-Geom)

I need to draw convex hulls around 2 nodes. I am using the force layout, so the convex hull needs to be dynamic in that it moves around the nodes if I click a node and drag it around. My code is currently based off of this example: http://bl.ocks.org/donaldh/2920551

For context, this is what I am trying to draw a convex hull around:

Here it works when there are 3 nodes:

3 nodes

Here is what I am trying to draw a convex hull around (doesn't work with the code from the example above because Hull Geom will only take arrays with 3+ vertices):

2 Nodes

I understand the traditional use of a convex hull would never involve only two points, but I have tried drawing ellipses, rectangles, etc around the 2 nodes and it doesn't look anywhere near as good as the 3 nodes does.

I understand that Hull Geom ultimately just spits out a string that is used for pathing, so I could probably write a modified version of Hull Geom for 2 nodes.

Any suggestions on how to write a modified Hull Geom for 2 nodes or any general advice to solve my problem is really appreciated.

Upvotes: 2

Views: 1336

Answers (2)

Aaron Bramson
Aaron Bramson

Reputation: 1288

Isolin has a great solution, but it can be simplified. Instead of making the virtual point on the line at the midpoint, it's enough to add the fake points basically on top of an existing point...offset by an imperceptible amount. I adapted Isolin's code to also handle cases of groups with 1 or 2 nodes.

var groupPath = function(d) {
   var fakePoints = [];  
   if (d.length == 1 || d.length == 2) {
       fakePoints = [ [d[0].x + 0.001, d[0].y - 0.001],
          [d[0].x - 0.001, d[0].y + 0.001],
          [d[0].x - 0.001, d[0].y + 0.001]]; }        
   return "M" + d3.geom.hull(d.map(function(i) { return [i.x, i.y]; })
       .concat(fakePoints))  //do not forget to append the fakePoints to the group data
       .join("L") + "Z";
};

Upvotes: 2

Isolin
Isolin

Reputation: 876

Basically, you need to at least one fake point very close to the line to achieve the desired result. This can be achieved in the groupPath function.

For d of length 2 you can create a temporary array and attach it to the result of the map function as follows:

var groupPath = function(d) {
    var fakePoints = [];
    if (d.values.length == 2)
    {
        //[dx, dy] is the direction vector of the line
        var dx = d.values[1].x - d.values[0].x;
        var dy = d.values[1].y - d.values[0].y;

        //scale it to something very small
        dx *= 0.00001; dy *= 0.00001;

        //orthogonal directions to a 2D vector [dx, dy] are [dy, -dx] and [-dy, dx]
        //take the midpoint [mx, my] of the line and translate it in both directions
        var mx = (d.values[0].x + d.values[1].x) * 0.5;
        var my = (d.values[0].y + d.values[1].y) * 0.5;
        fakePoints = [ [mx + dy, my - dx],
                [mx - dy, my + dx]];
        //the two additional points will be sufficient for the convex hull algorithm
    }

    //do not forget to append the fakePoints to the input data
    return "M" + 
        d3.geom.hull(d.values.map(function(i) { return [i.x, i.y]; })
        .concat(fakePoints))
    .join("L") 
    + "Z";
}

Here a fiddle with a working example.

Upvotes: 3

Related Questions