Coverage for pygeodesy/simplify.py : 91%

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 B{C{indices}}=C{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{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 B{C{indices}}=C{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}
@newfield example: Example, Examples '''
# try: # from collections import namedtuple # _T2 = namedtuple('_T2', 'ix, h2') # except ImportError: # class _T2(object): # ... # namedtuple not used because (a) values can not # be updated and (b) it produces PyChecker warning # "<string>:28: self is not first method argument" # which can not be suppressed by option --stdlib '''(INTERNAL) VW 2-tuple (index, area). '''
'''(INTERNAL) Simplify state. '''
indices, **options): '''New C{Simplify} state. '''
raise ValueError('%s too small: %.6e' % ('radius', radius))
# tolerance converted to degrees squared raise ValueError('%s too small: %.6e' % ('tolerance', tolerance))
# 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. ''' _, _, _, s, _ = self.d2yxse eps, d2yxu = self.eps, self.d2yxu t2, t = self.s2, 0 # tallest for i in range(n, m): d2, _, _, _ = d2yxu(s, i) if d2 > t2: t2, t = d2, i if brk and d2 > eps: break return t2, t
'''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.
@param modified: Use modified RDP (C{bool}). '''
else: # points[] to point [s] d2, i = d2ih(s+1, e, modified) 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 if isNumpy2(pts): raise AttributeError('%r invalid' % (attr,)) m = radians(1.0) * self.radius r[0].h2 = r[-1].h2 = 0 # zap sentinels for t2 in r: # convert back to meter setattr(pts[t2.ix], attr, sqrt(t2.h2) * m)
# double check for duplicates
'''Basic simplification of a path of C{LatLon} points.
Eliminates any points closer together than the given distance tolerance.
@param points: Path points (C{LatLon}[]). @param distance: Tolerance (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{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.
@param points: Path points (C{LatLon}[]). @param distance: Tolerance (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword shortest: Optional, shortest or perpendicular distance (C{bool}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{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).
@param points: Path points (C{LatLon}[]). @param distance: Tolerance (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword shortest: Optional, shortest or perpendicular distance (C{bool}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{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.
@param points: Path points (C{LatLon}[]). @param pipe: Half pipe width (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword shortest: Optional, shortest or perpendicular distance (C{bool}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{equirectangular_}.
@return: Simplified points (C{LatLon}[]).
@raise LimitError: Lat- and/or longitudinal delta exceeds the B{C{limit}}, see function L{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 (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.
@param points: Path points (C{LatLon}[]). @param area: Tolerance (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword attr: Optional, points attribute save area value (C{str}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{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{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 (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).
@param points: Path points (C{LatLon}[]). @param area: Tolerance (C{meter}, same units as B{C{radius}}). @keyword radius: Optional, mean earth radius (C{meter}). @keyword attr: Optional attribute to save the area value (C{str}). @keyword indices: Optionally return the simplified point indices instead of the simplified points (C{bool}). @keyword options: Optional keyword arguments passed thru to function L{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{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-2020 -- 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. |