在两组像素坐标(x，y)之间生成路径 [英] Generating a path between two sets of pixel coordinates (x, y)
问题描述
我有两组xy坐标，即开始和结束.起点是我想要离开的地方，终点是目的地.
I have two sets of xy coordinates, start and end. The start is where I'd like to move from, and the end is the destination.
目标是在两个坐标之间生成一个xy对象数组，可以对这些对象进行迭代，以生成到目标的平滑，非跳跃的路径，如下所示.
The goal is to produce an array of xy objects between the two coordinates that can be iterated over to produce a smooth, non-jumpy path to the destination, as shown below.
我已经阅读了Bezier曲线，但是我正在努力实现可视化，并想知道是否有更简单的方法来解决上述问题?
I've done reading around Bezier curves, but I'm struggling to visualise the implementation and wanted to know if there's an easier way to solve the above?
推荐答案
对于贝塞尔曲线，我改编了Maxim Shemanarev的算法(请参阅 https://web.archive.org/web/20190307062751/http://antigrain.com:80/research/adaptive_bezier/)，这涉及建立公差，通过该公差将曲线递归分解为线性段.通过使用公差，贝塞尔曲线的较平坦部分产生的线段很少，对于贝塞尔曲线的急剧弯曲，线段的数量增加，以便正确地描绘曲线.
For a bezier curve, I have adapted an algorithm from Maxim Shemanarev (see https://web.archive.org/web/20190307062751/http://antigrain.com:80/research/adaptive_bezier/ ) which involves establishing a tolerance by which to recursively break down the curve into linear segments. By using a tolerance, the flatter parts of the bezier curve produce very few line segments, and for sharp bends of a bezier curve, the number of line segments increases in order to properly depict the curve.
Maxim Shemanarev算法使用端点(P1& P4)与贝塞尔曲线控制点(P2& P3)之间的距离作为确定细分部分是否在公差范围内或是否需要进一步弯曲的手段.细分.
Maxim Shemanarev's algorithm used the distance between the end points (P1 & P4) and the bezier control points (P2 & P3) as a means of determining whether the subdivided segment was sufficiently within tolerance, or whether the curve needed further subdividing.
但是，我发现，当考虑到贝塞尔曲线包含非常尖锐的曲线的边缘情况时，他的算法不必要地复杂.为了简化他的算法，我的修改包括对由端点(P1和P4)形成的线与计算出的中点(P1234)之间的距离进行公差检查.通过添加此公差检查，端点之间仍然存在的任何急剧弯曲都会触发进一步细分为更小的线段...
I found, though, that his algorithm was unnecessarily complex when taking into account edge cases where the bezier included a very sharp curve. My adaptation, to simplify his algorithm, includes the tolerance check for the distance between the line formed by the end points (P1 & P4) with the calculated midpoint (P1234). By adding this tolerance check, any sharp bend that still exists between the end points will trigger a further subdivision into smaller line segments...
javascript实现如下...
The javascript implementation is as follows...
<!DOCTYPE html>
<html><body>
<canvas id="myCanvas" width="300" height="300" style="border:1px solid #d3d3d3;"></canvas>
<script>
var canvas = document.getElementById("myCanvas");
function distanceSqr(v, w) {
return (v.x - w.x) ** 2 + (v.y - w.y) ** 2;
};
function distanceToSegmentSqr(v, w, p) {
var vwLength = distanceSqr(v, w);
if (vwLength === 0) return distanceSqr(p, v);
var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / vwLength;
t = Math.max(0, Math.min(1, t));
return distanceSqr(p, { x: v.x + t * (w.x - v.x), y: v.y + t * (w.y - v.y) });
};
function lineateBezier( bezierTolerance, p1, p2, p3, p4 ) {
let tolerance = bezierTolerance * bezierTolerance;
var result = [ p1 ];
function recurse( p1, p2, p3, p4 ) {
var p12 = { x: (p1.x + p2.x) / 2, y: (p1.y + p2.y) / 2 };
var p23 = { x: (p2.x + p3.x) / 2, y: (p2.y + p3.y) / 2 };
var p34 = { x: (p3.x + p4.x) / 2, y: (p3.y + p4.y) / 2 };
var p123 = { x: (p12.x + p23.x) / 2, y: (p12.y + p23.y) / 2 };
var p234 = { x: (p23.x + p34.x) / 2, y: (p23.y + p34.y) / 2 };
var p1234 = { x: (p123.x + p234.x) / 2, y: (p123.y + p234.y) / 2 };
if( distanceToSegmentSqr( p1, p4, p2 ) < tolerance &&
distanceToSegmentSqr( p1, p4, p3 ) < tolerance &&
distanceToSegmentSqr( p1, p4, p1234 ) < tolerance )
{
result.push( p1234 );
} else {
recurse( p1, p12, p123, p1234 );
recurse( p1234, p234, p34, p4 );
}
};
recurse (p1, p2 || p1, p3 || p4, p4);
result.push( p4 );
return result;
};
function draw( bezierTolerance, startEndPoint, startControlPoint, endControlPoint, endPoint, clearCanvasFlag, pointsFlag, controlFlag ) {
// Get line segment points
let lineSegments = lineateBezier( bezierTolerance, startEndPoint, startControlPoint, endControlPoint, endPoint );
// Clear canvas
var ctx = canvas.getContext("2d");
if ( clearCanvasFlag ) {
ctx.clearRect( 0, 0, canvas.width, canvas.height );
}
// Draw line segments
ctx.beginPath();
ctx.moveTo( lineSegments[ 0 ].x, lineSegments[ 0 ].y );
for ( let i = 1; i < lineSegments.length; i++ ) {
ctx.lineTo( lineSegments[ i ].x, lineSegments[ i ].y );
}
ctx.strokeStyle = '#000000';
ctx.stroke();
// Draw points
if ( pointsFlag ) {
for ( let i = 0; i < lineSegments.length; i++ ) {
ctx.beginPath();
ctx.arc( lineSegments[ i ].x, lineSegments[ i ].y, 1.5, 0, 2 * Math.PI );
ctx.strokeStyle = '#ff0000';
ctx.stroke();
}
}
// Draw control points...
if ( controlFlag ) {
ctx.beginPath();
ctx.moveTo( startEndPoint.x, startEndPoint.y );
ctx.lineTo( startControlPoint.x, startControlPoint.y );
ctx.strokeStyle = '#0000ff';
ctx.stroke();
ctx.beginPath();
ctx.moveTo( endPoint.x, endPoint.y );
ctx.lineTo( endControlPoint.x, endControlPoint.y );
ctx.stroke();
}
}
draw( 1, { x:35, y: 45 }, { x: 65, y: 45 }, { x: 60, y: 110 }, { x:90, y:110 }, true, true, true );
draw( 5, { x:135, y: 45 }, { x: 165, y: 45 }, { x: 160, y: 110 }, { x:190, y:110 }, false, true, true );
draw( 0.25, { x:20, y: 200 }, { x: 250, y: 290 }, { x: 250, y: 160 }, { x:20, y:250 }, false, true, true );
</script>
</body></html>
请注意关键变量bezierTolerance.在运行上面的示例时，左侧的顶部曲线使用bezierTolerance = 1，这意味着只要端点(P1和P4)相对于P2，P3和P1234的距离小于1，则该段已充分弯曲"，因此不再进行细分.
Please note the critical variable bezierTolerance. In running the example above, the top curve on the left uses a bezierTolerance = 1, which means that as long as the distance between the end points (P1 & P4) relative to P2, P3, and P1234 is less than 1, then the segment is sufficiently "curved", and therefore no further subdividing occurs.
作为比较，右边的顶部曲线使用bezierTolerance = 5.再次，从P1和P4形成的线段到点P2，P3和P1234中的每一个的距离均小于5的任何贝塞尔细分都将被视为足够的弯曲"，并被添加为线细分为结果.
As a comparison, the top curve on the right uses a bezierTolerance = 5. Again, any bezier subdivision in which the distances from the line segment formed by P1 and P4 to each of the points P2, P3, and P1234, are all less than 5 will qualify as sufficiently "curved", and be added as a line segment to the results.
作为一个极端示例，底部的曲线包括非常尖锐的弯曲.通过设置bezierTolerance = 0.25，您会注意到该算法通过包含更多细分来更好地表示曲线，从而优雅地处理了急剧弯曲...
As an extreme example, the curve on the bottom includes a very sharp bend. By setting bezierTolerance = 0.25, you will note that the algorithm handles the sharp bend gracefully by including additional subdivisions to better represent the curve...
简而言之，绘制时，高公差将产生较少的线段和最佳贝塞尔曲线，而低公差将产生更多的线段和更好的贝塞尔曲线.但是，公差方法太小会产生不必要的线段数，因此需要做一些实验才能建立一个平衡良好的bezierTolerance ...
In short, a high tolerance will produce less line segments and a less than optimal bezier curve when drawn, and a low tolerance will produce more line segments and a better looking bezier curve. But, a tolerance way too small will produce a result with an unnecessary number of line segments, so some experimentation is required to establish a well balanced bezierTolerance...
这篇关于在两组像素坐标(x，y)之间生成路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
