Is an svg element in convex hull (path)?

Question

I have an svg path which I can draw. With d3js I calculate a convex hull around the path with d3.geom.hull(...). Now I have some svg objects like nodes (svg:circle) and I want to find out whether the node is in the hull or not. How can I realize that? Here is a picture from my svg view:

EDIT: My goal is to the node elements in the hull (which are within the path), not only at the edge of the path.

Answer 1

Here's an easy way to do that:

1. Calculate your hull geometry, get back the coordinates array that d3.geom.hull gives you.

2. Add your new point to your original data array and calculate d3.geom.hull again on this array.

3. Compare the array of points returned from step 1 with the array of points returned from step 2 to see if the calculated hull has changed. If it has, then the point is outside the convex hull. If there is no change, then it's inside the convex hull.

This might be performance-intensive if you have a really large dataset.

Here's some simple code to demonstrate:

   // Some Random points
   var coords = d3.range(50).map(function() {return [Math.random(),Math.random()]})
   yourHull = d3.geom.hull(coords)
   // Random new point
   newCoord = [Math.random(),Math.random()]
   coords.push(newCoord)
   newHull = d3.geom.hull(coords)

   //The easy case to spot
   if (newHull.length != yourHull.length) {
      console.log("Outside")
   }
   //If the array lengths are the same, the point values may have changed
   else {
   var outside = false;
   for (var x = 0; x < yourHull.length;x++) {
      for (var y = 0; y < 2;y++) {
         if (yourHull[x][y] != newHull[x][y]) {
            outside = true;
            break;
         }
      }
   }

   if (outside) {
      console.log("outside")
   }
   else {
      console.log("on the hull")
   }
  }

Answer 2

The fastest way of doing this is to have the browser do all the actual work. In particular, use the method document.getElementFromPoint() to have the rendering engine determine the overlap.

The idea is simple -- add the point you're interested in behind the hull, then check whether the above method gives you the point or the hull. The code looks like this.

function isInside(point) {
  var c = svg.insert("circle", "path.hull")
    .attr("r", 1)
    .attr("cx", point[0])
    .attr("cy", point[1]);

  var bounds = c.node().getBoundingClientRect();

  var atPoint = document.elementFromPoint(bounds.left, bounds.top);
  var inside = atPoint == c.node() ? false : true;

  c.remove();

  return inside;
}

The only slightly tricky bit is to convert the relative coordinates of the point to absolute coordinates -- the above code assumes that the SVG is a top-level element on the page itself or not translated by the containing elements. If this is not the case, adjust the code as appropriate.

The big advantage over the other answer is that the runtime does not depend on the size of the hull (as in the number of points defining it). It only depends on the number of points you want to check.

Complete demo here.