I needed to find the nearest point on a Konva.Line shape to an arbitrary point on the canvas. See example below where the mouse pointer is the arbitrary point and the coloured line is the Konva.Line. I specifically needed a Konvajs implementation.
This is a self-answer question, see my solution below. I am open to any better suggestions.
After some web research I found a commonly used algorithm for finding the nearest point on a path. See article by mbostock. This required very little change to operate as I needed - see code in snippet below.
This works by taking an SVG-style path definition, using the get-path-length function (I stick to pseudo naming here as your lib may differ in exact naming, see snippet for the Konva versions) then iterates through a bunch of points on the path, found by the get-point-at-length function, to compute via simple maths the distance from each to the arbitrary point. Because there is a processing cost overhead for this, it uses a coarse step-basis to get an approximation then a more refined binary approach to get to the final result quickly. The result is a point - the nearest point on the path to the given arbitrary point.
So - enabling this in Konva...noting that the target is a free hand drawn line...
The first issue is that to draw a free hand line on the canvas in the context of Konva, you use a Line shape. The Line shape has an array of points that give the co-ordinates for points along the line. You give it the points and Konva joins the dots with a stroke to make a line. A freehand drawn line is simple to create by advancing the line to the mouse pointer position on each mouse move event (see snippet). However, there are no path measuring functions for the line's points array, so we have to convert the Konva.Line to a Konva.Path shape because this DOES have the path functions that we need.
The conversion of points to path is straightforward. The points array is laid out as [x1, y1, x2, y2, ... xn, yn], while a path is a string laid out as "M x1, y1 L x2, y2...L xn, yn". They can both be more complicated than that, but sticking to a simple line of connected dots works for this requirement. The snippet includes the pointsToPath() function.
Having now found a path the creation of the Konva.Path shape is simple.
// use the pointsToPath fn to prepare a path from the line points.
thePath = pointsToPath(lineShape.points());
// Make a path shape tracking the lineShape because path has more options for measuring.
pathShape = new Konva.Path({
stroke: 'cyan',
strokeWidth: 5,
data: thePath
});
layer.add(pathShape);
In the snippet I replace the line shape with the path shape, but it would be possible to not even add the shape to the canvas and just instantiate it for use in the closest point process.
So - having the path we can call the closestPoint() function giving it the mouse position and the path shape so that the function can invoke the measuring and point-at-length-getting functions as it needs.
// showing nearest point - link mouse pointer to the closest point on the line
const closestPt = closestPoint(pathShape, {x: mousePos.x, y: mousePos.y});
connectorLine.points([closestPt.x, closestPt.y, mousePos.x, mousePos.y]);
All that then remains is to use the closestPt value as required. In the snippet I draw a red line from the mouse pointer to the closest point on the freehand line.
The maths is efficient and the process can happen in real time as the mouse is moved. See snippet.
let isDrawing = false;
// Set up a stage
stage = new Konva.Stage({
container: 'container',
width: window.innerWidth,
height: window.innerHeight
}),
// add a layer to draw on
layer = new Konva.Layer(),
mode = 'draw', // state control, draw = drawing line, measuring = finding nearest point
lineShape = null, // the line shape that we draw
connectorLine = null, // link between mouse and nearest point
pathShape = null; // path element
// Add the layer to the stage
stage.add(layer);
// On this event, add a line shape to the canvas - we will extend the points of the line as the mouse moves.
stage.on('mousedown touchstart', function (e) {
reset();
var pos = stage.getPointerPosition();
if (mode === 'draw'){ // add the line that follows the mouse
lineShape = new Konva.Line({
stroke: 'magenta',
strokeWidth: 5,
points: [pos.x, pos.y],
draggable: true
});
layer.add(lineShape);
}
});
// when we finish drawing switch mode to measuring
stage.on('mouseup touchend', function () {
// use the pointsToPath fn to prepare a path from the line points.
thePath = pointsToPath(lineShape.points());
// Make a path shape tracking the lineShape because path has more options for measuring.
pathShape = new Konva.Path({
stroke: 'cyan',
strokeWidth: 5,
data: thePath
});
layer.add(pathShape);
lineShape.destroy(); // remove the path shape from the canvas as we are done with it
layer.batchDraw();
mode='measuring'; // switch the mode
});
// As the mouse is moved we aer concerned first with drawing the line, then measuring the nearest point from the mouse pointer on the line
stage.on('mousemove touchmove', function (e) {
// get position of mouse pointer
const mousePos = stage.getPointerPosition();
if (mode === 'draw' ){
if (lineShape) { // on first move we will not yet have this shape!
// drawing the line - extend the line shape by adding the mouse pointer position to the line points array
const newPoints = lineShape.points().concat([mousePos.x, mousePos.y]);
lineShape.points(newPoints); // update the line points array
}
}
else {
// showing nearest point - link mouse pointer to the closest point on the line
const closestPt = closestPoint(pathShape, {x: mousePos.x, y: mousePos.y});
connectorLine.points([closestPt.x, closestPt.y, mousePos.x, mousePos.y]);
}
layer.batchDraw();
});
// Function to make a Konva path from the points array of a Konva.Line shape.
// Returns a path that can be given to a Konva.Path as the .data() value.
// Points array is as [x1, y1, x2, y2, ... xn, yn]
// Path is a string as "M x1, y1 L x2, y2...L xn, yn"
var pointsToPath = function(points){
let path = '';
for (var i = 0; i < points.length; i = i + 2){
switch (i){
case 0: // move to
path = path + 'M ' + points[i] + ',' + points[i + 1] + ' ';
break;
default:
path = path + 'L ' + points[i] + ',' + points[i + 1] + ' ';
break;
}
}
return path;
}
// reset the canvas & shapes as needed for a clean restart
function reset() {
mode = 'draw';
layer.destroyChildren();
layer.draw();
connectorLine = new Konva.Line({
stroke: 'red',
strokeWidth: 1,
points: [0,0, -100, -100]
})
layer.add(connectorLine);
}
// reset when the user asks
$('#reset').on('click', function(){
reset();
})
reset(); // reset at startup to prepare state
// From article by https://bl.ocks.org/mbostock at https://bl.ocks.org/mbostock/8027637
// modified as prefixes (VW)
function closestPoint(pathNode, point) {
var pathLength = pathNode.getLength(), // (VW) replaces pathNode.getTotalLength(),
precision = 8,
best,
bestLength,
bestDistance = Infinity;
// linear scan for coarse approximation
for (var scan, scanLength = 0, scanDistance; scanLength <= pathLength; scanLength += precision) {
if ((scanDistance = distance2(scan = pathNode.getPointAtLength(scanLength))) < bestDistance) {
best = scan, bestLength = scanLength, bestDistance = scanDistance;
}
}
// binary search for precise estimate
precision /= 2;
while (precision > 0.5) {
var before,
after,
beforeLength,
afterLength,
beforeDistance,
afterDistance;
if ((beforeLength = bestLength - precision) >= 0 && (beforeDistance = distance2(before = pathNode.getPointAtLength(beforeLength))) < bestDistance) {
best = before, bestLength = beforeLength, bestDistance = beforeDistance;
} else if ((afterLength = bestLength + precision) <= pathLength && (afterDistance = distance2(after = pathNode.getPointAtLength(afterLength))) < bestDistance) {
best = after, bestLength = afterLength, bestDistance = afterDistance;
} else {
precision /= 2;
}
}
best = {x: best.x, y: best.y}; // (VW) converted to object instead of array, personal choice
best.distance = Math.sqrt(bestDistance);
return best;
function distance2(p) {
var dx = p.x - point.x, // (VW) converter to object from array
dy = p.y - point.y;
return dx * dx + dy * dy;
}
}body {
margin: 10;
padding: 10;
overflow: hidden;
background-color: #f0f0f0;
}
#container {
width: 600px;
height: 400px;
border: 1px solid silver;
}<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<script src="https://unpkg.com/konva@^3/konva.min.js"></script>
<p>Draw a line by click + drag. Move mouse to show nearest point on line function. </p>
<p>
<button id = 'reset'>Reset</button></span>
</p>
<div id="container"></div>