贝塞尔曲线到点的垂线
Perpendicular line from bezier curve to point
问题
我需要获得三次 (2d) 贝塞尔曲线的 点 Q B(t) 其中从点 Q 到另一个给定点 P 与垂直 相交贝塞尔曲线。
- 我知道：P，B(t)
- 我寻找：Q（基本上我想要 g 的斜率，但当我知道 Q，但是g的斜率就够了）
到目前为止我做了什么（你可以跳过这个）
Note that I think this ansatz is wrong. This is only included for completeness.
我试图用我的（基础）数学知识来解决这个问题，但我无法完成。这是我现在的（请不要对符号太严格，我不太擅长这个）：
以下公式将表示为 y(x) 以获得一个结果，这必须针对 y(x) 进行计算和 x(y)。点P是控制点，Q是线g(x)从Q到P垂直于贝塞尔曲线B(t)=( x, y)T。 g(x) 行的表达式可以通过
检索
其中B(x)是笛卡尔坐标下的贝塞尔曲线，B'(x)是导数（在笛卡尔坐标下） k 是与 y 轴的交点。要获得 g(x) 的斜率，必须求解
要计算 B(x) 必须解决 B(t) t 然后将其插回 B(t)。所以在贝塞尔曲线上的每个点都有关系
这也适用于导数 B'(t).
B(t)的导数是（根据wikipedia）
对 t (with wolfram alpha) 求解这个结果
其中 a0 = (P1 - P0)x,a1 = (P2 - P1)x 和 a2 = (P 3 - P2)x.将 *ti*s 插回 B(t) 结果 (wolfram alpha for t1, wolfram alpha for t2, wolfram alpha for t3)
现在接下来的事情是使用 y = B'(x) 和第二个方程并消除 x 但我有不知道怎么做，我什至不知道这是否可能。
您已经知道贝塞尔曲线的导数 - 它描述曲线的切线。该切线应垂直于 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
现在打开括号并得到 5-th 度方程 t.
这样的多项式方程没有封闭形式的解，所以你需要某种数值root-finding algorithm（使用那些用于多项式根的）
我找到了 mbostock on Github who implemented the idea from this online book which was acutally created by @Mike'Pomax'Kamermans 关于贝塞尔曲线的问题的近似实现。如果您必须处理贝塞尔曲线，请检查一下。这解释了我在使用贝塞尔曲线时遇到的大部分问题。
算法思路如下：
- 粗略估计：
- 计算Q大约，i通过在 B[ 中插入不同的 tis =129=](t) (mbostock 使用 t1 = 0, t2 = 1/8, t3 = 2/8, ...).
- 计算Qapprox,之间的二次（省去一个平方根计算）距离i 和 P.
- 保存Q大约，i 和 ti 最接近（距离最小）.
- 做一个更精确的近似：
- 选择精度q.
- 计算t前 = ti - q.
- 检查Q之间的距离是否近似，之前 = B(tbefore) and P小于Qapprox,i和P，如果是则设置Q 大约，i = Q approx，before并从2开始（精确近似），如果没有则继续。
- 计算t后 = ti + q.
- 检查Q之间的距离是否近似，after = B(tafter) 和P小于Qapprox,i和P，如果是则设置Q 大约，i = Q 在之后从2开始（精确近似），如果没有则继续。
- Q大约，i是最近的。如果精度足够好就停在这里。如果不降低精度 q（mbostock 除以二）并从 2 重新开始（精确近似）。
As already mentioned there is the implementation of mbostock on Github. I
paste the code here in case the link goes down. THIS IS NOT MY OWN CODE.
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>
问题
我需要获得三次 (2d) 贝塞尔曲线的 点 Q B(t) 其中从点 Q 到另一个给定点 P 与垂直 相交贝塞尔曲线。
- 我知道：P，B(t)
- 我寻找：Q（基本上我想要 g 的斜率，但当我知道 Q，但是g的斜率就够了）
到目前为止我做了什么（你可以跳过这个）
Note that I think this ansatz is wrong. This is only included for completeness.
我试图用我的（基础）数学知识来解决这个问题，但我无法完成。这是我现在的（请不要对符号太严格，我不太擅长这个）：
以下公式将表示为 y(x) 以获得一个结果，这必须针对 y(x) 进行计算和 x(y)。点P是控制点，Q是线g(x)从Q到P垂直于贝塞尔曲线B(t)=( x, y)T。 g(x) 行的表达式可以通过
检索其中B(x)是笛卡尔坐标下的贝塞尔曲线，B'(x)是导数（在笛卡尔坐标下） k 是与 y 轴的交点。要获得 g(x) 的斜率，必须求解
要计算 B(x) 必须解决 B(t) t 然后将其插回 B(t)。所以在贝塞尔曲线上的每个点都有关系
这也适用于导数 B'(t).
B(t)的导数是（根据wikipedia）
对 t (with wolfram alpha) 求解这个结果
其中 a0 = (P1 - P0)x,a1 = (P2 - P1)x 和 a2 = (P 3 - P2)x.将 *ti*s 插回 B(t) 结果 (wolfram alpha for t1, wolfram alpha for t2, wolfram alpha for t3)
现在接下来的事情是使用 y = B'(x) 和第二个方程并消除 x 但我有不知道怎么做，我什至不知道这是否可能。
您已经知道贝塞尔曲线的导数 - 它描述曲线的切线。该切线应垂直于 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
现在打开括号并得到 5-th 度方程 t.
这样的多项式方程没有封闭形式的解，所以你需要某种数值root-finding algorithm（使用那些用于多项式根的）
我找到了 mbostock on Github who implemented the idea from this online book which was acutally created by @Mike'Pomax'Kamermans 关于贝塞尔曲线的问题的近似实现。如果您必须处理贝塞尔曲线，请检查一下。这解释了我在使用贝塞尔曲线时遇到的大部分问题。
算法思路如下：
- 粗略估计：
- 计算Q大约，i通过在 B[ 中插入不同的 tis =129=](t) (mbostock 使用 t1 = 0, t2 = 1/8, t3 = 2/8, ...).
- 计算Qapprox,之间的二次（省去一个平方根计算）距离i 和 P.
- 保存Q大约，i 和 ti 最接近（距离最小）.
- 做一个更精确的近似：
- 选择精度q.
- 计算t前 = ti - q.
- 检查Q之间的距离是否近似，之前 = B(tbefore) and P小于Qapprox,i和P，如果是则设置Q 大约，i = Q approx，before并从2开始（精确近似），如果没有则继续。
- 计算t后 = ti + q.
- 检查Q之间的距离是否近似，after = B(tafter) 和P小于Qapprox,i和P，如果是则设置Q 大约，i = Q 在之后从2开始（精确近似），如果没有则继续。
- Q大约，i是最近的。如果精度足够好就停在这里。如果不降低精度 q（mbostock 除以二）并从 2 重新开始（精确近似）。
As already mentioned there is the implementation of mbostock on Github. I paste the code here in case the link goes down. THIS IS NOT MY OWN CODE.
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>