Faster algorithm for the length of a polyline(-segment)

QCAD Professional QCAD Suggestions and Feedback
1

Andrew,

Please consider a faster algorithm for the length of a polyline(-segment), example code in this forum topic.

It is totally not required to explode a polyline to its individual segments first.
And discard all these shapes afterwards.

The required data can be extracted directly from the vertex data as explained.
Chord length and sweep angle for bulging segments is readily available.
The segment length is then nothing more than:

  • =A * sin(B) / B

OR

  • =A when it is straight.

Tested the algorithm on a large sample size of various polylines at hand without a hick-up
Results are systematically the same apart form the last or the last few floating point digits.

With such an accuracy error, it is impossible to determine which of the routes is more accurate.
In the end it is a running sum and that suffers from accuracy loss in floating point.

Except with 3D data … But then QCAD can not render a 3D polyline with bulging segments correctly in the first place.
And it will not save such data.
For that we have to agree that a bulging segment … a so-called ‘Arc’ in top view with 3D data is part of a Helix (G2/G3).
With a pitch of zero, it is again a flat, arc-shaped segment. :wink:

Regards,
CVH

2

Andrew,

Thanks for implementing a variant of the faster algorithm. (commit)

Still:

 Given that:
    bulge = tan(sweep)/4  => sweep = 4 * atan(bulge)  (1)
    radius = chord / 2 * sin(sweep / 2)               (2)
    length = radius * sweep                           (3) 
Plugging (2) into (3) we get:
    length =  chord / 2 * sin(sweep / 2) * sweep 
Rearranged: 
    length =  chord * sin(sweep/2) * sweep/2

Defining halfSweep = 2 * atan(bulge) ... We can eliminate all the divisions:
    length =  chord * sin(halfSweep) * halfSweep

As mentioned in the above:
Straight: length = A = chord
Curved: length = A * sin(B) * B = chord * sin(halfSweep) * halfSweep

Further …
In the considerations listed in the forum topic:

  • RPolyline::getSegmentAt(i) restricts the creation of an Arc on sweep not over 2Pi-RS.PointTolerance.
    From inverse calculation that is the same as |bulge| not equal or over 4.0e9


  • RPolyline::getSegmentAt also considers a segment to be straight for a |bulge| less than 1.0e-6 with RPolyline::isStraight(bulges.at(i)).

This means that current lines 1584 - 1586:

        if (qAbs(b) < 1e-9) {
            // straight line segment
            totalLength += dist;

Should read:

        if (qAbs(b) < 1e-6 || qAbs(b) >= 4.0e9) {
            // straight line segment
            totalLength += dist;

Otherwise you apply different conditions for creating a segment shape at index i than for its direct length calculation.
I did my homework, the AI probably not. :wink:


There was no limitation that the chord became nearly zero or less than 1e-12.
And this is no critical condition, both type of segment would be nearly zero long.

Current line 1577 - 1580 are obsolete.

Note that in current line 1569 it calculates the remainder of a division by the number of vertices each iteration.
Probably fast but even that can be left out by doubling the code for a last closing segment.
Somewhat longer code but also N times a fraction faster. :wink:


Regards,
CVH