javascript - 如何在二次曲线上跟踪坐标

Question

我有一个 Polyline在 HiDPICanvas (html5 Canvas )。当我左右移动鼠标时，我会跟踪它的坐标，并在折线上具有相同 X 坐标的对应点上绘制 Circle .你现在可以试试看结果。

// 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>

但是如果你去评论 draw smooth polyline并取消注释下面的代码(以及绘制粗糙折线的注释线) - 现在它将绘制平滑的折线(二次贝塞尔曲线)。但是当您尝试左右移动鼠标时 - Circle有时会超出折线范围。
二次曲线之前:

二次曲线后:

这是一个问题 : 我计算了x, y Circle 的坐标使用 linear interpolation 在粗糙的折线上, 但是我怎么计算 x, y Circle 的坐标顺利quadratic curve ?
加 1 : 使用 Beizer curve 的二次曲线作为平滑折线时的计算基础
添加 2 对于那些有点坚持实现的人，我从 here 找到并保存了更简单的解决方案， 例子:

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>

只需遍历曲线的所有线并使用此模式找到最近的位置

Answer 1

这可以使用迭代搜索来完成，就像您对线条所做的那样。
顺便说一句，有很多 better way to find the closest point在复杂度为 的行上O(1) 而不是 O(n) 在哪里 n 是线段的长度。
搜索最近点
以下函数可用于二次和三次贝塞尔曲线，并将贝塞尔曲线上最近点的单位位置返回到给定坐标。
该函数还有一个属性 foundPoint具有找到的点的位置
该函数使用对象 Point定义二维坐标。
签名
该函数有两个签名，一个用于二次贝塞尔曲线，另一个用于三次。

closestPointOnBezier(point, resolution, p1, p2, cp1)

closestPointOnBezier(point, resolution, p1, p2, cp1, cp2)

在哪里

point如Point是要检查的位置

resolution如Number搜索贝塞尔曲线的近似分辨率。如果为 0，则固定为 DEFAULT_SCAN_RESOLUTION否则它是起点和终点之间的距离乘以 resolution IE 如果 resolution = 1如果 resolution = 2，则大约扫描为 1px那么大约扫描是 1/2px

p1 , p2如Point 's 是贝塞尔曲线的起点和终点

cp1 , cp2如Point是贝塞尔曲线的第一个和/或第二个控制点

结果

他们都返回 Number这是最近点贝塞尔曲线上的单位 pos。该值将是 0 <= result <= 1 其中 0 是贝塞尔曲线的开始，1 是结束

函数属性closestPointOnBezier.foundPoint如Point具有贝塞尔曲线上最近点的坐标，可用于计算到贝塞尔曲线上点的距离。

功能

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 
}

用法
在两个贝塞尔曲线上查找最近点的示例用法
定义的几何

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(?,?);

寻找最近的

// 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;
}

壁橱点是found如Point