Uploaded image for project: 'Spatial Information Systems'
  1. Spatial Information Systems
  2. SIS-455

Compute length of cubic Bézier curve

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Won't Fix
    • Affects Version/s: None
    • Fix Version/s: 1.0
    • Component/s: Geometry, Referencing
    • Labels:
      None

      Description

      We need a way to estimate the length of a cubic Bézier curve from its starting point at t=0 to an arbitrary t value where t[0…1]. Conversely, we need to estimate the t parameter for a given length since the starting point. There is no exact solution for this problem, but we may estimate the length using Legendre-Gauss approach documented in A Primer on Bézier Curves page. The accuracy is determined by the number Gaussian Quadrature Weights and Abscissae used. For example with 3 terms:

      w₁ = 0.8888888888888888; a₁ = 0;
      w₂ = 0.5555555555555556; a₂ = -0.7745966692414834;
      w₃ = 0.5555555555555556; a₃ = +0.7745966692414834;
      length(t) ≈ t/2 * (w₁*f(a₁*t/2 - t/2) + w₂*f(a₂*t/2 - t/2) + w₃*f(a₃*t/2 - t/2))
      

      with f(t) defined as hypot(x′(t), y′(t)) and with x′(t) and y′(t) the first derivatives of Bézier equations for x(t) and y(t).

      Once we have the length for a given t value, we can try to find the converse by using an iterative approach as described in the Moving Along a Curve with Specified Speed paper from geometric tools.

      Once we are able to estimate the t parameters for a given length, we should delete the Bezier.isValid(x, y) method (and consequently remove its use and the TransformException in the curve method). Instead, given the geodesic distance from Bézier start point to ¼ of the distance from start point to end point, estimate the t parameter at that position. It should be a value close but not identical to t≈¼. We can then compute the (x, y) coordinates of the point on that curve at that t parameter value and compare with the expected coordinates. It should (hopefully) be a point closer to expected than the point computed at exactly t=¼, thus removing the need for the Bezier.isValid(x,y) hack.

      Alternatively, all the above is a complicated way to say that we want the shortest distance between a point on the geodesic path and a point on the curve which is known to be at position close to (but not exactly at) t≈¼ and t≈¾.

        Attachments

          Activity

            People

            • Assignee:
              desruisseaux Martin Desruisseaux
              Reporter:
              desruisseaux Martin Desruisseaux
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: