Для кривой Безье я адаптировал алгоритм от Максима Шеманарева (см. https://web.archive.org/web/20190307062751/http: //antigrain.com: 80 / research / adaptive_bezier / ), который включает в себя установление допуска, с помощью которого можно рекурсивно разбить кривую на линейные сегменты. Используя допуск, более плоские части кривой Безье дают очень мало сегментов линии, а при резких изгибах кривой Безье количество сегментов линии увеличивается для правильного отображения кривой.
Алгоритм Максима Шеманарева использовал расстояние между конечными точками (P1 и P4) и контрольными точками Безье (P2 & P3) в качестве средства определения, был ли подразделенный сегмент достаточно в пределах допуска, или нужна ли кривая дальнейшее подразделение.
Я обнаружил, однако, что его алгоритм был излишне сложным, учитывая граничные случаи, когда кривая Безье содержала очень резкую кривую. Моя адаптация, чтобы упростить его алгоритм, включает проверку допуска для расстояния между линией, образованной конечными точками (P1 и P4) с вычисленной средней точкой (P1234). При добавлении этой проверки допуска любой острый изгиб, который все еще существует между конечными точками, вызовет дальнейшее подразделение на меньшие отрезки линии ...
Реализация javascript выглядит следующим образом ...
<!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 ) {
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 ) < bezierTolerance &&
distanceToSegmentSqr( p1, p4, p3 ) < bezierTolerance &&
distanceToSegmentSqr( p1, p4, p1234 ) < bezierTolerance )
{
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( 20, { x:135, y: 45 }, { x: 165, y: 45 }, { x: 160, y: 110 }, { x:190, y:110 }, false, true, true );
draw( 0.1, { 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, то сегмент является достаточно линейным, и, следовательно, дальнейшее подразделение не происходит.
Для сравнения, верхняя кривая справа использует bezierTolerance = 20. Опять же, любое подразделение Безье, в котором расстояния от отрезка линии, образованного P1 и P4, до каждой из точек P2, P3 и P1234, все меньше, чем sqrt (20) (~ 4.47), будут квалифицироваться как «достаточно прямые», и быть добавлен как линейный сегмент к результатам.
В качестве крайнего примера, кривая внизу включает очень резкий изгиб. Установив bezierTolerance = 0.1, вы заметите, что алгоритм изящно обрабатывает резкий изгиб, добавляя дополнительные подразделения для лучшего представления кривой ...
Короче говоря, высокий допуск даст меньше отрезков и меньше, чем оптимальная кривая Безье при рисовании, а низкий допуск даст больше отрезков и лучшую кривую Безье. Но слишком малый допуск приведет к результату с ненужным количеством отрезков, поэтому необходимо провести эксперименты, чтобы установить sh правильное bezierTolerance ...