javascript - 如何检测由贝塞尔曲线制成的物体与圆之间的碰撞？

Question

所以我写了一个微生物动画。这一切都很酷，但我认为，如果微生物能够吃掉硅藻并破坏气泡，那就更好了。

问题在于微生物是由贝塞尔曲线构成的。我不知道如何以合理的方式检查由贝塞尔曲线构成的对象与圆之间的碰撞。我唯一想到的是在隐藏的 Canvas 上绘制微生物形状和气泡，然后检查它们是否绘制到相同的像素。但这会导致严重的性能问题恕我直言。

代码:https://codepen.io/michaelKurowski/pen/opWeKY

class Cell 是单元格，而 class CellWallNode 是贝塞尔曲线的节点，以防有人需要查看实现。

气泡和硅藻可以很容易地简化为圆形。

Answer 1

beziers定义的bounds testing object的解决方案

下面是一个示例解决方案，用于查找圆是否位于由中心点和一组定义周长的贝塞尔曲线定义的对象内。

该解决方案仅针对非相交的立方贝塞尔曲线进行了测试。如果被测对象和单元格中心之间有两个以上的截距，也将不起作用。然而，您需要解决的更复杂的界限都在代码中。

方法

1. 定义一个中心点作为二维点进行测试
2. 将测试点定义为二维点
3. 定义一条从中心到测试点的线
4. 对于每个贝塞尔曲线
5. 翻译贝塞尔曲线，所以第一个点在行的开头
6. 旋转贝塞尔曲线，使直线与 x 轴对齐
7. 求解贝塞尔多项式以求根(x 轴截距的位置)
8. 利用根求直线截距在贝塞尔曲线上的位置。
9. 使用离该点最近的截距来计算从中心到周边的距离。
10. 如果周长距离大于测试点距离加上半径则在内部。

注意事项

测试是沿着一条线到中心的一个点，而不是一个由三 Angular 形定义的区域的圆。只要圆半径与贝塞尔曲线的大小相比较小，近似就可以很好地工作。

不确定您使用的是三次贝塞尔曲线还是二次贝塞尔曲线，因此该解决方案涵盖了三次贝塞尔曲线和二次贝塞尔曲线。

例子

该代码段围绕一个中心点创建了一组贝塞尔曲线(立方体)。对象 theBlob 包含动画贝塞尔曲线。 testBlob 函数测试鼠标位置，如果在 theBlob 内则返回 true。对象 bezHelper 包含解决问题所需的所有功能。

立方根求解器源自 github intersections立方根求解器。

const bezHelper = (()=>{
    // creates a 2D point
    const P2 = (x=0, y= x === 0 ? 0 : x.y + (x = x.x, 0)) => ({x, y});
    const setP2As = (p,pFrom) => (p.x = pFrom.x, p.y = pFrom.y, p);
    // To prevent heap thrashing close over some pre defined 2D points
    const v1 = P2();
    const v2 = P2();
    const v3 = P2();
    const v4 = P2();
    var u,u1,u2;
    
    // solves quadratic for bezier 2 returns first root
    function solveBezier2(A, B, C){ 
        // solve the 2nd order bezier equation.
        // There can be 2 roots, u,u1 hold the results;
        // 2nd order function a+2(-a+b)x+(a-2b+c)x^2
        a = (A - 2 * B + C);
        b = 2 * ( - A + B);
        c = A;
        a1 = 2 * a;
        c = b * b - 4 * a * c;
        if(c < 0){ 
            u = Infinity;       
            u1 = Infinity;       
            return u;
        }else{
            b1 = Math.sqrt(c);
        }
        u = (-b + b1) / a1;
        u1 = (-b - b1) / a1;
        return u;
    
    }
    // solves cubic for bezier 3 returns first root
    function solveBezier3(A, B, C, D){  
        // There can be 3 roots, u,u1,u2 hold the results;
        // Solves 3rd order a+(-2a+3b)t+(2a-6b+3c)t^2+(-a+3b-3c+d)t^3 Cardano method for finding roots
        // this function was derived from http://pomax.github.io/bezierinfo/#intersections cube root solver
        // Also see https://en.wikipedia.org/wiki/Cubic_function#Cardano.27s_method

        function crt(v) {
          if(v<0) return -Math.pow(-v,1/3);
          return Math.pow(v,1/3);
        }                
        function sqrt(v) {
          if(v<0) return -Math.sqrt(-v);
          return Math.sqrt(v);
        }        
        var a, b, c, d, p, p3, q, q2, discriminant, U, v1, r, t, mp3, cosphi,phi, t1, sd;
        u2 = u1 = u = -Infinity;
        d = (-A + 3 * B - 3 * C + D);
        a = (3 * A - 6 * B + 3 * C) / d;
        b = (-3 * A + 3 * B) / d;
        c = A / d;
        p = (3 * b - a * a) / 3;
        p3 = p / 3;
        q = (2 * a * a * a - 9 * a * b + 27 * c) / 27;
        q2 = q / 2;
        a /= 3;
        discriminant = q2 * q2 + p3 * p3 * p3;
        if (discriminant < 0) {
            mp3 = -p / 3;
            r = sqrt(mp3 * mp3 * mp3);
            t = -q / (2 * r);
            cosphi = t < -1 ? -1 : t > 1 ? 1 : t;
            phi = Math.acos(cosphi);
            t1 = 2 * crt(r);
            u = t1 * Math.cos(phi / 3) - a;
            u1 = t1 * Math.cos((phi + 2 * Math.PI) / 3) - a;
            u2 = t1 * Math.cos((phi + 4 * Math.PI) / 3) - a;
            return u;
        }
        if(discriminant === 0) {
            U = q2 < 0 ? crt(-q2) : -crt(q2);
            u = 2 * U - a;           
            u1 = -U - a;            
            return u;
        }                
        sd = sqrt(discriminant);
        u = crt(sd - q2) - crt(sd + q2) - a; 
        return u;      
    }    
    
    
    
    
    // get a point on the bezier at pos ( from 0 to 1 values outside this range will be outside the bezier)
    // p1, p2 are end points and cp1, cp2 are control points.
    // ret is the resulting point. If given it is set to the result, if not given a new point is created
    function getPositionOnBez(pos,p1,p2,cp1,cp2,ret = P2()){
        if(pos === 0){
            ret.x = p1.x;
            ret.y = p1.y;
            return ret;
        }else
        if(pos === 1){
            ret.x = p2.x;
            ret.y = p2.y;
            return ret;
        }                
        v1.x = p1.x;
        v1.y = p1.y;
        var c = pos;
        if(cp2 === undefined){
            v2.x = cp1.x;
            v2.y = cp1.y;
            v1.x += (v2.x - v1.x) * c;
            v1.y += (v2.y - v1.y) * c;
            v2.x += (p2.x - v2.x) * c;
            v2.y += (p2.y - v2.y) * c;
            ret.x = v1.x + (v2.x - v1.x) * c;
            ret.y = v1.y + (v2.y - v1.y) * c;
            return ret;
        }
        v2.x = cp1.x;
        v2.y = cp1.y;
        v3.x = cp2.x;
        v3.y = cp2.y;
        v1.x += (v2.x - v1.x) * c;
        v1.y += (v2.y - v1.y) * c;
        v2.x += (v3.x - v2.x) * c;
        v2.y += (v3.y - v2.y) * c;
        v3.x += (p2.x - v3.x) * c;
        v3.y += (p2.y - v3.y) * c;
        v1.x += (v2.x - v1.x) * c;
        v1.y += (v2.y - v1.y) * c;
        v2.x += (v3.x - v2.x) * c;
        v2.y += (v3.y - v2.y) * c;
        ret.x = v1.x + (v2.x - v1.x) * c;
        ret.y = v1.y + (v2.y - v1.y) * c;
        return ret;  
    }
    const cubicBez = 0;
    const quadraticBez = 1;
    const none = 2;
    var type = none;
    
    // working bezier
    const p1 = P2();
    const p2 = P2();
    const cp1 = P2();
    const cp2 = P2();
    // rotated bezier
    const rp1 = P2();
    const rp2 = P2();
    const rcp1 = P2();
    const rcp2 = P2();
    // translate and rotate bezier
    function transformBez(pos,rot){
        const ax = Math.cos(rot);
        const ay = Math.sin(rot); 
        var x = p1.x - pos.x;
        var y = p1.y - pos.y;
        rp1.x = x * ax - y * ay;
        rp1.y = x * ay + y * ax;
        x = p2.x - pos.x;
        y = p2.y - pos.y;
        rp2.x = x * ax - y * ay;
        rp2.y = x * ay + y * ax;
        x = cp1.x - pos.x;
        y = cp1.y - pos.y;
        rcp1.x = x * ax - y * ay;
        rcp1.y = x * ay + y * ax;       
        if(type === cubicBez){
            x = cp2.x - pos.x;
            y = cp2.y - pos.y;
            rcp2.x = x * ax - y * ay;
            rcp2.y = x * ay + y * ax;       
        }
    }
    function getPosition2(pos,ret){
        return getPositionOnBez(pos,p1,p2,cp1,undefined,ret);
    }
    function getPosition3(pos,ret){
        return getPositionOnBez(pos,p1,p2,cp1,cp2,ret);
    }
    const API = {
        getPosOnQBez(pos,p1,cp1,p2,ret){
            return getPositionOnBez(pos,p1,p2,cp1,undefined,ret);
        },
        getPosOnCBez(pos,p1,cp1,cp2,p2,ret){
            return getPositionOnBez(pos,p1,p2,cp1,cp2,ret);
        },
        set bezQ(points){
            setP2As(p1, points[0]);
            setP2As(cp1, points[1]);
            setP2As(p2, points[2]);
            type = quadraticBez;
        },
        set bezC(points){
            setP2As(p1, points[0]);
            setP2As(cp1, points[1]);
            setP2As(cp2, points[2]);
            setP2As(p2, points[3]);
            type = cubicBez;
        },
        isInside(center, testPoint, pointRadius){
            drawLine(testPoint , center);
            v1.x = (testPoint.x - center.x);
            v1.y = (testPoint.y - center.y);
            const pointDist = Math.sqrt(v1.x * v1.x + v1.y * v1.y)
            const dir = -Math.atan2(v1.y,v1.x);
            transformBez(center,dir);
            if(type === cubicBez){
                solveBezier3(rp1.y, rcp1.y, rcp2.y, rp2.y); 
                if (u < 0 || u > 1)  { u = u1 }
                if (u < 0 || u > 1)  { u = u2 }
                if (u < 0 || u > 1)  { return }
                getPosition3(u, v4);
            }else{
                solveBezier2(rp1.y, rcp1.y, rp2.y);   
                if (u < 0 || u > 1)  { u = u1 }
                if (u < 0 || u > 1)  { return }
                getPosition2(u, v4);
                
            }
            drawCircle(v4);
            const dist = Math.sqrt((v4.x - center.x) ** 2 + (v4.y - center.y) ** 2);
            const dist1 = Math.sqrt((v4.x - testPoint.x) ** 2 + (v4.y - testPoint.y) ** 2); 
            return dist1 < dist && dist > pointDist - pointRadius;
        }
    }
                
                
                
    return API;        
})();                














const ctx = canvas.getContext("2d");
const m  = {x : 0, y : 0};
document.addEventListener("mousemove",e=>{
	var b = canvas.getBoundingClientRect();
	m.x = e.pageX - b.left - scrollX - 2;
	m.y = e.pageY - b.top - scrollY - 2;
});   
function drawCircle(p,r = 5,col = "black"){
    ctx.beginPath();
    ctx.strokeStyle = col;
    ctx.arc(p.x,p.y,r,0,Math.PI*2)
    ctx.stroke();
}
function drawLine(p1,p2,r = 5,col = "black"){
    ctx.beginPath();
    ctx.strokeStyle = col;
    ctx.lineTo(p1.x,p1.y);
    ctx.lineTo(p2.x,p2.y);
    ctx.stroke();
}

const w = 400;
const h = 400;
const diag = Math.sqrt(w * w + h * h);
// creates a 2D point
const P2 = (x=0, y= x === 0 ? 0 : x.y + (x = x.x, 0)) => ({x, y});
const setP2As = (p,pFrom) => (p.x = pFrom.x, p.y = pFrom.y, p);
// random int and double
const randI = (min, max = min + (min = 0)) => (Math.random()*(max - min) + min) | 0;
const rand = (min = 1, max = min + (min = 0)) => Math.random() * (max - min) + min;

const theBlobSet = [];
const theBlob = [];
function createCubicBlob(segs){
  const step = Math.PI / segs;
  for(var i = 0; i < Math.PI * 2; i += step){
    const dist = rand(diag * (1/6), diag * (1/5));
    const ang = i + rand(-step * 0.2,step * 0.2);
    
    const p = P2(
      w / 2 + Math.cos(ang) * dist,
      h / 2 + Math.sin(ang) * dist
    );  
    theBlobSet.push(p);
    theBlob.push(P2(p));
  }
  theBlobSet[theBlobSet.length -1] = theBlobSet[0];
  theBlob[theBlobSet.length -1] = theBlob[0];
}
createCubicBlob(8);
function animateTheBlob(time){
  for(var i = 0; i < theBlobSet.length-1; i++){
    const ang = Math.sin(time + i) * 6;
    theBlob[i].x = theBlobSet[i].x + Math.cos(ang) * diag * 0.04;
    theBlob[i].y = theBlobSet[i].y + Math.sin(ang) * diag * 0.04;
  }
}

function drawTheBlob(){
  ctx.strokeStyle = "black";
  ctx.lineWidth = 3;
  ctx.beginPath();
  var i = 0;
  ctx.moveTo(theBlob[i].x,theBlob[i++].y);
  while(i < theBlob.length){
    ctx.bezierCurveTo(
      theBlob[i].x,theBlob[i++].y,
      theBlob[i].x,theBlob[i++].y,
      theBlob[i].x,theBlob[i++].y
    );
  }
  ctx.stroke();
}
var center = P2(w/2,h/2);
function testBlob(){
  var i = 0;
  while(i < theBlob.length-3){
    bezHelper.bezC = [theBlob[i++], theBlob[i++], theBlob[i++], theBlob[i]];
    if(bezHelper.isInside(center,m,6)){
      return true;
    }
  }
  return false;
}


// main update function
function update(timer){
    ctx.clearRect(0,0,w,h);
    animateTheBlob(timer/1000)
    drawTheBlob();
    
    if(testBlob()){
        ctx.strokeStyle = "red";
    }else{
       ctx.strokeStyle = "black";
    }
    ctx.beginPath();
    ctx.arc(m.x,m.y,5,0,Math.PI*2)
    ctx.stroke();
    requestAnimationFrame(update);
}
requestAnimationFrame(update);

canvas { border : 2px solid black; }

<canvas id="canvas" width = "400" height = "400"></canvas>