二次贝塞尔曲线路径与直线的交点

问题描述 投票：0回答：2

我正在使用一个 svg 元素，其中包含 SVG 路径和垂直线形式的二次贝塞尔曲线。如何以编程方式计算它们之间的交集？

我已经提到了this，当我插入这个问题中的数字时，它返回完全相同的值，但不是我在SVG中的原始数字。

//referred to https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
var lerp = function(a, b, x) { return (a + x * (b - a)); };

// qCurve & line defs - as in https://stackoverflow.com/a/27664883/11156131
//works for the following
/*var p1 = {x:125,y:200};
var p2 = {x:250,y:225};
var p3 = {x:275,y:100};
var a1 = {x:30,y:125};
var a2 = {x:300,y:175};*/

// current svg  points
//does not work for following
var p1 = { x: 200, y: 300 };
var p2 = { x: 640, y: 175 };
var p3 = { x: 1080, y: 300 };
var a1 = { x: 640, y: 50 };
var a2 = { x: 640, y: 550 };


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);

// Display the intersection points
var textPoints = 'Intersections: ';
for (var i = 0; i < points.length; i++) {
  var p = points[i];
  textPoints += ' [' + parseInt(p.x) + ',' + parseInt(p.y) + ']';
}
console.log(textPoints);
console.log(points);

function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x,
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2,
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];
    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;
      // Bounds checks
      if (a1.x == a2.x && y >= minY && y <= maxY) {
        // Vertical line
        intersections.push(point);
      } else if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
};
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1280 600" id="svg">
  <rect class="vBoxRect" width="1280" height="600" fill="#EFEFEF"></rect>
  <g id="controlPoint">
    <circle cx="640" cy="175" r="5" fill="green" fill-opacity=".5"></circle>    
  </g>
  <g id="qBez">
    <path d="M200,300Q640,175,1080,300" stroke="tomato" fill="none"></path>
  </g>
  <g id="limit">
    <circle id="upper" cx="640" cy="50" r="5" fill="red"></circle>
    <circle id="lower" cx="640" cy="550" r="5" fill="red"></circle>
    <text id="0" x="650" y="60">(640, 50)</text>
    <text id="1" x="650" y="560">(640, 550)</text>
  </g>
  <g id="vert">
    <line x1="640" y1="550" x2="640" y2="50" stroke="blue" stroke-dasharray="500,500"></line>
  </g>
</svg>

//with the same numbers from https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
var lerp = function(a, b, x) { return (a + x * (b - a)); };

// qCurve & line defs - as in https://stackoverflow.com/a/27664883/11156131
//works for the following
var p1 = {x:125,y:200};
var p2 = {x:250,y:225};
var p3 = {x:275,y:100};
var a1 = {x:30,y:125};
var a2 = {x:300,y:175};


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);

// Display the intersection points
var textPoints = 'Intersections: ';
for (var i = 0; i < points.length; i++) {
  var p = points[i];
  textPoints += ' [' + parseInt(p.x) + ',' + parseInt(p.y) + ']';
}
console.log(textPoints);
console.log(points);

function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x,
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2,
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];
    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;
      // Bounds checks
      if (a1.x == a2.x && y >= minY && y <= maxY) {
        // Vertical line
        intersections.push(point);
      } else if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
};

javascript svg geometry bezier
2个回答
0
投票

该函数工作正常，除非线是垂直的（

b
和
c
变为无穷大）。

一个简单的解决方法是给线条一个不可见的倾斜，如下所示：

  if (a1.x === a2.x && a1.y !== a2.y) {
    a1.x += 1e-8;
  }


var p1 = {
  x: 200,
  y: 300
};
var p2 = {
  x: 640,
  y: 175
};
var p3 = {
  x: 1080,
  y: 300
};

var a1 = {
  x: +vert.getAttribute('x1'),
  y: +vert.getAttribute('y1')
};
var a2 = {
  x: +vert.getAttribute('x2'),
  y: +vert.getAttribute('y2')
};

var a3 = {
  x: +hor.getAttribute('x1'),
  y: +hor.getAttribute('y1')
};
var a4 = {
  x: +hor.getAttribute('x2'),
  y: +hor.getAttribute('y2')
};


// Calculate the intersections
var points = calcQLintersects(p1, p2, p3, a1, a2);
var points2 = calcQLintersects(p1, p2, p3, a3, a4);

// Display the intersection points
renderIntersections(points, svg);
renderIntersections(points2, svg);



function calcQLintersects(p1, p2, p3, a1, a2) {
  var intersections = [];

  //add invisible slant to vertical lines
  if (a1.x === a2.x && a1.y !== a2.y) {
    a1.x += 1e-8;
  }

  // Inverse line normal
  var normal = {
    x: a1.y - a2.y,
    y: a2.x - a1.x
  };

  // Q-coefficients
  var c2 = {
    x: p1.x + p2.x * -2 + p3.x,
    y: p1.y + p2.y * -2 + p3.y
  };

  var c1 = {
    x: p1.x * -2 + p2.x * 2,
    y: p1.y * -2 + p2.y * 2
  };

  var c0 = {
    x: p1.x,
    y: p1.y
  };

  // Transform to line
  var coefficient = a1.x * a2.y - a2.x * a1.y;
  var a = normal.x * c2.x + normal.y * c2.y;
  var b = (normal.x * c1.x + normal.y * c1.y) / a;
  var c = (normal.x * c0.x + normal.y * c0.y + coefficient) / a;
  //console.log(normal, a, b, c)

  // Solve the roots
  var roots = [];
  d = b * b - 4 * c;
  if (d > 0) {
    var e = Math.sqrt(d);
    roots.push((-b + Math.sqrt(d)) / 2);
    roots.push((-b - Math.sqrt(d)) / 2);
  } else if (d == 0) {
    roots.push(-b / 2);
  }

  // Calculate the solution points
  for (var i = 0; i < roots.length; i++) {
    var minX = Math.min(a1.x, a2.x);
    var minY = Math.min(a1.y, a2.y);
    var maxX = Math.max(a1.x, a2.x);
    var maxY = Math.max(a1.y, a2.y);
    var t = roots[i];

    if (t >= 0 && t <= 1) {
      // Possible point -- pending bounds check
      var point = {
        x: lerp(lerp(p1.x, p2.x, t), lerp(p2.x, p3.x, t), t),
        y: lerp(lerp(p1.y, p2.y, t), lerp(p2.y, p3.y, t), t)
      };
      var x = point.x;
      var y = point.y;

      // Bounds checks
      if (a1.y == a2.y && x >= minX && x <= maxX) {
        // Horizontal line
        intersections.push(point);
      } else if (x >= minX && y >= minY && x <= maxX && y <= maxY) {
        // Line passed bounds check
        intersections.push(point);
      }
    }
  }
  return intersections;
}


//referred to https://stackoverflow.com/a/27664883/11156131
// linear interpolation utility
function lerp(a, b, x) {
  return a + x * (b - a);
};
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1280 600" id="svg">
  <rect class="vBoxRect" width="1280" height="600" fill="#EFEFEF"></rect>
    <path d="
             M 200 300
             Q 640 175 
             1080 300" stroke="tomato" fill="none"></path>

    <line id="vert" x1="640" y1="550" x2="640" y2="50" stroke="blue" />
    <line id="hor" x1="200" y1="280" x2="1200" y2="280" stroke="purple" />
</svg>

<script>
  function renderIntersections(points, target) {
    for (var i = 0; i < points.length; i++) {
      var pt = points[i];
      let circle = document.createElementNS(
        "http://www.w3.org/2000/svg",
        "circle"
      );
      circle.setAttribute("cx", pt.x);
      circle.setAttribute("cy", pt.y);
      circle.setAttribute("r", "5");
      svg.append(circle);
    }
  }
</script>

0
投票

您基本上要做的是在旋转/变换的坐标系中找到抛物线的根。例如。这两个图像是同一对直线和曲线，但一个很难使用，另一个超级简单：

第二个非常简单的原因是因为我们只需要使用二次公式求解标准高中二次方程 By(t) = liney。如果我们将线下移到 y=0，现在实际上只是求根。需要认识到的重要一点是，贝塞尔曲线在变换和旋转下是不变的，因此，如果我们找到旋转/平移直线和曲线对的 t 值，这些值与 

t
值相同为原始方向。
所以我们就这样做吧：





const { atan2, cos, sin, sqrt } = Math;

function getIntersections(points, line) {
  const [p1, p2, p3] = points ;
  const [l1, l2] = line;
  const [ox, oy] = l1;
  const angle = atan2(l2[1]-l1[1], l2[0]-l1[0]);
  
  // transform our coordinates as per above:
  points.forEach(p => {
    let [x, y] = p;
    p[0] = (x-ox) * cos(-angle) - (y-oy) * sin(-angle);
    p[1] = (x-ox) * sin(-angle) + (y-oy) * cos(-angle);
  });
  
  // and now essentially done, we can "trivially" find our roots:
  const [y1, y2, y3] = [p1[1], p2[1], p3[1]];
  // set up the quadratic formula values:
  const a = y1 - 2*y2 + y3;
  const b = 2 * (y2 - y1);
  const c = y1;
  // then just... evaluate the formula:
  const u = -b/(2*a);
  const v = b**2 - 4*a*c;
  // 1: if there are no roots, there are no roots. Done.
  if (v < 0) return [];
  // 2: if there's only one root, return that:
  if (v === 0) return [u];
  // And 3: two roots because of the +/- in the quadratic formula:
  const w = sqrt(v)/(2*a);
  return [u + w, u - w];
}

// Let's test the coordinates from the above image:
const [[x1,y1],[x2,y2],[x3,y3]] = points = [[207,74], [70,133], [188,229]];
const line = [[209, 33], [75,245]];

const roots = getIntersections(points, line);
console.log(`roots: ${roots.join(`, `)}`);

const getCoordinate = t => {
  const mt = 1-t;
  return [
    x1*mt**2 + 2*x2*t*mt + x3*t**2,
    y1*mt**2 + 2*y2*t*mt + y3*t**2,
  ];
};

const coordinates = roots.map(t => getCoordinate(t).map(v => v.toFixed(2)));
console.log(`coordinates: ${coordinates.join(`, `)}`);





    





      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.