4

I have a Polyline on the HiDPICanvas (html5 canvas). When I move mouse left and right I track its coordinates and on corresponding point with same X coordinate on the polyline I draw a Circle. You can try it now to see the result.

// Create a canvas
var HiDPICanvas = function(container_id, color, w, h) {
    /*
    objects are objects on the canvas, first elements of dictionary are background elements, last are on the foreground
    canvas will be placed in the container
    canvas will have width w and height h
    */
    var objects = {
        box     : [],
        borders : [],
        circles : [],
        polyline: []
    }
    var doNotMove = ['borders']
    // is mouse down & its coords
    var mouseDown = false
    lastX = window.innerWidth/2
    lastY = window.innerHeight/2

    // return pixel ratio
    var getRatio = function() {
        var ctx = document.createElement("canvas").getContext("2d");
        var dpr = window.devicePixelRatio || 1;
        var bsr = ctx.webkitBackingStorePixelRatio ||
                    ctx.mozBackingStorePixelRatio ||
                    ctx.msBackingStorePixelRatio ||
                    ctx.oBackingStorePixelRatio ||
                    ctx.backingStorePixelRatio || 1;
    
        return dpr / bsr;
    }

    // return high dots per inch canvas
    var createHiDPICanvas = function() {
        var ratio = getRatio();
        var chart_container = document.getElementById(container_id);
        var can             = document.createElement("canvas");
        can.style.backgroundColor = color
        can.width           = w * ratio;
        can.height          = h * ratio;
        can.style.width     = w + "px";
        can.style.height    = h + "px";
        can.getContext("2d").setTransform(ratio, 0, 0, ratio, 0, 0);
        chart_container.appendChild(can);
        return can;
    }

    // add object to the canvas
    var add = function(object, category) {
        objects[category].push(object)
    }

    // clear canvas
    var clearCanvas = function(x0, y0, x1, y1) {
        ctx.clearRect(x0, y0, x1, y1);
        ctx.beginPath();
        ctx.globalCompositeOperation = "source-over";
        ctx.globalAlpha = 1;
        ctx.closePath();
    }

    // check function do I can move this group of objects
    var canMove = function(groupname) {
        for (var i = 0; i < doNotMove.length; i++) {
            var restricted = doNotMove[i]
            if (restricted == groupname) {
                return false
            }
        }
        return true
    }

    // refresh all objects on the canvas
    var refresh = function() {
        clearCanvas(0, 0, w, h)
        var object
        for (var key in objects) {
            for (var i = 0; i < objects[key].length; i++) {
                object = objects[key][i]
                object.refresh()
            }
        }
    }

    // shift all objects on the canvas except left and down borders and its content
    var shiftObjects = function(event) {
        event.preventDefault()
        // if mouse clicked now -> we can move canvas view left\right
        if (mouseDown) {
            var object
            for (var key in objects) {
                if (canMove(key)) {
                    for (var i = 0; i < objects[key].length; i++) {
                        object = objects[key][i]
                        object.move(event.movementX, event.movementY)
                    }   
                }
            }
            cci.refresh()
        }
    }
    
    // transfer x to canvas drawing zone x coord (for not drawing on borders of the canvas)
    var transferX = function(x) {
        return objects.borders[0].width + x
    }

    var transferCoords = function(x, y) {
        // no need to transfer y because borders are only at the left
        return {
            x : transferX(x),
            y : y
        }
    }

    // change mouse state on the opposite
    var toggleMouseState = function() {
        mouseDown = !mouseDown
    }

    // make mouseDown = false, (bug removal function when mouse down & leaving the canvas)
    var refreshMouseState = function() {
        mouseDown = false
    }

    // print information about all objects on the canvas
    var print = function() {
        var groupLogged = true
        console.log("Objects on the canvas:")
        for (var key in objects) {
            groupLogged = !groupLogged
            if (!groupLogged) {console.log(key, ":"); groupLogged = !groupLogged}
            for (var i = 0 ; i < objects[key].length; i++) {
                console.log(objects[key][i])
            }
        }
    }

    var restrictEdges = function() {
        console.log("offsetLeft", objects['borders'][0])
    }

    var getMouseCoords = function() {
        return {
            x : lastX,
            y : lastY
        }
    }

    var addCircleTracker = function() {
        canvas.addEventListener("mousemove", (e) => {
            var polyline = objects.polyline[0]
            var mouseCoords = getMouseCoords()
            var adjNodes = polyline.get2NeighbourNodes(mouseCoords.x)
            if (adjNodes != -1) {
                var prevNode   = adjNodes.prev
                var currNode   = adjNodes.curr
                var cursorNode = polyline.linearInterpolation(prevNode, currNode, mouseCoords.x)
                // cursorNode.cursorX, cursorNode.cursorY are coords
                // for circle that should be drawn on the polyline
                // between the closest neighbour nodes
                var circle = objects.circles[0]
                circle.changePos(cursorNode.x, cursorNode.y)
                refresh()
            }
        })
    }

    // create canvas
    var canvas = createHiDPICanvas()
    addCircleTracker()
    
    // we created canvas so we can track mouse coords
    var trackMouse = function(event) {
        lastX = event.offsetX || (event.pageX - canvas.offsetLeft)
        lastY = event.offsetY || (event.pageY - canvas.offsetTop)
    }

    // 2d context
    var ctx = canvas.getContext("2d")
    // add event listeners to the canvas
    canvas.addEventListener("mousemove" ,         shiftObjects         )
    canvas.addEventListener("mousemove",  (e) =>{ trackMouse(e)       })
    canvas.addEventListener("mousedown" , () => { toggleMouseState () })
    canvas.addEventListener("mouseup"   , () => { toggleMouseState () })
    canvas.addEventListener("mouseleave", () => { refreshMouseState() })
    canvas.addEventListener("mouseenter", () => { refreshMouseState() })

    return {
        // base objects
        canvas : canvas,
        ctx    : ctx,
        // sizes of the canvas
        width  : w,
        height : h,
        color  : color,
        // add object on the canvas for redrawing
        add    : add,
        print  : print,
        // refresh canvas
        refresh: refresh,
        // objects on the canvas
        objects: objects,
        // get mouse coords
        getMouseCoords : getMouseCoords
    }

}

// cci -> canvas ctx info (dict)
var cci = HiDPICanvas("lifespanChart", "bisque", 780, 640)
var ctx           = cci.ctx
var canvas        = cci.canvas


var Polyline = function(path, color) {
    
    var create = function() {
        if (this.path === undefined) {
            this.path = path
            this.color = color
        }
        ctx.save()
        ctx.beginPath()
        p = this.path
        ctx.fillStyle = color
        ctx.moveTo(p[0].x, p[0].y)
        for (var i = 0; i < p.length - 1; i++) {
            var currentNode = p[i]
            var nextNode    = p[i+1]
            
            // draw smooth polyline
            // var xc = (currentNode.x + nextNode.x) / 2;
            // var yc = (currentNode.y + nextNode.y) / 2;
            // taken from https://stackoverflow.com/a/7058606/13727076
            // ctx.quadraticCurveTo(currentNode.x, currentNode.y, xc, yc);
            
            // draw rough polyline
            ctx.lineTo(currentNode.x, currentNode.y)
        }
        ctx.stroke()
        ctx.restore()
        ctx.closePath()
    }
    // circle that will track mouse coords and be
    // on the corresponding X coord on the path
    // following mouse left\right movements
    var circle = new Circle(50, 50, 5, "purple")
    cci.add(circle, "circles")
    create()

    var get2NeighbourNodes = function(x) {
        // x, y are cursor coords on the canvas 
        //
        // Get 2 (left and right) neighbour nodes to current cursor x,y
        // N are path nodes, * is Node we search coords for
        //
        // N-----------*----------N
        //
        for (var i = 1; i < this.path.length; i++) {
            var prevNode = this.path[i-1]
            var currNode = this.path[i]
            if ( prevNode.x <= x && currNode.x >= x ) {
                return {
                    prev : prevNode,
                    curr : currNode
                }
            }
        }
        return -1
    }

    var linearInterpolation = function(prevNode, currNode, cursorX) {
        // calculate x, y for the node between 2 nodes
        // on the path using linearInterpolation
        // https://en.wikipedia.org/wiki/Linear_interpolation
        var cursorY = prevNode.y + (cursorX - prevNode.x) * ((currNode.y - prevNode.y)/(currNode.x - prevNode.x))
        
        return {
            x : cursorX,
            y : cursorY
        }
    }

    var move = function(diff_x, diff_y) {
        for (var i = 0; i < this.path.length; i++) {
            this.path[i].x += diff_x
            this.path[i].y += diff_y
        }
    }
    
    return {
        create : create,
        refresh: create,
        move   : move,
        get2NeighbourNodes : get2NeighbourNodes,
        linearInterpolation : linearInterpolation,
        path   : path,
        color  : color
    }


}

var Circle = function(x, y, radius, fillStyle) {
    
    var create = function() {
        if (this.x === undefined) {
            this.x = x
            this.y = y
            this.radius = radius
            this.fillStyle = fillStyle
        }
        ctx.save()
        ctx.beginPath()
        ctx.arc(this.x, this.y, radius, 0, 2*Math.PI)
        ctx.fillStyle = fillStyle
        ctx.strokeStyle = fillStyle
        ctx.fill()
        ctx.stroke()
        ctx.closePath()
        ctx.restore()
    }
    create()

    var changePos = function(new_x, new_y) {
        this.x = new_x
        this.y = new_y
    }

    var move = function(diff_x, diff_y) {
        this.x += diff_x
        this.y += diff_y
    }

    return {
        refresh : create,
        create  : create,
        changePos: changePos,
        move    : move,
        radius  : radius,
        x       : this.x,
        y       : this.y
    }
}

var Node = function(x, y) {
    this.x = x
    this.y = y
    return {
        x : this.x,
        y : this.y
    }
} 

var poly   = new Polyline([
    Node(30,30), Node(150,150), 
    Node(290, 150), Node(320,200), 
    Node(350,350), Node(390, 250), 
    Node(450, 140)
], "green")

cci.add(poly, "polyline")
<div>
        <div id="lifespanChart"></div>
    </div>

But if you go to the comment draw smooth polyline and uncomment code below (and comment line that draws rough polyline) - it will draw smooth polyline now (quadratic Bézier curve). But when you try to move mouse left and right - Circle sometimes goes out of polyline bounds.

before quadratic curve:

enter image description here

after quadratic curve:

enter image description here

Here is a question : I calculated x, y coordinates for the Circle on the rough polyline using linear interpolation, but how could I calculate x, y coordinates for the Circle on the smooth quadratic curve?

ADD 1 : QuadraticCurve using Beizer curve as a base in calculations when smoothing polyline

ADD 2 For anyone who a little stucked with the implementation I found & saved easier solution from here, example:

var canvas = document.getElementById("canv")
var canvasRect = canvas.getBoundingClientRect()
var ctx = canvas.getContext('2d')


var p0 = {x : 30, y : 30}
var p1 = {x : 20, y :100}
var p2 = {x : 200, y :100}
var p3 = {x : 200, y :20}

// Points are objects with x and y properties
// p0: start point
// p1: handle of start point
// p2: handle of end point
// p3: end point
// t: progression along curve 0..1
// returns an object containing x and y values for the given t
// link https://stackoverflow.com/questions/14174252/how-to-find-out-y-coordinate-of-specific-point-in-bezier-curve-in-canvas
var BezierCubicXY = function(p0, p1, p2, p3, t) {
    var ret = {};
    var coords = ['x', 'y'];
    var i, k;

    for (i in coords) {
        k = coords[i];
        ret[k] = Math.pow(1 - t, 3) * p0[k] + 3 * Math.pow(1 - t, 2) * t * p1[k] + 3 * (1 - t) * Math.pow(t, 2) * p2[k] + Math.pow(t, 3) * p3[k];
    }

    return ret;
}

var draw_poly = function () {
  ctx.beginPath()
  ctx.lineWidth=2
  ctx.strokeStyle="white"
  ctx.moveTo(p0.x, p0.y)// start point
  //                 cont        cont        end
  ctx.bezierCurveTo(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)
  ctx.stroke()
  ctx.closePath()
}
var clear_canvas = function () {
  ctx.clearRect(0,0,300,300);
  ctx.beginPath();
  ctx.globalCompositeOperation = "source-over";
  ctx.globalAlpha = 1;
  ctx.closePath();
};
var draw_circle = function(x, y) {
    ctx.save();
    // semi-transparent arua around the circle
    ctx.globalCompositeOperation = "source-over";
    ctx.beginPath()
    ctx.fillStyle = "white"
    ctx.strokeStyle = "white"
    ctx.arc(x, y, 5, 0, 2 * Math.PI);
    ctx.stroke();
    ctx.closePath();
    ctx.restore();
}
var refresh = function(circle_x, circle_y) {
  clear_canvas()
  draw_circle(circle_x, circle_y)
  draw_poly()
}

var dist = function(mouse, point) {
  return Math.abs(mouse.x - point.x)
  // return ((mouse.x - point.x)**2 + (mouse.y - point.y)**2)**0.5
}

var returnClosest = function(curr, prev) {
  if (curr < prev) {
    return curr
  }
  return prev
}

refresh(30,30)
canvas.addEventListener("mousemove", (e) => {
  var mouse = {
     x : e.clientX - canvasRect.left, 
     y : e.clientY - canvasRect.top
  }
  
  var Point = BezierCubicXY(p0, p1, p2, p3, 0)
  for (var t = 0; t < 1; t += 0.01) {
    var nextPoint = BezierCubicXY(p0, p1, p2, p3, t)
    if (dist(mouse, Point) > dist(mouse, nextPoint)) {
      Point = nextPoint
    }
    // console.log(Point)
  }
  
  refresh(Point.x, Point.y)
  
})
canvas {
  background: grey;
}
<canvas id="canv" width = 300 height = 300></canvas>

Just iterate through all the lines of the curve & find closest position using this pattern

Aquill
  • 69
  • 6

1 Answers1

2

This can be done using an iterative search, as you have done with the lines.

BTW there is a much better way to find the closest point on a line that has a complexity of O(1) rather than O(n) where n is length of line segment.

Search for closest point

The following function can be used for both quadratic and cubic beziers and returns the unit position of closest point on bezier to a given coordinate.

The function also has a property foundPoint that has the position of the point found

The function uses the object Point that defines a 2D coordinate.

Signatures

The function has two signatures, one for quadratic beziers and the other for cubic.

  1. closestPointOnBezier(point, resolution, p1, p2, cp1)
  2. closestPointOnBezier(point, resolution, p1, p2, cp1, cp2)

Where

  • point as Point is the position to check
  • resolution as Number The approx resolution to search the bezier. If 0 then this is fixed to DEFAULT_SCAN_RESOLUTION else it is the distance between start and end points times resolution IE if resolution = 1 then approx scan is 1px, if resolution = 2 then approx scan is 1/2px
  • p1, p2 as Point's are the start and end points of the bezier
  • cp1, cp2 as Point's are the first and/or second control points of the bezier

Results

  • They both return Number that is the unit pos on the bezier of closest point. The value will be 0 <= result <= 1 Where 0 is at start of bezier and 1 is end
  • The function property closestPointOnBezier.foundPoint as Point has the coordinate of the closest point on the bezier and can be used to calculate the distance to the point on the bezier.

The function

const Point = (x = 0, y = 0) => ({x, y});
const MAX_RESOLUTION = 2048;
const DEFAULT_SCAN_RESOLUTION = 256;
closestPointOnBezier.foundPoint = Point();
function closestPointOnBezier(point, resolution, p1, p2, cp1, cp2) {  
    var unitPos, a, b, b1, c, i, vx, vy, closest = Infinity;
    const v1 = Point(p1.x - point.x, p1.y - point.y);
    const v2 = Point(p2.x - point.x, p2.y - point.y);
    const v3 = Point(cp1.x - point.x, cp1.y - point.y);
    resolution = resolution > 0 && reolution < MAX_RESOLUTION ? (Math.hypot(p1.x - p2.x, p1.y - p2.y) + 1) * resolution : 100;
    const fp = closestPointOnBezier.foundPoint;
    const step = 1 / resolution;
    const end = 1 + step / 2;
    const checkClosest = (e = (vx * vx + vy * vy) ** 0.5) => {
        if (e < closest ){
            unitPos = i;
            closest = e;
            fp.x = vx;
            fp.y = vy;
        }        
    }
    if (cp2 === undefined) {  // find quadratic 
        for (i = 0; i <= end; i += step) {
            a = (1 - i); 
            c = i * i; 
            b = a*2*i;
            a *= a;  
            vx = v1.x * a + v3.x * b + v2.x * c;
            vy = v1.y * a + v3.y * b + v2.y * c;
            checkClosest();
        }
    } else { // find cubic
        const v4 = Point(cp2.x - point.x, cp2.y - point.y);
        for (i = 0; i <= end; i += step) { 
            a = (1 - i); 
            c = i * i; 
            b = 3 * a * a * i; 
            b1 = 3 * c * a; 
            a = a * a * a;
            c *= i; 
            vx = v1.x * a + v3.x * b + v4.x * b1 + v2.x * c;
            vy = v1.y * a + v3.y * b + v4.y * b1 + v2.y * c;
            checkClosest();
        }
    }    
    return unitPos < 1 ? unitPos : 1; // unit pos on bezier. clamped 
}

Usage

Example usage to find closest point on two beziers

The defined geometry

const bzA = {
    p1: Point(10, 100),   // start point
    p2: Point(200, 400),  // control point
    p3: Point(410, 500),  // end point
};
const bzB = {
    p1: bzA.p3,           // start point
    p2: Point(200, 400),  // control point
    p3: Point(410, 500),  // end point
};
const mouse = Point(?,?);

Finding closest

// Find first point
closestPointOnBezier(mouse, 2, bzA.p1, bzA.p3, bzA.p2);

// copy point
var found = Point(closestPointOnBezier.foundPoint.x, closestPointOnBezier.foundPoint.y);

// get distance to mouse
var dist = Math.hypot(found.x - mouse.x, found.y - mouse.y);

// find point on second bezier
closestPointOnBezier(mouse, 2, bzB.p1, bzB.p3, bzB.p2);

// get distance of second found point
const distB = Math.hypot(closestPointOnBezier.foundPoint.x - mouse.x, closestPointOnBezier.foundPoint.y - mouse.y);

// is closer
if (distB < dist) {
    found.x = closestPointOnBezier.foundPoint.x;
    found.y = closestPointOnBezier.foundPoint.y;
    dist = distB;
}

The closet point is found as Point

Blindman67
  • 51,134
  • 11
  • 73
  • 136
  • Thank you, it was really helpful! – Aquill Sep 07 '20 at 14:32
  • One question. Could you tell me - why you use you search here between 2 beizers, not between 2 neighbouring nodes? For linear interpolation I return 2 nodes --> should I return 2 beizers for using this function? – Aquill Sep 07 '20 at 14:53