Coverage for pygeodesy/simplify.py : 98%

Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*-
Each of the I{simplify} functions is based on a different algorithm and produces different simplified results in (very) different run times for the same path of C{LatLon} points.
Function L{simplify1} eliminates points based on edge lengths shorter than a given tolerance.
The functions L{simplifyRDP} and L{simplifyRDPm} use the original, respectively modified Ramer-Douglas-Peucker (RDP) algorithm, iteratively finding the point farthest from each path edge. The difference is that function L{simplifyRDP} exhaustively searches the most distant point in each iteration, while modified L{simplifyRDPm} stops at the first point exceeding the distance tolerance.
Function L{simplifyRW} use the Reumann-Witkam method, sliding a "pipe" over each path edge, removing all subsequent points within, closer than the pipe radius up to the first point outside the pipe.
Functions L{simplifyVW} and L{simplifyVWm} are based on the original, respectively modified Visvalingam-Whyatt (VW) method using the area of the triangle formed by three neigboring points. Function L{simplifyVW} removes only a single point per iteration, while modified L{simplifyVWm} eliminates in each iteration all points with a triangular area not exceeding the tolerance.
Functions L{simplifyRDP}, L{simplifyRDPm} and L{simplifyRW} provide keyword argument I{shortest} to select the computation of the distance between a point and a path edge. If C{True}, use the shortest distance to the path edge or path end points, if C{False} use the perpendicular distance to the extended path edge line.
Keyword argument B{C{radius}} of all fuctions is set to the mean earth radius in meter. Other units can be choosen, provided that the radius and tolerance are always specified in the same units.
Use keyword argument C{B{indices}=True} in any function to return a list of simplified point I{indices} instead of the simplified points. The first and last index are always the first and last original index.
Finally, any additional keyword arguments B{C{options}} to all functions are passed thru to function L{pygeodesy.equirectangular_} to specify the distance approximation.
To process C{NumPy} arrays containing rows of lat-, longitude and possibly other values, use class L{Numpy2LatLon} to wrap the C{NumPy} array into I{on-the-fly-LatLon} points. Pass the L{Numpy2LatLon} instance to any I{simplify} function and the returned result will be a C{NumPy} array containing the simplified subset, a partial copy of the original C{NumPy} array. Use keyword argument C{B{indices}=True} to return a list of array row indices inlieu of the simplified array subset.
See: - U{https://Bost.Ocks.org/mike/simplify} - U{https://WikiPedia.org/wiki/Ramer-Douglas-Peucker_algorithm} - U{https://hydra.Hull.ac.UK/resources/hull:8338} - U{https://psimpl.SourceForge.net/reumann-witkam.html} - U{https://www.CS.UBC.CA/cgi-bin/tr/1992/TR-92-07.pdf} - U{https://GitHub.com/FlorianWilhelm/gps_data_with_python} - U{https://www.BDCC.co.UK/Gmaps/GDouglasPeuker.js} - U{https://GitHub.com/mourner/simplify-js} - U{https://GitHub.com/OmarEstrella/simplify.py} - U{https://PyPI.org/project/rdp} - U{https://PyPI.org/project/visvalingam} - U{https://PyPI.org/project/simplification} ''' # make sure int/int division yields float quotient, see .basics
# try: # from collections import namedtuple # _T2 = namedtuple('_T2', 'ix, h2') # except ImportError: # class _T2(object): # ... # namedtuple (and .named._NamedTuple) can not be # used because (a) values can not be updated and # (b) it produces PyChecker warning "<string>:28: # self is not first method argument" which can't # be suppressed with command line option --stdlib '''(INTERNAL) VW 2-tuple (index, area). ''' # __slots__ are no longer space savers, see # the comments at the class .points.LatLon_ # __slots__ = ('ix', 'h2')
'''(INTERNAL) Simplify state. '''
indices, **options): '''New C{Simplify} state. '''
raise _ValueError(radius=radius, txt=_too_(_small_))
# tolerance converted to degrees squared raise _ValueError(tolerance=tolerance, txt=_too_(_small_))
# compute either the shortest or perpendicular distance
'''Set path edge or line thru points[s] to -[e]. '''
'''Find the tallest distance among all points[n..m] to points[s] exceeding the tolerance. ''' break
'''Find the tallest perpendicular distance among all points[n..m] to the path edge or line thru points[s] to -[e] exceeding the tolerance. ''' # perpendicular distance squared
'''Find the tallest shortest distance among all points[n..m] to the path edge or line thru points[s] to -[e] exceeding the tolerance. ''' # point (x, y) on axis rotated by angle a ccw: # x' = y * sin(a) + x * cos(a) # y' = y * cos(a) - x * sin(a) # # distance (w) along and perpendicular (h) to # a line thru point (dx, dy) and the origin: # w = (y * dy + x * dx) / hypot(dx, dy) # h = (y * dx - x * dy) / hypot(dx, dy)
# distance points[i] to -[s] # perpendicular distance squared else: # distance points[i] to -[e]
'''Return distance squared, points[i] to -[j] deltas and longitudinal unrollment. ''' p2.lat, p2.lon, **self.options)
'''Compute the Visvalingam-Whyatt triangular area, points[i0] is the top and points[i1] to -[i2] form the base of the triangle. ''' # triangle height h = h2 / sqrt(d21) and # the area = h * sqrt(d21) / 2 == h2 / 2
'''Return the list of simplified points or indices. ''' else:
'''Ramer-Douglas-Peucker (RDP) simplification of a path of C{LatLon} points.
@arg modified: Use modified RDP (C{bool}). '''
else: # points[] to point [s] else:
'''Eliminate one Visvalingam-Whyatt point and recomputes the trangular area of both neighboring points, but removes those too unless the recomputed area exceeds the tolerance. '''
else:
'''Eliminate all Visvalingam-Whyatt points with a triangular area not exceeding the tolerance. '''
'''Initialize Visvalingam-Whyatt as list of 2-tuples _T2(ix, h2) where ix is the points[] index and h2 is the triangular area I{(times 2)} of that point. '''
elif n > 0: self.r = [_T2(i, s2e) for i in range(0, n)] # PYCHOK false else: self.r = []
'''Return the Visvalingam-Whyatt results, optionally including the triangular area (in meters) as attribute attr to each simplified point. '''
# double check the minimal triangular area
# the sqrt of double the triangular area) # converted back from degrees to meter raise _AttributeError(attr=attr)
# double check for duplicates
'''Basic simplification of a path of C{LatLon} points.
Eliminates any points closer together than the given distance tolerance.
@arg points: Path points (C{LatLon}[]). @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small. '''
indices=False, **options): '''Ramer-Douglas-Peucker (RDP) simplification of a path of C{LatLon} points.
Eliminates any points too close together or closer to an edge than the given distance tolerance.
This C{RDP} method exhaustively searches for the point with the largest distance, resulting in worst-case complexity M{O(n**2)} where M{n} is the number of points.
@arg points: Path points (C{LatLon}[]). @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg shortest: Optional, shortest or perpendicular distance (C{bool}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small. '''
indices=False, **options): '''Modified Ramer-Douglas-Peucker (RDPm) simplification of a path of C{LatLon} points.
Eliminates any points too close together or closer to an edge than the given distance tolerance.
This C{RDPm} method stops at the first point farther than the given distance tolerance, significantly reducing the run time (but producing results different from the original C{RDP} method).
@arg points: Path points (C{LatLon}[]). @kwarg distance: Tolerance (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg shortest: Optional, shortest or perpendicular distance (C{bool}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{distance}} or B{C{radius}} too small. '''
indices=False, **options): '''Reumann-Witkam (RW) simplification of a path of C{LatLon} points.
Eliminates any points too close together or within the given pipe tolerance along an edge.
@arg points: Path points (C{LatLon}[]). @kwarg pipe: Pipe radius, half-width (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg shortest: Optional, shortest or perpendicular distance (C{bool}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{pipe}} or B{C{radius}} too small. '''
else: else: # drop points[e]
indices=False, **options): '''Visvalingam-Whyatt (VW) simplification of a path of C{LatLon} points.
Eliminates any points too close together or with a triangular area not exceeding the given area tolerance I{squared}.
This C{VW} method exhaustively searches for the single point with the smallest triangular area, resulting in worst-case complexity M{O(n**2)} where M{n} is the number of points.
@arg points: Path points (C{LatLon}[]). @kwarg area: Tolerance (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg attr: Optional, points attribute to save the area value (C{str}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise AttributeError: If an B{C{attr}} is specified for I{Numpy2} B{C{points}}.
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small. '''
# remove any points too close or # with a zero triangular area
# keep removing the point with the smallest # area until latter exceeds the tolerance
indices=False, **options): '''Modified Visvalingam-Whyatt (VWm) simplification of a path of C{LatLon} points.
Eliminates any points too close together or with a triangular area not exceeding the given area tolerance I{squared}.
This C{VWm} method removes all points with a triangular area below the tolerance in each iteration, significantly reducing the run time (but producing results different from the original C{VW} method).
@arg points: Path points (C{LatLon}[]). @kwarg area: Tolerance (C{meter}, same units as B{C{radius}}). @kwarg radius: Mean earth radius (C{meter}). @kwarg attr: Optional, points attribute to save the area value (C{str}). @kwarg indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @kwarg options: Optional keyword arguments passed thru to function L{pygeodesy.equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise AttributeError: If an B{C{attr}} is specified for I{Numpy2} B{C{points}}.
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{pygeodesy.equirectangular_}.
@raise ValueError: Tolerance B{C{area}} or B{C{radius}} too small. '''
# remove all points with an area # not exceeding the tolerance
# **) MIT License # # Copyright (C) 2016-2022 -- mrJean1 at Gmail -- All Rights Reserved. # # Permission is hereby granted, free of charge, to any person obtaining a # copy of this software and associated documentation files (the "Software"), # to deal in the Software without restriction, including without limitation # the rights to use, copy, modify, merge, publish, distribute, sublicense, # and/or sell copies of the Software, and to permit persons to whom the # Software is furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included # in all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS # OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR # OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, # ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR # OTHER DEALINGS IN THE SOFTWARE. |