Return a subsequence of vertex indices such that the polyline connecting
these vertices is never further than "tolerance" from the original
polyline. Provided the first and last vertices are distinct, they are
always preserved; if they are not, the subsequence may contain only a
single index.
Some useful properties of the algorithm:
- It runs in linear time.
- The output is always a valid polyline. In particular, adjacent
output vertices are never identical or antipodal.
- The method is not optimal, but it tends to produce 2-3% fewer
vertices than the Douglas-Peucker algorithm with the same tolerance.
- The output is *parametrically* equivalent to the original polyline to
within the given tolerance. For example, if a polyline backtracks on
itself and then proceeds onwards, the backtracking will be preserved
(to within the given tolerance). This is different than the
Douglas-Peucker algorithm, which only guarantees geometric equivalence.
See also S2PolylineSimplifier, which uses the same algorithm but is more
efficient and supports more features, and also S2Builder, which can
simplify polylines and polygons, supports snapping (e.g. to E7 lat/lng
coordinates or S2CellId centers), and can split polylines at intersection
points.
Return a subsequence of vertex indices such that the polyline connecting these vertices is never further than "tolerance" from the original polyline. Provided the first and last vertices are distinct, they are always preserved; if they are not, the subsequence may contain only a single index.
Some useful properties of the algorithm:
- It runs in linear time.
- The output is always a valid polyline. In particular, adjacent output vertices are never identical or antipodal.
- The method is not optimal, but it tends to produce 2-3% fewer vertices than the Douglas-Peucker algorithm with the same tolerance.
- The output is *parametrically* equivalent to the original polyline to within the given tolerance. For example, if a polyline backtracks on itself and then proceeds onwards, the backtracking will be preserved (to within the given tolerance). This is different than the Douglas-Peucker algorithm, which only guarantees geometric equivalence.
See also S2PolylineSimplifier, which uses the same algorithm but is more efficient and supports more features, and also S2Builder, which can simplify polylines and polygons, supports snapping (e.g. to E7 lat/lng coordinates or S2CellId centers), and can split polylines at intersection points.