Find rightmost/leftmost point of SVG path

Question

How to find leftmost/rightmost point of SVG C (bezier curve) path segment? I know there is getBoundingClientRect() and getBBox() but none of them apply since they return only single coordinate of the point.

Just to avoid XY problem - I want to split single path composed of bezier curves into several paths each monotonously going from left to right (or right to left). It means that on any single path should be no 2 points having equal X coordinate. I understand that required split point may potentially be inside the bounding box of a segment thus not being leftmost/rightmost, but I'm almost sure that way of finding such point should use same techniques as finding horizontally extreme point.

What do you mean `getBBpox(0` returns a "single point"? `getBBox()` returns the bounding box of the path. The leftmost point should be `bbox.x` and the rightmost should be `bbox.x + bbox.width`. Is that what you wanted? — Paul LeBeau, Nov 29 '16 at 12:33
`getBBox` can let me know `x` coordinate of the target point, but not `y`. This is what I mean when say only single coordinate. — Vasily Liaskovsky, Nov 29 '16 at 21:51

score 1 · Answer 1 · answered Nov 29 '16 at 13:07

You would need to iterate through the path length with .getPointAtLength(i) method, and then find the limits. Seemed like a fun thing to do so I made a quick and dirty implementation, this is the important part:

function findLimits(path) {

  var boundingPoints = {
    minX: {x: dimensions.width, y: dimensions.height},
    minY: {x: dimensions.width, y: dimensions.height},
    maxX: {x: 0, y: 0},
    maxY: {x: 0, y: 0}
  }
  var l = path.getTotalLength();
  for (var p = 0; p < l; p++) {
    var coords = path.getPointAtLength(p);
    if (coords.x < boundingPoints.minX.x) boundingPoints.minX = coords;
    if (coords.y < boundingPoints.minY.y) boundingPoints.minY = coords;
    if (coords.x > boundingPoints.maxX.x) boundingPoints.maxX = coords;
    if (coords.y > boundingPoints.maxY.y) boundingPoints.maxY = coords;
  }
  return boundingPoints
}

You can find the implementation here: https://jsfiddle.net/4gus3hks/1/

This has linear O(length) performance. Is there any way to do it faster, or maybe some routine out-of-the-box? — Vasily Liaskovsky, Nov 29 '16 at 21:49
See this question for a mathematical solution instead of an iterative one. http://stackoverflow.com/questions/24809978/calculating-the-bounding-box-of-cubic-bezier-curve — Paul LeBeau, Nov 30 '16 at 02:24

score 0 · Accepted Answer · answered Dec 03 '16 at 01:26

Paul LeBeau's comment and fancy animation on the wiki inspired me for the solution. It is based mostly on following terms:

Values of parameter t from [0, 1] can be matched to the curve points.
For any parameter value point on the curve can be constructed step-by-step by linearly combining pairs of adjacent control points into intermediate control points of higher "depth". This operation can be repeated until only single point left - point on the curve itself.
Coordinates of the intermediate points can be defined by t-polynoms of degree equal to point "depth". And coefficients of those polynoms ultimately depend only on coordinates of initial control points.
Penultimate step of construction gives 2 points that define tangent to the curve at the final point, and coordinates of those points are controlled by quadratic polynom.
Having direction of tangent in question as vector allows to construct quadratic equation against t where curve has required tangent.

So, in fact, finding required points can be performed in constant O(1) time:

  tangentPoints: function(tx, ty){
    var ends = this.getPolynoms(2);
    var tangent = [ends[1][0].subtractPoly(ends[0][0]),
                   ends[1][1].subtractPoly(ends[0][1])];
    var eq = tangent[0].multiplyScalar(ty).subtractPoly(tangent[1].multiplyScalar(tx));
    return solveQuadratic(...eq.values).filter(t => t >= 0 && t <= 1);
  }

Full code with assisting Polynom class and visual demo I placed into this repo and fiddle

Find rightmost/leftmost point of SVG path

2 Answers2

Linked