Intersection of 2 SVG Paths

Question

I need to check if two SVG Path elements intersect. Checking for intersection of the bounding boxes with .getBBox() is too inaccurate. What I'm currently doing is iterating both paths with .getTotalLength() and then checking if two points .getPointAtLength() are equal.

Below is a snippet, but as you can see this is very slow and blocks the browser tab. There must be a more efficient method to check for intersections between two paths.

var path1 = document.getElementById("p1");
var path2 = document.getElementById("p2");
var time = document.getElementById("time");
var btn = document.getElementById("start");
btn.addEventListener("click", getIntersection);

function getIntersection() {
var start = Date.now();
  for (var i = 0; i < path1.getTotalLength(); i++) {
    for (var j = 0; j < path2.getTotalLength(); j++) {
      var point1 = path1.getPointAtLength(i);
      var point2 = path2.getPointAtLength(j);

      if (pointIntersect(point1, point2)) {
        var end = Date.now();
        time.innerHTML = (end - start) / 1000 + "s";
        return;
      }
    }

  }
}

function pointIntersect(p1, p2) {
  p1.x = Math.round(p1.x);
  p1.y = Math.round(p1.y);
  p2.x = Math.round(p2.x);
  p2.y = Math.round(p2.y);
  return p1.x === p2.x && p1.y === p2.y;
}

svg {
  fill: none;
  stroke: black;
}
#start {
  border: 1px solid;
  display: inline-block;
  position: absolute;
}

<div id="start">Start
</div>
<svg xmlns="http://www.w3.org/2000/svg">
  <path d="M 50 10 c 120 120 120 120 120 20 z" id="p1"></path>
  <path d="M 150 10 c 120 120 120 120 120 20 z" id="p2"></path>
</svg>
<div id="time"></div>

Instead of sampling hundreds or thousands of points and checking if some off them are "close enough" like your current algorithm does, this looks like a faster and more reliable method: https://stackoverflow.com/a/4041286/1869660 — Sphinxxx, Mar 20 '18 at 00:06

score 6 · Answer 1 · answered Nov 15 '18 at 11:54

6

You can use an existing library to do this: https://github.com/signavio/svg-intersections

It calculates the intersections mathematically rather than iteratively so the performance shouldn't degrade with very long paths.

answered Nov 15 '18 at 11:54

matt helliwell

2,353
17
24

score 2 · Accepted Answer · answered Feb 07 '17 at 15:22

I'm not sure but it may be possible to solve this mathematically if you could extract the vectors and curves from the paths. However, your function can be optimized by caching the points from one path, and reducing the number of calls to getTotalLength and getPointAtLength.

function getIntersection() {
    var start = Date.now(),
    path1Length = path1.getTotalLength(),
    path2Length = path2.getTotalLength(),
    path2Points = [];

    for (var j = 0; j < path2Length; j++) {      
        path2Points.push(path2.getPointAtLength(j));
    }

    for (var i = 0; i < path1Length; i++) {  
        var point1 = path1.getPointAtLength(i);

        for (var j = 0; j < path2Points.length; j++) {
            if (pointIntersect(point1, path2Points[j])) {
                var end = Date.now();
                time.innerHTML = (end - start) / 1000 + "s";        
                return;
            }
       }
    }
}

This can calculate the example paths in around 0.07 seconds instead of 4-5 seconds.

jsfiddle

I have tried your method and also made a test of it here: https://codepen.io/netsi1964/pen/yKagwx/ — Netsi1964, Mar 16 '18 at 22:26
wrong result is comming try this in your code ```
Start

``` — Amit Panasara, Dec 09 '19 at 09:38

score 1 · Answer 3 · answered Apr 07 '21 at 04:46

time 0.027s

function getIntersection2() {
  function Intersect(p1, p2) {
    return p1.z!==p2.z && p1.x === p2.x && p1.y === p2.y;
  }
  var paths = [path1,path2];
    var start = Date.now(),
    pathLength = [path1.getTotalLength(),path2.getTotalLength()],
    pathPoints = [],
    inters = [];
 
  for (var i = 0; i < 2; i++) {  
    for (var j = 0; j < pathLength[i]; j++) {
      var p = paths[i].getPointAtLength(j);
      p.z=i;
      p.x=Math.round(p.x);
      p.y=Math.round(p.y);
      pathPoints.push(p);
    }
  }
  pathPoints.sort((a,b)=>a.x!=b.x?a.x-b.x:a.y!=b.y?a.y-b.y:0)
  // todos os pontos
  .forEach((a,i,m)=>i&&Intersect(m[i-1],a)?inters.push([a.x,a.y]):0)
  // somente o primeiro
  //.some((a,i,m)=>i&&Intersect(m[i-1],a)?inters.push([a.x,a.y]):0);
  result.innerHTML = inters;
        var end = Date.now();
        time.innerHTML = (end - start) / 1000 + "s";
        return;
}

Intersection of 2 SVG Paths

3 Answers3