4

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>
Kai
  • 135
  • 2
  • 7
  • 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

4 Answers4

2

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

lewism
  • 99
  • 3
1

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;
}
Ricardo Dias
  • 11
  • 1
0

And this, while totally not being what the OP asked for, is what I was looking for.

A way to detect intersections over a large number of paths by sampling:

function pointIntersects(p1, p2) {
    return (Math.abs(p1.x - p2.x) > 10)
        ? false
        : (Math.abs(p1.y - p2.y) < 10)
}

function pointsIntersect(points, point) {
    return _.some(points, p => pointIntersects(p, point))
}

function samplePathPoints(path) {
    const pathLength = path.getTotalLength()
    const points = []
    for (let i = 0; i < pathLength; i += 10)
        points.push(path.getPointAtLength(i))
    return points
}

let pointCloud = []
_(document.querySelectorAll('svg path'))
    .filter(path => {
        const points = samplePathPoints(path)
        if (_.some(pointCloud, point => pointsIntersect(points, point)))
            return true
        points.forEach(p => pointCloud.push(p))
    })
    .each(path => path.remove())

note: underscore/lodash has been used for brevity

Orwellophile
  • 13,235
  • 3
  • 69
  • 45
0

You can further optimize performance by reducing the amount of sample points.

getPointAtLength() is rather expensive especially when run >100 times.

The following examples should usually need only a few milliseconds.

Example 1: Boolean result (intersecting true/false)

let svg = document.querySelector("svg");

function check() {
  perfStart();
  let intersections = checkPathIntersections(p0, p1, 24);
  time.textContent = '1. stroke intersection: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';
  //render indtersection point
  gInter.innerHTML = '';
  renderPoint(gInter, intersections[0], 'red', '2%');
}

function checkPathIntersections(path0, path1, checksPerPath = 24, threshold = 2) {
  /**
   * 0. check bbox intersection
   * to skip sample point checks
   */
  let bb = path0.getBBox();
  let [left, top, right, bottom] = [bb.x, bb.y, bb.x + bb.width, bb.y + bb.height];

  let bb1 = path1.getBBox();
  let [left1, top1, right1, bottom1] = [bb1.x, bb1.y, bb1.x + bb1.width, bb1.y + bb1.height];

  let bboxIntersection =
    left <= right1 - threshold &&
    top <= bottom1 - threshold &&
    bottom >= top1 - threshold &&
    right >= left1 - threshold ?
    true :
    false;

  if (!bboxIntersection) {
    return false;
  }

  // path0
  let pathLength0 = path0.getTotalLength();
  // set temporary stroke
  let style0 = window.getComputedStyle(path0);
  let fill0 = style0.fill;
  let strokeWidth0 = style0.strokeWidth;
  path0.style.strokeWidth = threshold;

  // path1
  let pathLength1 = path1.getTotalLength();

  // set temporary stroke
  let style1 = window.getComputedStyle(path1);
  let fill1 = style1.fill;
  let strokeWidth1 = style1.strokeWidth;
  path1.style.strokeWidth = threshold;

  /**
   * 1. check sample point intersections
   */
  let checks = 0;
  let intersections = [];

  /**
   * 1.1 compare path0 against path1
   */
  for (let c = 0; c < checksPerPath && !intersections.length; c++) {
    let pt = path1.getPointAtLength((pathLength1 / checksPerPath) * c);
    let inStroke = path0.isPointInStroke(pt);
    let inFill = path0.isPointInFill(pt);

    // check path 1 against path 2
    if (inStroke || inFill) {
      intersections.push(pt)
    } else {
      /**
       * no intersections found: 
       * check path1  sample points against path0
       */
      let pt1 = path0.getPointAtLength(
        (pathLength0 / checksPerPath) * c
      );

      let inStroke1 = path1.isPointInStroke(pt1);
      let inFill1 = path1.isPointInFill(pt1);

      if (inStroke1 || inFill1) {
        intersections.push(pt1)
      }
    }
    // just for benchmarking
    checks++;
  }

  // reset styles
  path0.style.fill = fill0;
  path0.style.strokeWidth = strokeWidth0;

  path1.style.fill = fill1;
  path1.style.strokeWidth = strokeWidth1;

  console.log('sample point checks:', checks);
  return intersections;

}


/**
 * simple performance test
 */

function perfStart() {
  t0 = performance.now();
}

function perfEnd(text = "") {
  t1 = performance.now();
  total = t1 - t0;
  console.log(`excecution time ${text}:  ${total} ms`);
  return total;
}

function renderPoint(
  svg,
  coords,
  fill = "red",
  r = "2",
  opacity = "1",
  id = "",
  className = ""
) {
  //console.log(coords);
  if (Array.isArray(coords)) {
    coords = {
      x: coords[0],
      y: coords[1]
    };
  }

  let marker = `<circle class="${className}" opacity="${opacity}" id="${id}" cx="${coords.x}" cy="${coords.y}" r="${r}" fill="${fill}">
    <title>${coords.x} ${coords.y}</title></circle>`;
  svg.insertAdjacentHTML("beforeend", marker);
}
svg {
  fill: none;
  stroke: black;
}
<p><button onclick="check()">Check intersection</button></p>
<svg xmlns="http://www.w3.org/2000/svg">
 <path d="M 50 10 c 120 120 120 120 120 20 z" id="p0"></path>
  <path d="M 150 10 c 120 120 120 120 120 20 z" id="p1"></path>
  <g id="gInter"></g>
</svg>

<p id="time"></p>

How it works

1. Check BBox intersections

Checking for intersection of the bounding boxes with .getBBox() is too inaccurate.

That's true, however we should always start with a bbox intersection test to avoid unnecessary calculations.

2. Check intersection via isPointInStroke() and isPointInFill()

These natively supported methods are well optimized so we don't need to compare retrieved point arrays against each other.

By increasing the stroke-width of the paths we can also increase the tolerance threshold for intersections.

3. Reduce sample points

If we don't need all intersecting points but only a boolean value, we can drastically reduce the number of intersection checks by creating them progressively within the testing loop.

Once we found any intersection (in stroke or fill) – we stop the loop and return true.

Besides we can usually reduce the number by splitting the path length in e.g 24-100 steps.

Example 2: get all intersection points

let svg = document.querySelector("svg");
let paths = svg.querySelectorAll("path");

function check() {
  // reset results
  gInter2.innerHTML = '';
  gInter.innerHTML = '';
  time.textContent = '';


  /**
   * Boolean check
   */
  perfStart();
  let intersections = checkPathIntersections(p0, p1, 24);
  time.textContent += '1. stroke intersection: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';
  renderPoint(svg, intersections[0]);

  perfStart();
  let intersections1 = checkPathIntersections(p2, p3, 24);
  time.textContent += '2. fill intersection: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';
  renderPoint(svg, intersections1[0])

  /**
   * Precise check
   */
  perfStart();
  let intersections3 = checkIntersectionPrecise(p4, p5, 100, 1);
  time.textContent += '3. multiple intersections: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';

  if (intersections3.length) {
    intersections3.forEach(p => {
      renderPoint(svg, p, 'red')
    })
  }

  // no bbox intersection
  perfStart();
  let intersections4 = checkPathIntersections(p5, p6, 24);
  time.textContent += '4. no bbBox intersection: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';
  
  
  perfStart();
  let intersections5 = checkIntersectionPrecise(p8, p9, 1200, 0);
  time.textContent += '5. multiple intersections: ' + perfEnd().toFixed(3) * 1 + ' ms; \n ';
  if (intersections5.length) {
    intersections5.forEach(p => {
      renderPoint(gInter2, p, 'green', '0.25%');
    })
  }



}



function checkIntersectionPrecise(path0, path1, split = 1000, decimals = 0) {

  /**
   * 0. check bbox intersection
   * to skip sample point checks
   */
  let bb = path0.getBBox();
  let [left, top, right, bottom] = [bb.x, bb.y, bb.x + bb.width, bb.y + bb.height];

  let bb1 = path1.getBBox();
  let [left1, top1, right1, bottom1] = [bb1.x, bb1.y, bb1.x + bb1.width, bb1.y + bb1.height];

  let bboxIntersection =
    left <= right1 &&
    top <= bottom1 &&
    bottom >= top1 &&
    right >= left1 ?
    true :
    false;

  if (!bboxIntersection) {
    console.log('no intersections at all');
    return false;
  }


  // path0
  let pathData0 = path0.getPathData({
    normalize: true
  })
  let points0 = pathDataToPolygonPoints(pathData0, true, split);
  let points0Strings = points0.map(val => {
    return val.x.toFixed(decimals) + '_' + val.y.toFixed(decimals)
  });
  // filter duplicates
  points0Strings = [...new Set(points0Strings)];

  // path1
  let pathLength1 = path1.getTotalLength();
  let pathData1 = path1.getPathData({
    normalize: true
  })
  let points1 = pathDataToPolygonPoints(pathData1, true, split);
  let points1Strings = points1.map(val => {
    return val.x.toFixed(decimals) + '_' + val.y.toFixed(decimals)
  });
  points1Strings = [...new Set(points1Strings)];


  // 1. compare
  let intersections = [];
  let intersectionsFilter = [];

  for (let i = 0; i < points0Strings.length; i++) {
    let p0Str = points0Strings[i];
    let index = points1Strings.indexOf(p0Str);
    if (index !== -1) {
      let p1 = p0Str.split('_');
      intersections.push({
        x: +p1[0],
        y: +p1[1]
      });
    }
  }

  // filter nearby points
  if (intersections.length) {
    intersectionsFilter = [intersections[0]];

    let length = intersections.length;
    for (let i = 1; i < length; i += 1) {
      let p = intersections[i];
      let pPrev = intersections[i - 1];

      let diffX = Math.abs(pPrev.x - p.x);
      let diffY = Math.abs(pPrev.y - p.y);
      let diff = diffX + diffY;

      if (diff > 1) {
        intersectionsFilter.push(p)
      }
    }
  } else {
    return false
  }

  return intersectionsFilter;

}



/**
 * convert path d to polygon point array
 */
function pathDataToPolygonPoints(pathData, addControlPointsMid = false, splitNtimes = 0, splitLines = false) {

  let points = [];
  pathData.forEach((com, c) => {
    let type = com.type;
    let values = com.values;
    let valL = values.length;

    // optional splitting
    let splitStep = splitNtimes ? (0.5 / splitNtimes) : (addControlPointsMid ? 0.5 : 0);
    let split = splitStep;

    // M 
    if (c === 0) {
      let M = {
        x: pathData[0].values[valL - 2],
        y: pathData[0].values[valL - 1]
      };
      points.push(M);
    }

    if (valL && c > 0) {
      let prev = pathData[c - 1];
      let prevVal = prev.values;
      let prevValL = prevVal.length;
      let p0 = {
        x: prevVal[prevValL - 2],
        y: prevVal[prevValL - 1]
      };

      // cubic curves
      if (type === "C") {
        if (prevValL) {
          let cp1 = {
            x: values[valL - 6],
            y: values[valL - 5]
          };
          let cp2 = {
            x: values[valL - 4],
            y: values[valL - 3]
          };
          let p = {
            x: values[valL - 2],
            y: values[valL - 1]
          };

          if (addControlPointsMid && split) {
            // split cubic curves
            for (let s = 0; split < 1 && s < 9999; s++) {
              let midPoint = getPointAtCubicSegmentLength(p0, cp1, cp2, p, split);
              points.push(midPoint);
              split += splitStep
            }
          }
          points.push({
            x: values[valL - 2],
            y: values[valL - 1]
          });
        }
      }

      // linetos
      else if (type === "L") {
        if (splitLines) {
          //let prevCoords = [prevVal[prevValL - 2], prevVal[prevValL - 1]];
          let p1 = {
            x: prevVal[prevValL - 2],
            y: prevVal[prevValL - 1]
          }
          let p2 = {
            x: values[valL - 2],
            y: values[valL - 1]
          }

          if (addControlPointsMid && split) {
            for (let s = 0; split < 1; s++) {
              let midPoint = interpolatedPoint(p1, p2, split);
              points.push(midPoint);
              split += splitStep
            }
          }
        }
        points.push({
          x: values[valL - 2],
          y: values[valL - 1]
        });
      }
    }
  });
  return points;
}


/**
 * Linear  interpolation (LERP) helper
 */
function interpolatedPoint(p1, p2, t = 0.5) {
  //t: 0.5 - point in the middle
  if (Array.isArray(p1)) {
    p1.x = p1[0];
    p1.y = p1[1];
  }
  if (Array.isArray(p2)) {
    p2.x = p2[0];
    p2.y = p2[1];
  }
  let [x, y] = [(p2.x - p1.x) * t + p1.x, (p2.y - p1.y) * t + p1.y];
  return {
    x: x,
    y: y
  };
}


/**
 * calculate single points on segments
 */

function getPointAtCubicSegmentLength(p0, cp1, cp2, p, t=0.5) {
  let t1 = 1 - t;
  return {
    x: t1 ** 3 * p0.x + 3 * t1 ** 2 * t * cp1.x + 3 * t1 * t ** 2 * cp2.x + t ** 3 * p.x,
    y: t1 ** 3 * p0.y + 3 * t1 ** 2 * t * cp1.y + 3 * t1 * t ** 2 * cp2.y + t ** 3 * p.y
  }
}





function checkPathIntersections(path0, path1, checksPerPath = 24, threshold = 2) {

  /**
   * 0. check bbox intersection
   * to skip sample point checks
   */
  let bb = path0.getBBox();
  let [left, top, right, bottom] = [bb.x, bb.y, bb.x + bb.width, bb.y + bb.height];

  let bb1 = path1.getBBox();
  let [left1, top1, right1, bottom1] = [bb1.x, bb1.y, bb1.x + bb1.width, bb1.y + bb1.height];

  let bboxIntersection =
    left <= right1 - threshold &&
    top <= bottom1 - threshold &&
    bottom >= top1 - threshold &&
    right >= left1 - threshold ?
    true :
    false;

  if (!bboxIntersection) {
    return false;
  }

  // path0
  let pathLength0 = path0.getTotalLength();
  // set temporary stroke
  let style0 = window.getComputedStyle(path0);
  let fill0 = style0.fill;
  let strokeWidth0 = style0.strokeWidth;
  path0.style.strokeWidth = threshold;

  // path1
  let pathLength1 = path1.getTotalLength();

  // set temporary stroke
  let style1 = window.getComputedStyle(path1);
  let fill1 = style1.fill;
  let strokeWidth1 = style1.strokeWidth;
  path1.style.strokeWidth = threshold;

  /**
   * 1. check sample point intersections
   */
  let checks = 0;
  let intersections = [];

  /**
   * 1.1 compare path0 against path1
   */
  for (let c = 0; c < checksPerPath && !intersections.length; c++) {
    let pt = path1.getPointAtLength((pathLength1 / checksPerPath) * c);
    let inStroke = path0.isPointInStroke(pt);
    let inFill = path0.isPointInFill(pt);

    // check path 1 against path 2
    if (inStroke || inFill) {
      intersections.push(pt)
    } else {
      /**
       * no intersections found: 
       * check path1  sample points against path0
       */
      let pt1 = path0.getPointAtLength(
        (pathLength0 / checksPerPath) * c
      );

      let inStroke1 = path1.isPointInStroke(pt1);
      let inFill1 = path1.isPointInFill(pt1);

      if (inStroke1 || inFill1) {
        intersections.push(pt1)
      }
    }
    // just for benchmarking
    checks++;
  }

  // reset styles
  path0.style.fill = fill0;
  path0.style.strokeWidth = strokeWidth0;

  path1.style.fill = fill1;
  path1.style.strokeWidth = strokeWidth1;

  console.log('sample point checks:', checks);
  return intersections;

}

/**
 * simple performance test
 */

function perfStart() {
  t0 = performance.now();
}

function perfEnd(text = "") {
  t1 = performance.now();
  total = t1 - t0;
  console.log(`excecution time ${text}:  ${total} ms`);
  return total;
}

function renderPoint(
  svg,
  coords,
  fill = "red",
  r = "2",
  opacity = "1",
  id = "",
  className = ""
) {
  //console.log(coords);
  if (Array.isArray(coords)) {
    coords = {
      x: coords[0],
      y: coords[1]
    };
  }

  let marker = `<circle class="${className}" opacity="${opacity}" id="${id}" cx="${coords.x}" cy="${coords.y}" r="${r}" fill="${fill}">
    <title>${coords.x} ${coords.y}</title></circle>`;
  svg.insertAdjacentHTML("beforeend", marker);
}
body {
  font-family: sans-serif;
}

svg {
  width: 100%;
}

path {
  fill: none;
  stroke: #000;
  stroke-width: 1px;
}

p {
  white-space: pre-line;
}
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 500 150">

        <path id="p0" d="M27.357,21.433c13.373,3.432,21.433,17.056,18.001,30.43
 c-3.432,13.374-17.057,21.434-30.43,18.002" />
        <path id="p1" d="M80.652,80.414c-12.205,6.457-27.332,1.8-33.791-10.403
 c-6.458-12.204-1.8-27.333,10.404-33.791" />

        <path id="p2"
            d="M159.28 40.26c6.73 12.06 2.41 27.29-9.65 34.01s-27.29 2.41-34.01-9.65s-2.41-27.29 9.65-34.01c12.06-6.73 27.29-2.41 34.01 9.65z" />
        <path id="p3"
            d="M191.27 53.72c-0.7 13.79-12.45 24.4-26.24 23.7s-24.4-12.45-23.7-26.24s12.45-24.4 26.24-23.7s24.4 12.45 23.7 26.24z" />

        <path id="p4"
            d="M259.28 40.26c6.73 12.06 2.41 27.29-9.65 34.01s-27.29 2.41-34.01-9.65s-2.41-27.29 9.65-34.01c12.06-6.73 27.29-2.41 34.01 9.65z" />
        <path id="p5"
            d="M291.27 53.72c-0.7 13.79-12.45 24.4-26.24 23.7s-24.4-12.45-23.7-26.24s12.45-24.4 26.24-23.7s24.4 12.45 23.7 26.24z" />

        <path id="p6"
            d="M359.28 40.26c6.73 12.06 2.41 27.29-9.65 34.01s-27.29 2.41-34.01-9.65s-2.41-27.29 9.65-34.01c12.06-6.73 27.29-2.41 34.01 9.65z" />
        <path id="p7"
            d="M420 53.72c-0.7 13.79-12.45 24.4-26.24 23.7s-24.4-12.45-23.7-26.24s12.45-24.4 26.24-23.7s24.4 12.45 23.7 26.24z" />

        <g id="gInter"></g>

    </svg>
    
  <p>Based on @Netsi1964's codepen: 
https://codepen.io/netsi1964/pen/yKagwx/</p>  
<svg id="svg2" viewBox="0 0 2000 700">
<path d=" M  529 664  C  93 290  616 93  1942 385  C  1014 330  147 720  2059 70  C  1307 400  278 713  1686 691 " style="stroke:orange!important" stroke="orange" id="p8"/>
<path d=" M  1711 363  C  847 15  1797 638  1230 169  C  1198 443  1931 146  383 13  C  1103 286  1063 514  521 566 " id="p9"/>
<g id="gInter2"></g>
</svg>

<p><button onclick="check()">Check intersection</button></p>

<p id="time"></p>

<script src="https://cdn.jsdelivr.net/npm/path-data-polyfill@1.0.4/path-data-polyfill.min.js"></script>

This example calculates sample points from a parsed pathData array - retrieved with getPathData() (needs a polyfill).

All commands are normalized/converted via

path.getPathData({normalize:true})

to absolute coordinates using only M,C,L and Z.

We can now easily calculate points on bézier C commands with an interpolation helper.

function getPointAtCubicSegmentLength(p0, cp1, cp2, p, t=0.5) {
    let t1 = 1 - t;
    return {
        x: t1 ** 3 * p0.x + 3 * t1 ** 2 * t * cp1.x + 3 * t1 * t ** 2 * cp2.x + t ** 3 * p.x,
        y: t1 ** 3 * p0.y + 3 * t1 ** 2 * t * cp1.y + 3 * t1 * t ** 2 * cp2.y + t ** 3 * p.y
    }
}
  1. p0 = previous commands last point
  2. cp1 = first C control point
  3. cp2 = second control point
  4. p = C control end point
  5. t = split position: t=0.5 => middle of the curve

Admittedly, quite a chunk of code.
However way faster for calculating hundreds of sample points than using getPointAtLength().

Codepen example.

herrstrietzel
  • 11,541
  • 2
  • 12
  • 34