Package pygeodesy :: Module simplify
[frames] | no frames]

Module simplify

Six functions to simplify or linearize a path of LatLon points.

Each of the simplify functions is based on a different algorithm and produces different simplified results in (very) different run times for the same path of LatLon points.

Function simplify1 eliminates points based on edge lengths shorter than a given tolerance.

The functions simplifyRDP and 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 simplifyRDP exhaustively searches the most distant point in each iteration, while modified simplifyRDPm stops at the first point exceeding the distance tolerance.

Function simplifyRW use the Reumann-Witkam method, sliding a "pipe" over each path edge, removing all subsequent points closer than the pipe radius up to the first point outside the pipe.

Functions simplifyVW and simplifyVWm are based on the original, respectively modified Visvalingam-Whyatt (VW) method using the area of the triangle formed by three neigboring points. Function simplifyVW removes only a single point per iteration, while modified simplifyVWm eliminates all points with a triangular area not exceeding the tolerance in each iteration.

Functions simplifyRDP, simplifyRDPm and simplifyRW provide keyword argument shortest to select the computation of the distance between a point and a path edge. If True, use the shortest distance to the path edge or path end points, False use the perpendicular distance to the extended path edge line.

For all functions, keyword argument adjust scales the longitudinal distance between two points by the cosine of the mean of the latitudes.

Likewise, keyword argument 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.

Finally, use keyword argument indices=True in any function to return a list of simplified point indices instead of the simplified points. The first and last index are always the first and last points index.

To process NumPy arrays containing rows of lat-, longitude and possibly other values, use class Numpy2LatLon to wrap the NumPy array into on-the-fly-LatLon points. Pass the Numpy2LatLon instance to any simplify function and the returned result will be a NumPy array containing the simplified subset, a partial copy of the original NumPy array. Use keyword argument indices=True to return a list of array row indices inlieu of the simplified array subset.

See:

Tested with 64-bit Python 2.6.9 (and numpy 1.6.2), 2.7.13 and 2.7.14 (both with numpy 1.13.1), 3.5.3 and 3.6.2 on macOS 10.12.6 Sierra, with 64-bit Intel-Python 3.5.3 (and numpy 1.11.3) on macOS 10.12.6 Sierra and with Pythonista 3.1 using 64-bit Python 2.7.12 and 3.5.1 (both with numpy 1.8.0) on iOS 10.3.3.


Version: 17.11.26

Functions
 
simplify1(points, distance, radius=6371008.77141, adjust=True, indices=False)
Basic simplification of a path of LatLon points.
 
simplifyRDP(points, distance, radius=6371008.77141, adjust=True, shortest=False, indices=False)
Ramer-Douglas-Peucker (RDP) simplification of a path of LatLon points.
 
simplifyRDPm(points, distance, radius=6371008.77141, adjust=True, shortest=False, indices=False)
Modified Ramer-Douglas-Peucker (RDP) simplification of a path of LatLon points.
 
simplifyRW(points, pipe, radius=6371008.77141, adjust=True, shortest=False, indices=False)
Reumann-Witkam simplification of a path of LatLon points.
 
simplify2(points, pipe, radius=6371008.77141, adjust=True, shortest=False, indices=False)
Reumann-Witkam simplification of a path of LatLon points.
 
simplifyVW(points, area, radius=6371008.77141, adjust=True, attr=None, indices=False)
Visvalingam-Whyatt (VW) simplification of a path of LatLon points.
 
simplifyVWm(points, area, radius=6371008.77141, adjust=True, attr=None, indices=False)
Modified Visvalingam-Whyatt (VW) simplification of a path of LatLon points.
Function Details

simplify1(points, distance, radius=6371008.77141, adjust=True, indices=False)

 

Basic simplification of a path of LatLon points.

Eliminates any points closer together than the given distance tolerance.

Parameters:
  • points - Path points (LatLons).
  • distance - Tolerance (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • ValueError - Radius or distance tolerance too small.

simplifyRDP(points, distance, radius=6371008.77141, adjust=True, shortest=False, indices=False)

 

Ramer-Douglas-Peucker (RDP) simplification of a path of LatLon points.

Eliminates any points too close together or closer to an edge than the given distance tolerance.

This RDP method exhaustively searches for the point with the largest distance, resulting in worst-case complexity O(n**2) where n is the number of points.

Parameters:
  • points - Path points (LatLons).
  • distance - Tolerance (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • shortest - Optional, shortest or perpendicular distance (bool).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • ValueError - Radius or distance tolerance too small.

simplifyRDPm(points, distance, radius=6371008.77141, adjust=True, shortest=False, indices=False)

 

Modified Ramer-Douglas-Peucker (RDP) simplification of a path of LatLon points.

Eliminates any points too close together or closer to an edge than the given distance tolerance.

This RDP method stops at the first point farther than the given distance tolerance, significantly reducing the run time (but producing results different from the original RDP method).

Parameters:
  • points - Path points (LatLons).
  • distance - Tolerance (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • shortest - Optional, shortest or perpendicular distance (bool).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • ValueError - Radius or distance tolerance too small.

simplifyRW(points, pipe, radius=6371008.77141, adjust=True, shortest=False, indices=False)

 

Reumann-Witkam simplification of a path of LatLon points.

Eliminates any points too close together or within the given pipe tolerance along an edge.

Parameters:
  • points - Path points (LatLons).
  • pipe - Half pipe width (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • shortest - Optional, shortest or perpendicular distance (bool).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • ValueError - Radius or pipe tolerance too small.

simplify2(points, pipe, radius=6371008.77141, adjust=True, shortest=False, indices=False)

 

Reumann-Witkam simplification of a path of LatLon points.

Eliminates any points too close together or within the given pipe tolerance along an edge.

Parameters:
  • points - Path points (LatLons).
  • pipe - Half pipe width (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • shortest - Optional, shortest or perpendicular distance (bool).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • ValueError - Radius or pipe tolerance too small.

simplifyVW(points, area, radius=6371008.77141, adjust=True, attr=None, indices=False)

 

Visvalingam-Whyatt (VW) simplification of a path of LatLon points.

Eliminates any points too close together or with a triangular area not exceeding the given area tolerance (squared).

This VW method exhaustively searches for the single point with the smallest triangular area, resulting in worst-case complexity O(n**2) where n is the number of points.

Parameters:
  • points - Path points (LatLons).
  • area - Tolerance (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • attr - Optional, points attribute save area value (string).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • AttributeError - If attr is specified for Numpy2 points.
  • ValueError - Radius or area tolerance too small.

simplifyVWm(points, area, radius=6371008.77141, adjust=True, attr=None, indices=False)

 

Modified Visvalingam-Whyatt (VW) simplification of a path of LatLon points.

Eliminates any points too close together or with a triangular area not exceeding the given area tolerance (squared).

This VW method removes all points with a triangular area below the tolerance per iteration, significantly reducing the run time (but producing results different from the original VW method).

Parameters:
  • points - Path points (LatLons).
  • area - Tolerance (meter, same units as radius).
  • radius - Optional, mean earth radius (meter).
  • adjust - Optionally adjust longitudes (bool).
  • attr - Optional attribute to save the area value (string).
  • indices - Optionally return the simplified point indices instead of the simplified points (bool).
Returns:
Simplified points (list of LatLons).
Raises:
  • AttributeError - If attr is specified for Numpy2 points.
  • ValueError - Radius or area tolerance too small.