SmoothLine library

Sourceforge Project Page

Contents

• Introduction
• Functions description
• Examples
• Method
• Download
• Dependencies, Compilation, Linking
• License
• History

Introduction

Additionally, some functions to calculate several curve or polyline parameters (length, max. angle, angle sum, twist and writhe) as well as some functions to solve systems of linear equations are provided.

Functions description

For the representation of coordinate vectors, the Tiny Vector Matrix library using Expression Templates (tvmet) is used. In the following, the definitions

typedef Vector<fltyp,dim>  Vect;
typedef list<Vect>         l_Vect;

were used.

libSmoothLine provides four smoothing functions:

smooth_connect

This function generates a polyline that hits the original points. r is used for input (original points) and for output (smoothed polyline points). The smoothing procedure is iterated until all angles α_i between two consecutive line segments s_i and s_i+1 are ≤ MaxAng (in radians) and all areas |s_i| ⋅ |s_i+1| ⋅ sin(α_i) are ≤ MaxArea. The procedure also stops after MaxSteps iterations. If closeIt is true, the polyline will be closed, otherwise it starts/ends at the first/last point of the original point list. Consecutive points in the input list may not be identical. For closed lines, the first point may not be repeated at the end of the list! The calculation cost is proportional to the number of final points.

Return values:

•  0 :   No errors, nothing special.
•  1 = HasTurningPoint:   There is at least one turning point in the polyline (α_i = 2 π) which could not be smoothed. However, all other edges of the polyline are smoothed. This is no error.
• -1 = TooFewPoints:   The original point list must contain at least three points, otherwise this error code is returned.
• -2 = IdenticalPoints:   At least two consecutive points in the input list are identical. After that error, the point list r may be partially modified.

smooth_polyline

This function generates a polyline that has approximately the same line length as the polyline given by the original points. The length of the polyline is typically reduced by less than 1% but in extreme cases, it might be reduced by more than 10%. The parameters and return values are as described above.

smooth_polyline_el

This function generates a polyline that has exactly the same line length as the polyline given by the original points. All parameters and return values are as described above, the additional parameter enhance is used to activate a calculation-intensive procedure (including numerical root-finding) that enhances the quality of the smoothed polyline in some extreme cases.

Disadvantages compared to smooth_polyline:

• Slightly (enhance=false) or notably (enhance=true) higher calculation cost.
• The result is not invariant under point order reversion.
• In some cases, the result is less straight, i.e. it has wider arcs.

smooth_polyline_g

This function also generates a polyline that has exactly the same line length as the polyline given by the original points. As with smooth_polyline, the result is invariant under point order reversion. The parameters and return values are as described above, but an additional error code may be returned:

• -3 = MultiRootFail:   A GSL multiroot function returned an error.

• Very high calculation cost proportional to N³ and memory consumption proportional to N² where N is the number of final points. Thus it is not applicable to large polylines.

calc_maxAngle_Len

This function calculates the maximum angle MxAng between consecutive line segments (in radians, turning points are omitted) and the length Len of the polyline r, which may optionally be closed. Return values:

•  0 :   No errors, nothing special.
•  1 = HasTurningPoint:   There is at least one turning point in the polyline (α_i = 2 π). This is no error.
• -1 = TooFewPoints:   The point list must contain at least three points, otherwise this error code is returned.
• -2 = IdenticalPoints:   At least two consecutive points in the input list are identical.

calc_maxAng_sum_Ang_Len

This function calculates the maximum angle MxAng between consecutive line segments (in radians, turning points are omitted), the sum of these angles SumAng (including turning points) and the length Len of the polyline r, which may optionally be closed. The return values are as described above. If an error is returned (return value < 0), the values of MxAng, SumAng and Len are trashy.

calc_Len

This function returns the length of the polyline r, which may optionally be closed.

calc_Twist_Writhe

This function calculates the twist tw and the writhe wr of the polyline r (dim=3 only), which may optionally be closed (see here, method 2a, for a description of the calculation method). Return values:

•  0 :   No errors.
• -1 = TooFewPoints:   The point list must contain at least three points, otherwise this error code is returned.
• -2 = IdenticalPoints:   At least two consecutive points in the input list are identical.
• -4 = ErrTurningPoint:   There is at least one turning point in the polyline (α_i = 2 π), twist and writhe cannot be calculated.
• -5 = MethodFail:   The calculation method failed.

calc_Twist

This function calculates the twist tw of the polyline r (dim=3 only), which may optionally be closed. The return values are as described above but -5 = MethodFail cannot occur. If an error is returned, the value of tw is trashy.

Functions to solve systems of linear equations

Examples

Code example

Smoothing examples

When closeIt=true, a regular polygon is always transformed into a circle. In such a special case, the line length is also exactly preserved by smooth_polyline, i.e. the results of smooth_polyline, smooth_polyline_el and smooth_polyline_g are identical. See the results for a regular triangle with closeIt=true and closeIt=false:

Last but not least an extreme example, a stair. With closeIt=false, nothing strange happens, but it's suitable for showing the non-invariance of smooth_polyline_el under point order reversion. With closeIt=true, smooth_polyline_el without enhancement produces a surprising bend. Here, the result of smooth_polyline_el with enhance=true is much better while smooth_polyline_g clearly produces the best result.

Method

In smooth_connect, the base sides of the isosceles triangles (i.e. the provisional new segments) are positioned such that they hit the points r_i and r_i+1. In smooth_polyline, smooth_polyline_el and smooth_polyline_g, they are positioned such that its lengths are equal to half the length of the old segment s_i. Generally, the end points of adjacent provisional segments s'_j do not coincide, i.e. the segments are not connected. (In the case of smooth_connect, every other connection is okay.)

In smooth_connect and in smooth_polyline, the final new segments were determined by taking the center points c_j of each two end points of the s'_j which have to be connected as the corners r'_j of the new polyline. In smooth_connect_el, a new corner point is determined by rotating the provisional segments s'_j-1 and s'_j around their outer end points such that the inner endpoints hit each other. In three dimensions, the resulting triangle is then rotated around its baseline in order to minimize the distance between its upper tip (the junction point) and the center point c_j.

If enhancement is activated, the lengths of the two sides of that triangle (i.e. the two segments) are varied to minimize the distance between its upper tip and the center point c_j while keeping the sum of these lengths as well as the triangle's baseline constant. This operation requires (one dimensional) numerical root-finding.

In smooth_connect_g, a global optimization procedure is applied. The positions of all new corner points are varied simultaneously to minimize the sum of the squared distances between the corner points and the corresponding center points c_j while forcing the total length of the new polyline to the length of the original one. This operation requires multidimensional numerical root-finding, i.e. the numerical solution of a system of nonlinear equations.

So far the basic principles. If you are interested in the details, please look into the code!

Download

Dependencies, Compilation, Linking

Compilation is tested with g++ (GCC) 4.7.1.

Example:
g++ -g -O2 -Wl,--gc-sections -o test_smooth test_smooth.cpp smoothline.cpp -lgsl -lcblas -lblas

License

This library is free software; you can redistribute and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

History