1

问题

我需要得到三次（2d）贝塞尔曲线B（t）的点Q ，其中从点Q到另一个给定点P的线与贝塞尔曲线垂直相交。

  • 我知道：P , B(t)
  • 我寻找：Q（基本上我想要g的斜率，但是当我知道Q时我可以很容易地计算出来，但是g的斜率就足够了）

到目前为止我所做的（你可以跳过这个）

请注意，我认为这个 ansatz 是错误的。这只是为了完整性。

我试图用我的（基本）数学知识来解决这个问题，但我无法完成它。这就是我现在所拥有的（请不要对符号太严格，我在这方面不是很好）：

以下公式将表示为y(x)以获得一个结果，这必须为y(x) 和 x(y)计算。点P是控制点，Q是从Q到P的线g(x)与贝塞尔曲线B (t) = (x, y) T垂直的点。可以通过以下方式检索g(x)行的表达式

其中B(x)是笛卡尔坐标中的贝塞尔曲线，B'(x)是导数（笛卡尔坐标中），k是与 y 轴的交点。要获得g(x)的斜率，必须解决

要计算B(x) ，必须为t求解B (t)，然后将其插回B(t)。所以在贝塞尔曲线上的每个点都有关系

这也适用于导数B '(t)。

B (t)的导数是（根据维基百科）

为 t 解决这个问题（使用 wolfram alpha）导致

其中a 0 = ( P 1 - P 0 ) x，a 1 = ( P 2 - P 1 ) x和a 2 = ( P 3 - P 2 ) x。将 *t i *s 插回B (t)会导致 ( wolfram alpha for t 1 , wolfram alpha for t 2 , wolfram alpha for t 3 )

现在接下来的事情是使用y = B'(x)和第二个方程并消除x但我不知道如何，我什至不知道这是否可能。

4

2 回答 2

3

您已经知道贝塞尔曲线的导数 - 它描述了曲线的切线。该切线应垂直于QP矢量。所以此时你需要写向量PQ和切向量的两个分量T

PQx = (1-t)^3 * P0.x + 3*t*(1-t)^2*P1.x  ... - P.x
PQy = (1-t)^3 * P0.y + ... - P.y
Tx = 3*(1-t)^2 * (P1.x - P0.x).... and so on
Ty = ....

并为向量 T 和 QP 的点积建立方程（垂直向量的点积为零）：

 PQx * Tx + PQy * Ty = 0

现在打开括号并得到unknown的5 次t方程。

这种多项式方程没有封闭形式的解，因此您需要某种数值求根算法（使用那些用于多项式根的算法）

于 2020-01-09T13:26:51.237 回答
0

我在 Github 上找到了 mbostock 对我的问题提出的近似值的实现，他实现了这本由@Mike'Pomax'Kamermans 创作的关于贝塞尔曲线的在线书籍中的想法。如果您必须处理贝塞尔曲线，请检查一下。这解释了我在使用贝塞尔曲线时遇到的大部分问题。

该算法的思想如下：

  1. 做一个粗略的近似：
    1. 通过在B ( t ) 中插入不同的t i s计算Q approx, i (mbostock 使用t 1 = 0, t 2 = 1/8, t 3 = 2/8, ...)。
    2. 计算Q approx, i和P之间的二次（节省一个平方根计算）距离。
    3. 保存Q近似值、i和最接近（距离最短）的t i 。
  2. 做一个更精确的近似：
    1. 选择一个精度q。
    2. 计算t before = t i - q。
    3. 检查Q approx, before = B ( t before ) 和P之间的距离是否小于Q approx, i和P之间的距离，如果是，则设置Q approx, i = Q approx, before并从 2 开始（精确近似)，如果没有继续。
    4. 在= t i + q之后计算t。
    5. 检查Q approx, after = B ( t after ) 和P之间的距离是否小于Q approx, i和P之间的距离，如果是，则设置Q approx, i = Q after并从 2 开始（精确近似），如果没有继续。
    6. Q大约，i是最接近的。如果精度足够好，请在此处停止。如果不降低精度q（mbostock 除以 2）并从 2 重新开始（精确近似）。

如前所述，在 Github 上有 mbostock的实现。我在此处粘贴代码以防链接断开。这不是我自己的代码。

var points = [[474,276],[586,393],[378,388],[338,323],[341,138],[547,252],[589,148],[346,227],[365,108],[562,62]];
var width = 960,
    height = 500;
var line = d3.svg.line()
    .interpolate("cardinal");
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
var path = svg.append("path")
    .datum(points)
    .attr("d", line);
var line = svg.append("line");
var circle = svg.append("circle")
    .attr("cx", -10)
    .attr("cy", -10)
    .attr("r", 3.5);
svg.append("rect")
    .attr("width", width)
    .attr("height", height)
    .on("mousemove", mousemoved);
// adding coordinates display
var coords = svg.append("text");
function mousemoved() {
  var m = d3.mouse(this),
      p = closestPoint(path.node(), m);
  line.attr("x1", p[0]).attr("y1", p[1]).attr("x2", m[0]).attr("y2", m[1]);
  circle.attr("cx", p[0]).attr("cy", p[1]);
  coords.attr("x", (p[0] + m[0]) / 2).attr("y", (p[1] + m[1]) / 2).html("Q(" + Math.round(p[0]) + ", " + Math.round(p[1]) + ")");
}
function closestPoint(pathNode, point) {
  var pathLength = 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 = [best.x, best.y];
  best.distance = Math.sqrt(bestDistance);
  return best;
  function distance2(p) {
    var dx = p.x - point[0],
        dy = p.y - point[1];
    return dx * dx + dy * dy;
  }
}
.disclaimer{
  padding: 10px;
  border-left: 3px solid #ffcc00;
  background: #fffddd;
}
path {
  fill: none;
  stroke: #000;
  stroke-width: 1.5px;
}
line {
  fill: none;
  stroke: red;
  stroke-width: 1.5px;
}
circle {
  fill: red;
}
rect {
  fill: none;
  cursor: crosshair;
  pointer-events: all;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
<div class="disclaimer">
  This is not my own code. This is made by <a href="https://gist.github.com/mbostock/8027637">mbostock on Github</a> based on Mike Kamermans <a href="https://pomax.github.io/bezierinfo/#projections">Primer on Bézier Curves online book</a>.
</div>

于 2020-01-13T10:49:19.333 回答