centerline-width 0.2.1

A Python package to find the centerline and width of rivers based on the latitude and longitude of the right and left bank

Centerline-Width

Find the centerline and width of rivers based on the latitude and longitude positionss from the right and left bank

• Convert raw data from Google Earth Pro to CSV
  • extractPointsToTextFile()
  • convertColumnsToCSV()
• Find centerline and width of river
  • plotCenterline()
  • plotCenterlineWidth()
  • riverWidthFromCenterline()
  • centerlineLatitudeLongtiude
  • centerlineLength
  • rightBankLength
  • leftBankLength

River Outlined in Google Earth Pro	Generated Centerline for the River Bank

Python implementation of R-Code CMGO (with modification)

NOTE: This is Beta quality software that is being actively developed, use at your own risk. This project is not supported or endorsed by either JPL or NASA. The code is provided “as is”, use at your own risk.

Requirements

Currently running on Python 3.7+

pip install -r requirements.txt

Requirements will also be downloaded as part of the pip download

Install

PyPi pip install at pypi.org/project/centerline-width/

pip install centerline-width

Quickstart: centerline-width

The core of centerline-width works with a .csv file of the left and right bank latitude/longitudes. Starting with Google Earth Pro, two .kml must first be translated to a single .csv file

import centerline_width
centerline_width.extractPointsToTextFile(left_kml="left_bank.kml",
					right_kml="right_bank.kml",
					text_output_name="river_coordinates_output.txt")
centerline_width.convertColumnsToCSV(text_file="river_coordinates_output.txt")

Then, to run the centerline-width functions, generate a river object from the river_coordinates_output.csv

river_object = centerline_width.riverCenterline(csv_data="river_coordinates_output.csv")

To plot the centerline, run the plotCenterline() function from river_object created

river_object.plotCenterline()

To plot the width of the river at intervals along the bank, run plotCenterlineWidth (apply_smoothing is optional and defaults to False, but is recommended)

river_object.plotCenterlineWidth(apply_smoothing=True)

Preprocessing

Convert KML files to Text File

Convert two .kml files from Google Earth Pro (for the left and right bank) and export the coordinates into a text file

extractPointsToTextFile(left_kml=None,
			right_kml=None,
			text_output_name=None)

• [REQUIRED] left_kml (string): File location of the kml file for left bank
• [REQUIRED] right_kml (string): File location of the kml file for right bank
• [REQUIRED] text_output_name (string): Output file name (and location)

import centerline_width
centerline_width.extractPointsToTextFile(left_kml="leftbank.kml",
					right_kml="rightbank.kml",
					text_output_name="data/river_coords_output.txt")

Output: The text file data/river_coords_output.txt with the headers llat, llon, rlat, rlon (for the left latitude, left longitude, right latitude, and right longitude)

Example:

     llat       llon      rlat       rlon
30.037581 -92.868569 30.119804 -92.907933
30.037613 -92.868549 30.119772 -92.907924
30.037648 -92.868546 30.119746 -92.907917
30.037674 -92.868536 30.119721 -92.907909
30.037702 -92.868533 30.119706 -92.907905

Converted Text File to CSV

Convert a text file with coordinates for a left and right bank's latitude/longitude to a csv file

convertColumnsToCSV(text_file=None, flipBankDirection=False)

• [REQUIRED] text_file (string): File location of the text file to convert
• [OPTIONAL] flipBankDirection (boolean): If the latitude/longitude of the banks are generated in reverse order, flip the final values so left/right bank are in order

Scripts expects data as a list of point for left and right banks:

• Header: llat, llon, rlat, rlon

import centerline_width
centerline_width.convertColumnsToCSV(text_file="data/river_coords.txt",
				flipBankDirection=True)

Converts text file:

     llat       llon      rlat       rlon
30.037581 -92.868569 30.037441 -92.867476
30.037613 -92.868549 30.037448 -92.867474
30.037648 -92.868546 30.037482 -92.867449
30.037674 -92.868536 30.037506 -92.867432
30.037702 -92.868533 30.037525 -92.867430

To a CSV file:

llat,llon,rlat,rlon
30.037581,-92.868569,30.037441,-92.867476
30.037613,-92.868549,30.037448,-92.867474
30.037648,-92.868546,30.037482,-92.867449
30.037674,-92.868536,30.037506,-92.867432
30.037702,-92.868533,30.037525,-92.867430

Output: A csv file data/river_coords.csv with the headers llat, llon, rlat, rlon

Centerline and Width

River Object

First, generate a river object to contain river data and available transformations

centerline_width.riverCenterline(csv_data=None,
				optional_cutoff=None,
				interpolate_data=False,
				interpolate_n=5)

• [REQUIRED] csv_data (string): File location of the text file to convert
• [OPTIONAL] optional_cutoff (int): Include only the first x amount of the data to chart (useful for debugging)
• [OPTIONAL] interpolate_data (bool): Interpolate between existing data by adding additional points
• [OPTIONAL] interpolate_n (int): Number of additional points to add between existing data, defaults to 5 (note: larger numbers will take exponentially longer to run, recommends less than 15)

Interpolating is an option that can be used to find a centerline when the existing data generates a Voronoi graph that is jagged or contains gaps dues to the combination of sparse data and a narrow river

Object (class) useful attributes:

• centerlineLatitudeLongtiude (list of tuples): List of the latitude and longitude coordinates of the centerline
• centerlineLength (float): Length of the centerline of the river (in km)
• rightBankLength (float): Length of the right bank of the river (in km)
• leftBankLength (float): Length of the left bank of the river (in km)

Object (class) additional atttributes:

• river_name (string): name of object, set to the csv_data string
• left_bank_coordinates (list of tuples): list of coordinates of the left bank generated from the csv file ([(x, y), (x, y)])
• right_bank_coordinates (list of tuples) list of coordinates of the right bank generated from the csv file ([(x, y), (x, y)])
• df_len (int): Length of the dataframe of the csv data spliced by the optional_cutoff
• bank_polygon (Shapley Polygon): Multi-sided polygon generated to encapsulate river bank (used to define an inside and an outside of the river)
• top_bank (Shapley Linestring): Linestring that represents the top of the river/polygon
• bottom_bank (Shapley Linestring): Linestring that represents the bottom of the river/polygon
• starting_node (tuple): Tuple of the starting position (latitude and longitude) of the centerline path
• ending_node (tuple): Tuple of the end position (latitude and longitude) of the centerline path
• bank_voronoi (scipy Voronoi object): Voronoi generated by left/right banks
• x_voronoi_ridge_point (list of tuples): X positions on Voronoi ridge (starting Latitude position to ending Latitude position)
• y_voronoi_ridge_point (list of tuples): Y position on Voronoi ridge (starting Longitude position to ending Longitude position)
• interpolate_data (bool): if interpolating between existing data, defaults to False
• interpolate_n (int): specifies how many additional points will be added when interpolating data, defaults to 5

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv")

Return Latitude/Longitude Coordinates of Centerline

Return the latitude/longtiude coordinates of the centerline based on the left and right banks

river_object.centerlineLatitudeLongtiude

Centerline coordinates are formed from Voronoi vertices

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv", optional_cutoff=15)
river_centerline_coordinates = river_object.centerlineLatitudeLongtiude

Output is a list of tuples: (example) [(-92.86788596499872, 30.03786596717931), (-92.86789573751797, 30.037834641974108), (-92.8679141386283, 30.037789636848878), (-92.8679251193248, 30.037756853899904), (-92.86796903819089, 30.03765423778148), (-92.86797335733262, 30.037643336049054), (-92.8679920356456, 30.037592224469797), (-92.86800576063828, 30.037555441489403), (-92.86800841510367, 30.037546512833107), (-92.8680119498663, 30.03753043193875)]

Return Length of Centerline

Return the length of the centerline found between the left and right bank

river_object.centerlineLength

Length returned in kilometers

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv", optional_cutoff=550)
river_centerline_length = river_object.centerlineLength

The length of the river centerline returns 215.34700589636674 km

Plot Centerline in Matplotlib

Plot the centerline created from a list of right and left banks with Voronoi vertices

plotCenterline(display_all_possible_paths=False, 
		plot_title=None, 
		save_plot_name=None, 
		display_voronoi=False)

• [OPTIONAL] display_all_possible_paths (boolean): Display all possible paths, not just the centerline (useful for debugging)
• [OPTIONAL] plot_title (string): Change plot title, defaults to "River Coordinates: Valid Centerline = True/False, Valid Polygon = True/False"
• [OPTIONAL] save_plot_name (string): Save the plot with a given name and location
• [OPTIONAL] display_voronoi (boolean): Overlay Voronoi diagram used to generate centerline

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv")
river_object.plotCenterline(display_all_possible_paths=False, display_voronoi=False)

Output:

Plot Centerline Width Lines in Matplotlib

Plot the Centerline Width Lines

Plot the width of the river based on the centerline

Display Centerline at even intervals from the Voronoi generated centerline

plotCenterlineWidth(plot_title=None, 
		save_plot_name=None, 
		display_true_centerline=True,
		n_interprolate_centerpoints=None,
		transect_span_distance=3,
		apply_smoothing=False,
		flag_intersections=True,
		remove_intersections=False)

• [OPTIONAL] plot_title (string): Change plot title, defaults to "River Coordinates: Valid Centerline = True/False, Valid Polygon = True/False"
• [OPTIONAL] save_plot_name (string): Save the plot with a given name and location
• [OPTIONAL] display_true_centerline (boolean): Display generated true centerline based on Voronoi diagrams
• [OPTIONAL] n_interprolate_centerpoints (int): Recreate centerline coordinates with n evenly spaced points, defaults to the number of rows in the csv file
• [OPTIONAL] transect_span_distance (int): Sum up n amount of points around a centerpoint to determine the slope (increase to decrease the impact of sudden changes), defaults to 6, must be greater than 2 (since the slope is found from the difference in position between two points), measured orthogonal to the centerline
• [OPTIONAL] apply_smoothing (bool): Apply a B-spline smoothing to centerline
• [OPTIONAL] flag_intersections (bool): Display intersecting width lines as red in graph, defaults to True
• [OPTIONAL] remove_intersections (bool): Iterative remove intersecting lines, to maintain the most width lines, but return only non-intersecting width lines, defaults to False

apply_smoothing

apply_smoothing applies a spline to smooth the centerline points created by the Voronoi vertices. This reduces the noise of the slopes and can create width lines that are less susceptible to small changes in the bank

apply_smoothing=False	apply_smoothing=True

transect_span_distance

Transect span describes the number of points that are averaged to generated a width line (example: transect_span_distance=3, average of three slopes)

transect_span_distance=6	transect_span_distance=30

remove_intersections

remove_intersections will remove the width lines that intersect other lines (that could be creating unrepresentative long width lines). Intersections are removed first in order from most to least (to ensure that the most width lines as possible are kept) and then, based on the longer of two intersecting lines

Intersecting lines are flagged in red by default (flag_intersections=True)

remove_intersections=False	remove_intersections=True

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv")
river_object.plotCenterlineWidth(save_plot_name="data/river_coords_width.png",
				display_true_centerline=False,
				n_interprolate_centerpoints=None,
				transect_span_distance=3,
				apply_smoothing=True,
				flag_intersections=True,
				remove_intersections=True)

Return Width of River

Return the width of the river at each (evenly spaced) centerline coordinate

riverWidthFromCenterline(n_interprolate_centerpoints=None,
			transect_span_distance=3,
			apply_smoothing=True,
			remove_intersections=False,
			units="km",
			save_to_csv=None)

• [OPTIONAL] n_interprolate_centerpoints (int): Recreate centerline coordinates with n evenly spaced points, defaults to the number of rows in the csv file
• [OPTIONAL] transect_span_distance (int): Sum up n amount of points around a centerpoint to determine the slope (increase to decrease the impact of sudden changes), defaults to 6, must be greater than 2 (since the slope is found from the difference in position between two points), measured orthogonal to the centerline
• [OPTIONAL] apply_smoothing (bool): Apply a B-spline smoothing to centerline
• [OPTIONAL] remove_intersections (bool): Iterative remove intersecting lines, to maintain the most width lines, but return only non-intersecting width lines, defaultsl to True
• [OPTIONAL] units (string): Units to measure distance, options: ["km" (kilometers), "m" (meters), "mi" (miles), "nmi" (nautical miles), "ft" (feet), "in" (inches), "rad" (radians), "deg" (degrees)], defaults to "km" (kilometers)
• [OPTIONAL] save_to_csv (string): Save river width output to a csv file, defaults to None (no file is saved)

import centerline_width
river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv")
river_width_dict = river_object.riverWidthFromCenterline(transect_span_distance=3,
							apply_smoothing=True,
							units="km",
							remove_intersections=True)

Width dictionary = {(-92.86792084788995, 30.037769672351182): 0.10969163557087018, (-92.86795038641004, 30.03769867854198): 0.10794219579997719}

Documentation and Algorithm to Determine Centerline

The centerline is defined by the greatest distance from the right and left bank, created from a Voronoi Diagram. The remaining paths within the river are filtered through Dijkstra's algorithm to find the shortest path that is the centerline

Right and Left bank points are plotted (X-Axis for Latitude, Y-Axis for Longitude)

Generate a polygon to encapsulate the river between the right and left banks to define in and outside of river

Generate a Voronoi based on the points along the river banks

Display Voronoi ridge vertices that lie within the polygon (within the river banks)

Filter out any point pairs that only have one connections to filter out the short dead end paths and find the starting and ending node based on distance from the top and bottom of polygon

With the vertices removed, it is possible form multiple unconnected graphs within the polygon. The largest subgraph is assumed to contain the centerline and the other subgraphs are filtered out

Find the shortest path from the starting node to the ending node (Dijkstra's Algorithm)

Points on River Bank	NetworkX Graph of Points on River Bank

Display the centerline found by connecting the starting/ending node with the shortest path

This is an attempt at a more robust algorithm working from raw data to ensure that all dead ends are removed and no gaps exist in the centerline

Points that only have one connection are removed, but by limiting the number of connections for a point to just two will create gaps. The Voronoi vertices connect to other vertex values, but some connect to more and some only connect to one other point. Removing additional values will create gaps, so this is avoided in this code by not applying additional filters.

All vertices:

Vertices that have at least two connections (that would create gaps):

Types of Centerlines

• Voronoi centerline: centerline generated from where Voronoi vertices intersect within the river
• Evenly Spaced Centerline: centerline based on Voronoi centerline but evenly spaced with a fixed number of points
• Smoothed Centerline: centerline generated from the evenly spaced centerline but smoothed by a b-spline

Debugging, Error Handling, and Edge Cases

Wide Start/End of River

If the data starts or ends with a large width, it is possible for the starting/ending nodes to end up in the wrong position Currently, the starting node is determined by the closest node to the top of the bank (in green) and the ending node is determined by the closest node to the bottom of the bank (in red) that sits along the longest path

Invalid Polygon

A polygon is formed to encapsulate the river with the given data (to determine the inside and outside of the river). The top and bottom are connected by a straight line from the start/end of the available data. As a result, it is possible for this straight line to overlap and create an invalid polygon.

A polygon is invalid if it overlaps within itself: In this example, the polygon is invalid, but with such a small overlap it is still able to find a valid path

With limited data, the polygon will overlap more dramatically and will struggle to find a valid centerline:

Invalid Centerline

If the data is too small, a centerline and its coordinates cannot not be found (since only a single Voronoi vertex exists within the polygon and after deadends are filtered)

CRITICAL ERROR, Voronoi diagram generated too small to find centerline (no starting node found), unable to plot centerline. Set displayVoronoi=True to view. Can typically be fixed by adding more data to expand range. Can be fixed by expanding the data until the polygon is large enough to contain at least two different vertex points

Invalid Top and Bottom Bank Postiions (flipDirection = True)

If the data for the left and right river banks are generated in reverse order, they will be read in the incorrect order and the graph will find the invalid top and bottom of the bank

If the latitude/longitude of the banks are generated in reverse order, flip the final values so left/right bank are in order

This can be fixed by using the flipDirection optional argument centerline_width.convertColumnsToCSV(text_file="data_example.txt", flipBankDirection=True)

Fix Gaps and Jagged Centerlines

Gaps formed can cause part of the centerline to be skipped due to sparse data. As a result, the start and end of the centerline can skip parts at the beginning or end of a river Set river object created by centerline_width.riverCenterline to interpolate_data=True to fix for jagged edges or gaps formed by the interaction of sparse data and narrow banks

river_object = centerline_width.riverCenterline(csv_data="data/river_coords.csv", interpolate_data=True)

interpolate_data = False	interpolate_data = True

The amount of additional points added by interpolating can be adjusted with interpolate_n, but defaults to add 5 additional points between values

Developer Notes: Tech Debt and Bug Fixes

• conversion of centerline lat-lon to meters
• Fix legend overlapping on graph, replace doc_examples that have an overlapping
• Verify that smoothing filter option does not produce a line that goes outside of the polygon

Citations

Based on work written in R (Golly et al. 2017):

Golly, A. and Turowski, J. M.: Deriving principal channel metrics from bank and long-profile geometry with the R package cmgo, Earth Surf. Dynam., 5, 557-570, https://doi.org/10.5194/esurf-5-557-2017, 2017.

Github - CMGO

This material is based upon work supported by the National Science Foundation Graduate Fellowship under Grant No. 2141064. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the atuhors and do not neccessarily reflect the views of the National Science Foundation.

Bug and Feature Request

Submit a bug fix, question, or feature request as a Github Issue or to [e-mail]/[e-mail]