Coverage for pygeodesy/simplify.py : 99%

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 I{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 I{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 I{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 specify of the distance between a point and a path edge. If C{True}, use the I{shortest} distance to the path edge or edge points, otherwise use the I{perpendicular} distance to the extended line through both path edge points.
Keyword argument B{C{radius}} of all fuctions is set to the mean earth radius in C{meter}. Other units can be used, 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://www.ScienceDirect.com/science/article/pii/S0098300402000092} - 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
# from pygeodesy.basics import len2 # from .fmath # from pygeodesy.lazily import _ALL_LAZY # from .units
# 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. '''
elif self.radius < self.eps: 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] to -[e] exceeding the tolerance. ''' break
'''Find the tallest I{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 I{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 I{squared}, points[i] to -[j] deltas and the (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]
'''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. '''
'''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 I{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: If C{True} 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): '''I{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 I{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: If C{True} use the I{shortest} otherwise the I{perpendicular} distance (C{bool}). @kwarg indices: If C{True} 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 I{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 I{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: If C{True} use the I{shortest} otherwise the I{perpendicular} distance (C{bool}). @kwarg indices: If C{True} 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): '''I{Reumann-Witkam} (RW) simplification of a path of C{LatLon} points.
Eliminates any points too close together or within the given I{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: If C{True} use the I{shortest} otherwise the I{perpendicular} distance (C{bool}). @kwarg indices: If C{True} 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): '''I{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 I{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: If C{True} 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): '''I{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: If C{True} 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-2023 -- 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. |