Algorithm for a Bezier Curve approximation on a Cartesian Grid

Question

Given any bezier curve, I would like to find a set of lines such that:

a) the lines are all connected in series

b) the start point and end point of the series of lines are the start point and end point of the bezier curve

c) the start and end point of each line can only be placed on intersection points of a cartesian grid. ie. Integer values only like (1, 1) or (2,2). No decimals like (1.5, 2.5) or (5, 3.3)

d) the resulting lines are the best fit for the curve. This may mean that the area between the lines and the curve is minimized, but I am open to other metrics for "best fit."

Note) All the control points for the bezier curve must also be on the grid, though I am unsure if that will affect the solution.

For example, the red lines in the following image are the best fit for the curve given the requirement that endpoints must be on the grid:

So far, I've been able to think of a brute-force algorithm, but I'm looking to improve on that. A brute-force algorithm is possible because the on-grid restriction makes the search-space discrete:

let optimalSequence = []
let optimalSequenceArea = Infinity
let points = Collection of all points in the vicinity of the curve
for (let numberOfPoints = 1; numberOfPoints < floor(length of the curve); numberOfPoints++) {

  let firstControlPoint = first control point on the bezier curve
  let lastControlPoint = last control point on the bezier curve

  func recursivelyFindOptimalSequence(sequence) {
    if (length(sequence) == numberOfPoints - 1) {
      let totalArea = total area between the lines of the sequence and the curve
      if (totalArea < optimalSequenceArea) {
        optimalSequenceArea = totalArea
        optimalSequence = sequence
        return;
      }
    }
    for (let point in points) {
      recursivelyFindOptimalSequence([ ...sequence, point ])
    }
  }

  recursivelyFindOptimalSequence([ firstControlPoint ]);
}
return optimalSequence

But, again this algorithm is terribly inefficient, especially for large curves. Can anyone think of a more efficient algorithm?

Answer 1

I’d suggest that you generate polyline vertices that lie on the curve, and then move each vertex to the nearest grid point.

Generating an initial polyline that’s a good approximation of the curve can be done in several ways. The choice depends on your criteria for speed, accuracy, and minimization of the number of points.

I don’t claim that my suggestion will generate a polyline that’s optimal, in some sense, but you haven’t given us any criteria for optimality, anyway.