sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Desruisseaux (JIRA)" <>
Subject [jira] [Resolved] (SIS-455) Compute length of cubic Bézier curve
Date Sat, 25 May 2019 12:59:00 GMT


Martin Desruisseaux resolved SIS-455.
       Resolution: Won't Fix
         Assignee: Martin Desruisseaux
    Fix Version/s: 1.0

Not needed anymore at least in the form documented in this issue. We use iteration instead
for finding the nearest point using Newton method. This work only with the assumption that
the initial point is close enough to the point we are looking for and that straight lines
are reasonably good approximation in that vicinity. Those assumptions may be wrong, but for
the need of this algorithm this is okay since in case of doubt, the point will be considered
too far and the curve will be separated in two smaller curves for finer examination.

> Compute length of cubic Bézier curve
> ------------------------------------
>                 Key: SIS-455
>                 URL:
>             Project: Spatial Information Systems
>          Issue Type: Improvement
>          Components: Geometry, Referencing
>    Affects Versions: 1.0
>            Reporter: Martin Desruisseaux
>            Assignee: Martin Desruisseaux
>            Priority: Major
>             Fix For: 1.0
> 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:
> {noformat}
> 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))
> {noformat}
> 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_≈¾.

This message was sent by Atlassian JIRA

View raw message