Provides various simplification algorithms for n-dimensional simple polylines. More...
#include <psimpl.h>
Classes | |
| class | DPHelper |
| Douglas-Peucker approximation helper class. More... | |
Public Member Functions | |
| OutputIterator | ComputePositionalErrors2 (InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, OutputIterator result, bool *valid=0) |
| Computes the squared positional error between a polyline and its simplification. More... | |
| math::Statistics | ComputePositionalErrorStatistics (InputIterator original_first, InputIterator original_last, InputIterator simplified_first, InputIterator simplified_last, bool *valid=0) |
| Computes statistics for the positional errors between a polyline and its simplification. More... | |
| OutputIterator | DouglasPeucker (InputIterator first, InputIterator last, value_type tol, OutputIterator result) |
| Performs Douglas-Peucker approximation (DP). More... | |
| OutputIterator | DouglasPeuckerN (InputIterator first, InputIterator last, unsigned count, OutputIterator result) |
| Performs a Douglas-Peucker approximation variant (DPn). More... | |
| OutputIterator | Lang (InputIterator first, InputIterator last, value_type tol, unsigned look_ahead, OutputIterator result) |
| Performs Lang approximation (LA). More... | |
| OutputIterator | NthPoint (InputIterator first, InputIterator last, unsigned n, OutputIterator result) |
| Performs the nth point routine (NP). More... | |
| OutputIterator | Opheim (InputIterator first, InputIterator last, value_type min_tol, value_type max_tol, OutputIterator result) |
| Performs Opheim approximation (OP). More... | |
| OutputIterator | PerpendicularDistance (InputIterator first, InputIterator last, value_type tol, unsigned repeat, OutputIterator result) |
| Repeatedly performs the perpendicular distance routine (PD). More... | |
| OutputIterator | PerpendicularDistance (InputIterator first, InputIterator last, value_type tol, OutputIterator result) |
| Performs the perpendicular distance routine (PD). More... | |
| OutputIterator | RadialDistance (InputIterator first, InputIterator last, value_type tol, OutputIterator result) |
| Performs the (radial) distance between points routine (RD). More... | |
| OutputIterator | ReumannWitkam (InputIterator first, InputIterator last, value_type tol, OutputIterator result) |
| Performs Reumann-Witkam approximation (RW). More... | |
Private Types | |
| typedef std::iterator_traits< InputIterator >::difference_type | diff_type |
| typedef std::iterator_traits< const value_type * >::difference_type | ptr_diff_type |
| typedef std::iterator_traits< InputIterator >::value_type | value_type |
Private Member Functions | |
| void | Advance (InputIterator &it, diff_type n=1) |
| Increments the iterator by n points. More... | |
| InputIterator | AdvanceCopy (InputIterator it, diff_type n=1) |
| Increments a copy of the iterator by n points. More... | |
| void | Backward (InputIterator &it, unsigned &remaining) |
| Decrements the iterator by 1 point. More... | |
| void | CopyKey (InputIterator key, OutputIterator &result) |
| Copies the key to the output destination. More... | |
| void | CopyKeyAdvance (InputIterator &key, OutputIterator &result) |
| Copies the key to the output destination, and increments the iterator. More... | |
| unsigned | Forward (InputIterator &it, unsigned n, unsigned &remaining) |
| Increments the iterator by n points if possible. More... | |
Detailed Description
template<unsigned DIM, class InputIterator, class OutputIterator>
class psimpl::PolylineSimplification< DIM, InputIterator, OutputIterator >
Provides various simplification algorithms for n-dimensional simple polylines.
A polyline is simple when it is non-closed and non-selfintersecting. All algorithms operate on input iterators and output iterators. Note that unisgned integer types are NOT supported.
Member Typedef Documentation
◆ diff_type
|
private |
◆ ptr_diff_type
|
private |
◆ value_type
|
private |
Member Function Documentation
◆ Advance()
|
inlineprivate |
Increments the iterator by n points.
- See also
- AdvanceCopy
- Parameters
-
[in,out] it iterator to be advanced [in] n number of points to advance
◆ AdvanceCopy()
|
inlineprivate |
◆ Backward()
|
inlineprivate |
◆ ComputePositionalErrors2()
|
inline |
Computes the squared positional error between a polyline and its simplification.
For each point in the range [original_first, original_last) the squared distance to the simplification [simplified_first, simplified_last) is calculated. Each positional error is copied to the output range [result, result + count), where count is the number of points in the original polyline. The return value is the end of the output range: result + count.
Note that both the original and simplified polyline must be defined using the same value_type.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain a minimum of 2 vertices 6- The range [simplified_first, simplified_last) represents a simplification of the range [original_first, original_last), meaning each point in the simplification has the exact same coordinates as some point from the original polyline
In case these requirements are not met, the valid flag is set to false OR compile errors may occur.
- Parameters
-
[in] original_first the first coordinate of the first polyline point [in] original_last one beyond the last coordinate of the last polyline point [in] simplified_first the first coordinate of the first simplified polyline point [in] simplified_last one beyond the last coordinate of the last simplified polyline point [in] result destination of the squared positional errors [out] valid [optional] indicates if the computed positional errors are valid
- Returns
- one beyond the last computed positional error
◆ ComputePositionalErrorStatistics()
|
inline |
Computes statistics for the positional errors between a polyline and its simplification.
Various statistics (mean, max, sum, std) are calculated for the positional errors between the range [original_first, original_last) and its simplification the range [simplified_first, simplified_last).
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to double 4- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The ranges [original_first, original_last) and [simplified_first, simplified_last) contain a minimum of 2 vertices 6- The range [simplified_first, simplified_last) represents a simplification of the range [original_first, original_last), meaning each point in the simplification has the exact same coordinates as some point from the original polyline
In case these requirements are not met, the valid flag is set to false OR compile errors may occur.
- See also
- ComputePositionalErrors2
- Parameters
-
[in] original_first the first coordinate of the first polyline point [in] original_last one beyond the last coordinate of the last polyline point [in] simplified_first the first coordinate of the first simplified polyline point [in] simplified_last one beyond the last coordinate of the last simplified polyline point [out] valid [optional] indicates if the computed statistics are valid
- Returns
- the computed statistics
◆ CopyKey()
|
inlineprivate |
Copies the key to the output destination.
- See also
- CopyKeyAdvance
- Parameters
-
[in] key the first coordinate of the key [in,out] result destination of the copied key
◆ CopyKeyAdvance()
|
inlineprivate |
◆ DouglasPeucker()
|
inline |
Performs Douglas-Peucker approximation (DP).
The DP algorithm uses the RadialDistance (RD) routine O(n) as a preprocessing step. After RD the algorithm is O (n m) in worst case and O(n log m) on average, where m < n (m is the number of points after RD).
The DP algorithm starts with a simplification that is the single edge joining the first and last vertices of the polyline. The distance of the remaining vertices to that edge are computed. The vertex that is furthest away from theedge (called a key), and has a computed distance that is larger than a specified tolerance, will be added to the simplification. This process will recurse for each edge in the current simplification, untill all vertices of the original polyline are within tolerance.
Note that this algorithm will create a copy of the input polyline during the vertex reduction step.
RD followed by DP is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol perpendicular (point-to-segment) distance tolerance [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ DouglasPeuckerN()
|
inline |
Performs a Douglas-Peucker approximation variant (DPn).
This algorithm is a variation of the original implementation. Instead of considering one polyline segment at a time, all segments of the current simplified polyline are evaluated at each step. Only the vertex with the maximum distance from its edge is added to the simplification. This process will recurse untill the the simplification contains the desired amount of vertices.
The algorithm, which does not use the (radial) distance between points routine as a preprocessing step, is O(n2) in worst case and O(n log n) on average.
Note that this algorithm will create a copy of the input polyline for performance reasons.
DPn is applied to the range [first, last). The resulting simplified polyline consists of count vertices and is copied to the output range [result, result + count). The return value is the end of the output range: result + count.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains a minimum of count vertices 6- count is at least 2
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- See also
- DouglasPeucker
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] count the maximum number of points of the simplified polyline [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ Forward()
|
inlineprivate |
Increments the iterator by n points if possible.
If there are fewer than n point remaining the iterator will be incremented to the last point.
- See also
- Backward
- Parameters
-
[in,out] it iterator to be advanced [in] n number of points to advance [in,out] remaining number of points remaining after it
- Returns
- the actual amount of points that the iterator advanced
◆ Lang()
|
inline |
Performs Lang approximation (LA).
The LA routine defines a fixed size search-region. The first and last points of that search region form a segment. This segment is used to calculate the perpendicular distance to each intermediate point. If any calculated distance is larger than the specified tolerance, the search region will be shrunk by excluding its last point. This process will continue untill all calculated distances fall below the specified tolerance , or there are no more intermediate points. At this point all intermediate points are removed and a new search region is defined starting at the last point from old search region. Note that the size of the search region (look_ahead parameter) controls the maximum amount of simplification, e.g.: a size of 20 will always result in a simplification that contains at least 5% of the original points.
LA routine is applied to the range [first, last) using the specified tolerance and look ahead values. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a bidirectional iterator 3- The InputIterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0 7- look_ahead is not zero
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol perpendicular (point-to-segment) distance tolerance [in] look_ahead defines the size of the search region [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ NthPoint()
|
inline |
Performs the nth point routine (NP).
NP is an O(n) algorithm for polyline simplification. It keeps only the first, last and each nth point. As an example, consider any random line of 8 points. Using n = 3 will always yield a simplification consisting of points: 1, 4, 7, 8
NP is applied to the range [first, last). The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the OutputIterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- n is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] n specifies 'each nth point' [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ Opheim()
|
inline |
Performs Opheim approximation (OP).
The O(n) OP routine is very similar to the Reumann-Witkam (RW) routine, and can be seen as a constrained version of that RW routine. OP uses both a minimum and a maximum distance tolerance to constrain the search area. For each successive vertex vi, its radial distance to the current key vkey (initially v0) is calculated. The last point within the minimum distance tolerance is used to define a ray R (vkey, vi). If no such vi exists, the ray is defined as R(vkey, vkey+1). For each successive vertex vj beyond vi its perpendicular distance to the ray R is calculated. A new key is found at vj-1, when this distance exceeds the minimum tolerance Or when the radial distance between vj and the vkey exceeds the maximum tolerance. After a new key is found, the process repeats itself.
OP routine is applied to the range [first, last) using the specified distance tolerances min_tol and max_tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- min_tol is not 0 7- max_tol is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] min_tol radial and perpendicular (point-to-ray) distance tolerance [in] max_tol radial distance tolerance [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ PerpendicularDistance() [1/2]
|
inline |
Repeatedly performs the perpendicular distance routine (PD).
The algorithm stops after calling the PD routine 'repeat' times OR when the simplification does not improve. Note that this algorithm will need to store up to two intermediate simplification results.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol perpendicular (segment-to-point) distance tolerance [in] repeat the number of times to successively apply the PD routine [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ PerpendicularDistance() [2/2]
|
inline |
Performs the perpendicular distance routine (PD).
PD is an O(n) algorithm for polyline simplification. It computes the perpendicular distance of each point pi to the line segment S(pi-1, pi+1). Only when this distance is larger than the given tolerance will pi be part of the simpification. Note that the original polyline can only be reduced by a maximum of 50%. Multiple passes are required to achieve higher points reductions.
PD is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol perpendicular (segment-to-point) distance tolerance [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ RadialDistance()
|
inline |
Performs the (radial) distance between points routine (RD).
RD is a brute-force O(n) algorithm for polyline simplification. It reduces successive vertices that are clustered too closely to a single vertex, called a key. The resulting keys form the simplified polyline.
RD is applied to the range [first, last) using the specified tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains only vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol radial (point-to-point) distance tolerance [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
◆ ReumannWitkam()
|
inline |
Performs Reumann-Witkam approximation (RW).
The O(n) RW routine uses a point-to-line (perpendicular) distance tolerance. It defines a line through the first two vertices of the original polyline. For each successive vertex vi its perpendicular distance to this line is calculated. A new key is found at vi-1, when this distance exceeds the specified tolerance. The vertices vi and vi+1 are then used to define a new line, and the process repeats itself.
RW routine is applied to the range [first, last) using the specified perpendicular distance tolerance tol. The resulting simplified polyline is copied to the output range [result, result + m*DIM), where m is the number of vertices of the simplified polyline. The return value is the end of the output range: result + m*DIM.
Input (Type) Requirements: 1- DIM is not 0, where DIM represents the dimension of the polyline 2- The InputIterator type models the concept of a forward iterator 3- The input iterator value type is convertible to a value type of the output iterator 4- The range [first, last) contains vertex coordinates in multiples of DIM, f.e.: x, y, z, x, y, z, x, y, z when DIM = 3 5- The range [first, last) contains at least 2 vertices 6- tol is not 0
In case these requirements are not met, the entire input range [first, last) is copied to the output range [result, result + (last - first)) OR compile errors may occur.
- Parameters
-
[in] first the first coordinate of the first polyline point [in] last one beyond the last coordinate of the last polyline point [in] tol perpendicular (point-to-line) distance tolerance [in] result destination of the simplified polyline
- Returns
- one beyond the last coordinate of the simplified polyline
The documentation for this class was generated from the following file: