javascriptcanvaslinepath-finding

Connect points by going around them

I'm working on a line drawing feature for a web application (html canvas). It includes a line and a cluster of points. One end of the line is attached to an anchor point and the other is following the mouse pointer. As the mouse moves inside of the cluster, the line can get "caught up" on one or more points.

You can imagine how this works in real life, if you move a thread between pins on a map. By moving the thread around the pins you can make it stretch from one pin to another.

enter image description here

It's not enough that the line is in close proximity to a point (it's not snapping). There needs to be an intersection and the continued path of the thread needs to deviate from the earlier path. If the intersection occured on the right side of the pin the thread needs to move to the left, and vice versa.

enter image description here

At this point I haven't been able to produce any code that would be meaningful to show you. I already know how to draw a line and add new segments when a certain condition is met. What I don't have is a good definition of such a condition and a practical way to determine when it has been met. Any help would be very much appreciated.

I haven't been able to find any algorithms or other techniques that deal with this particular task.

Solution

  • Not sure I fully understand the task, but here is example implementation of what I do understand:

    const pinUrl = 'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABwAAAAcCAYAAAByDd+UAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAABdaVRYdFNuaXBNZXRhZGF0YQAAAAAAeyJjbGlwUG9pbnRzIjpbeyJ4IjowLCJ5IjowfSx7IngiOjI4LCJ5IjowfSx7IngiOjI4LCJ5IjoyOH0seyJ4IjowLCJ5IjoyOH1dfeeW5RYAAAQ9SURBVEhLnVY3Sy1hEB1zwoRZUTBhthEFESvtxAQ2WqiVaGshoqXY+RfExkLQSlBsDKCCghERzIiYMGPO8+bMu7te07t334GPe3d3ds43M2fmWxcWkB3e39/p+vqatra2aHl5mRYXF2l7e5vOzs7o6emJYO7p6Uk+Pj4UHh5O8fHxlJaWpis5OZlCQkLIzc3N5u0HgNDA8/MzLy0tcUtLC4sDFqfs6uqqy8XFxVz298Q5+/r6cmJiItfW1vLAwAAfHx/z29ubzetnmIQwmJub49LSUnUAZ9iPsYzrr7/2C5sICwvjuro6npmZ4cfHR5v3D5iER0dHXF9fz5Iu0yEceHl5saSJ4+LiOCkpSZekkaOiojgoKEjtEaU9sbu7O+fl5XF/fz/f3NzYGP5Ca4i6DQ4OUkNDg9ZKbpEQUX5+PpWXl1NKSgr5+/uTOCLZhNZZdk+3t7e0ublJU1NTJBGRpFKfAbBDTdva2qiyslLfV4BQRMKtra26U0SG37KyMhbBaF1/wsPDA5+cnPD+/j6LqHhoaIirq6s5MDDQTDcyhGygrrAHlBBFrqmpMYWAGvb09CByNfoKpEkyws3Nzdze3s7T09PqcG9vjzs7Ozk2NlZ9gRT+CgsLWTKh77prmDbItS4xooCAAP017otDuri4IImIxsfHqa+vjzY2Nsjb25teX19JaktCRE1NTRQcHEwdHR0kutB30Vqrq6uUkJBASigRUXR0tOZd1Kr9Njk5qT318vJC5+fnWquFhQWStqHDw0OSVKszkKHu2Mz9/T1dXl4qoYhMawob+Ds9PVXfuKEt0d3drX2HgLBQC6RGmlvvo65GmuyXiIGrqqq4sbGRS0pKODs7W9/x8PAwbfz8/FSxsrmPtpifn+f09PRPzozi/7bwHC0A5/hviM5YsMHzoqIiXltbUx6TEErt6urSxoWxIaCvJM4svAsi9GlFRQWPjY2Zav80S1GL4eFh7cmdnR29Rh1QJwN25grUXSIjiVIFBLFBD5JaEnVSQUEBxcTEaA8D34Y3GhoiAZmkgUZGRmhlZUVViuIfHByoDQDnMgopNzeXIiMjSepOEpWKJjQ0VK8NIhMg/A1CwKJIFkKds729vSzSNmuEMTc6OvrrcPgJrjbeH4FjSGYmZWZmUk5ODqWmpurIM4DdiwI1nc7in4RfgXrZO0dfaW9ZgCVCRAdhSDpVPKgrBoAVWCaEEACQYgpBSFZgiRAjMCIiQqPDuru7UzUbR5IzsESINsAZh74D0B4YzDgXnYUlQnw4ZWVlmScJBsLExATt7u7aLBzDEiFUmpGRoV9oAEjX19dpdnZW6+kMLBECGFPFxcXaowCUKkOBrq6u9NoRLBNCOJiPGAgGIB5j3DmCZUKkEYMZH0YgxYcwZqn5keQA34a3M8B0wWmCoY7UYgNItaHef+G/CAGQYsogYpBCUI5B9AcI4Zaprk7MAwAAAABJRU5ErkJggg==';

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const pinImage = new Image();
pinImage.onload = drawFrame;
pinImage.src = pinUrl;
const pinPositions = [{x: 40, y: 40}, {x: 100, y: 130}, {x: 400, y: 350}, {x: 300, y: 400}, {x: 270, y: 230}, {x: 50, y: 380}, {x: 460, y: 73}];
let unusedPins = [...pinPositions];
const drawedLines = [];
let lastMovePoint = {x: 40, y: 40};
const candidateLine = {x1: 40, y1: 40, x2: 40, y2: 40};

canvas.addEventListener('mousemove', ({offsetX, offsetY}) => {
  const prevPoint = {x: candidateLine.x2, y: candidateLine.y2};
  candidateLine.x2 = offsetX;
  candidateLine.y2 = offsetY;
  checkIntersection();
  lastMovePoint = prevPoint;
  unusedPins = unusedPins.filter(pin => !isPinInUse(pin));
});

function drawFrame() {
  ctx.beginPath();
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  
  for(const pin of pinPositions) {
    ctx.drawImage(pinImage, pin.x - 10, pin.y - 10, 20, 20);
  }
  
  ctx.strokeStyle = 'red';
  ctx.lineWidth = 2;
  ctx.moveTo(40, 40);
  
  for(const line of drawedLines) {
    ctx.lineTo(line.x2, line.y2);
  }

  ctx.stroke();
  ctx.closePath();
  
    if(drawedLines.length && drawedLines[0].x1 === drawedLines[drawedLines.length - 1].x2 && drawedLines[0].y1 === drawedLines[drawedLines.length - 1].y2) return;
    
  ctx.beginPath();
  ctx.lineWidth = 2;
  ctx.strokeStyle = 'green';
  const lastLine = drawedLines[drawedLines.length - 1] || {x2: 40, y2: 40}
  ctx.moveTo(lastLine.x2, lastLine.y2);
  ctx.lineTo(candidateLine.x2, candidateLine.y2);
  ctx.stroke();
  ctx.closePath();
  requestAnimationFrame(drawFrame);
}

function checkIntersection() {
  
  for(const pin of unusedPins) {
    const {x1, x2, y1, y2} = candidateLine;
    if(x1 === pin.x && y1 === pin.y) continue;
    if(isLineExist({x: x1, y: y1}, pin)) continue;
    if(isPointInTriangle({x: x1, y: y1}, {x: x2, y: y2}, lastMovePoint, pin)) {
      drawedLines.push({x1, y1, x2: pin.x, y2: pin.y});
      candidateLine.x1 = pin.x;
      candidateLine.y1 = pin.y;
    }
  }
}

function triangleArea(p1, p2, p3) {
  const area = (p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y)) / 2;
  return Math.abs(area);
}

function isPointInTriangle(p1, p2, p3, p) {
  return triangleArea(p1, p2, p3) === triangleArea(p1, p2, p) + triangleArea(p1, p, p3) + triangleArea(p, p2, p3);
}

function isLineExist(p1, p2) {
  return drawedLines.some(({x1, x2, y1, y2}) => x1 === p1.x && y1 === p1.y && x2 === p2.x && y2 === p2.y || x2 === p1.x && y2 === p1.y && x1 === p2.x && y1 === p2.y)
}

function isPinInUse({x, y}) {
  let isEntryFound = false, isExitFound = false;
  drawedLines.forEach(line => {
    isEntryFound ||= line.x1 === x && line.y1 === y;
    isExitFound ||= line.x2 === x && line.y2 === y;
  });
  
  return isEntryFound && isExitFound;
}

function restart() {
  drawedLines.splice(0, drawedLines.length);
  candidateLine.x1 = 40;
  candidateLine.y1 = 40;
  candidateLine.x2 = 40;
  candidateLine.y2 = 40;
  lastMovePoint = {x:40, y:40};
  unusedPins = [...pinPositions];
  drawFrame();
}
    #canvas {
  display: block;
  background: white;
  border: 1px solid darkgray;
}

button {
  margin-top: 10px;
}
    <canvas id="canvas" width="500" height="500"></canvas>
<button onClick="restart()">Restart</button>

    In above example I allowing only one entry+exit per pin, and exiting interaction once you closed a loop. Not sure if this is what you want though, but you can play with it into whatever you need.