waypoint_merge – Waypoint and Route Merge Application

With multiple chart plotters, it’s very easy to have waypoints defined (or modified) separately. It’s necessary to reconcile the changes to arrive at a single, comprehensive list of waypoints that can be then distributed to all devices.

This requires reading and comparing GPX files to arrive at a master list of waypoints.

Similar analysis must be done for routes to accomodate changes.

Here’s the structure of this application

@startuml component waypoint_merge { class Waypoint_Plot class History History *-- "2" Waypoint_Plot class WP_Match { wp_1: Waypoint_Plot wp_2: Waypoint_Plot } WP_Match::wp_1 -- "?" Waypoint_Plot WP_Match::wp_2 -- "?" Waypoint_Plot } component navigation { class Waypoint { lat: Lat lon: Lon } } Waypoint_Plot *-- Waypoint @enduml

This module includes several groups of components.

  • The Input Parsing group is the functions and classes that acquire input from the GPX or CSV file.

  • The Processing functions work out range and bearing, magnetic bearing, total distance run, and elapsed time in minutes and hours.

  • The Output Writing group is the functions to write the CSV result.

  • Finally, the CLI components are used to build a proper command-line application.

Input Parsing

There are two kinds of inputs

  • GPX files. Each source has a unique logical layout imposed over a common physical format.

    • OpenCPN GPX. These tend to be richly detailed, using OpenCPN extensions.

    • Chartplotter GPX. These are minimal, skipping import details like GUID’s that provide unique identity to routes and waypoints.

  • USR files. Also called “Lowrance USR files.” These are a binary dump of chartplotter information.

Base Classes

Plotted image of a waypoint.

Input Processing

Generates Waypoint_Plot onjects from an OpenCPN GPX doc.

<wpt lat="37.184990000" lon="-76.422203000">
  <time>2020-09-30T07:52:39Z</time>
  <name>Chisman Creek</name>
  <sym>anchor</sym>
  <type>WPT</type>
  <extensions>
    <opencpn:guid>34de7898-f37e-458c-8ccb-e4e03fa325ec</opencpn:guid>
    <opencpn:viz_name>1</opencpn:viz_name>
    <opencpn:arrival_radius>0.050</opencpn:arrival_radius>
    <opencpn:waypoint_range_rings visible="false" number="-1" step="-1" units="-1" colour="#FFFFFF" />
    <opencpn:scale_min_max UseScale="false" ScaleMin="2147483646" ScaleMax="0" />
  </extensions>

This uses a BUNCH of namespaces

  • xmlns="http://www.topografix.com/GPX/1/1"

  • xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"

  • xmlns:gpxx="http://www.garmin.com/xmlschemas/GpxExtensions/v3"

  • xmlns:opencpn="http://www.opencpn.org"

Parameters

source – an open XML file.

Returns

An iterator over LogEntry objects.

Generates Waypoint_Plot onjects from an Chartplotter GPX doc.

<metadata>
    <time>2021-06-04T16:55:38Z</time>
    <depthunits>meters</depthunits>
    <tempunits>C</tempunits>
    <sogunits>m/s</sogunits>
</metadata>
<wpt lon="-80.22695124" lat="25.71541470" >
    <time>2017-05-28T19:15:52Z</time>
    <name>Coconut Grove</name>
    <sym>anchor</sym>
</wpt>

This uses one namespace

  • xmlns="http://www.topografix.com/GPX/1/1"

Parameters

source – an open XML file.

Returns

An iterator over LogEntry objects.

USR Details

{'uuid': UUID('41f0e2b8-e631-462a-82fd-f5292523f98d'),
'UID_unit_number': 12988,
'UID_sequence_number': 328,
'waypt_stream_version': 2,
'waypt_name_length': 18,
'waypt_name': 'ALLIGTR C',
'UID_unit_number_2': 12988,
'longitude': -76.64669528,
'latitude': 24.38829583,
'flags': 4,
'icon_id': 0,
'color_id': 0,
'waypt_description_length': -1,
'waypt_description': '',
'alarm_radius': 0.0,
'waypt_creation_date': datetime.date(2017, 6, 11),
'waypt_creation_time': datetime.timedelta(seconds=36080, microseconds=754000),
'unknown_2': -1,
'depth': 0.0,
'LORAN_GRI': -1, 'LORAN_Tda': 0, 'LORAN_Tdb': 0}
Parameters

source –

Returns

Processing

This is part of a four-step use case.

  1. Dump charplotter-unique waypoints. These are not on the computer, which should be the single source of truth.

  2. Merge the waypoints, loading OpenCPN. Make manual edits and updates to cleanup and simplify. Locate “to-be deleted” waypoints. These are duplicates (or near duplicates) that need to be merged and reconciled. Removing a waypoint can break routes, so route editing is part of this. There several cases:

    • Same name, new location. These are updates to OpenCPN to move an existing waypoint to a new location. It’s not clear how this should be done, but GUID matching should make this work.

    • Different names, proximate locations. The waypoint was renamed or is a duplicate.

    • New name, unique location. These are simply added.

  3. Dump chartplotter-unique routes (if any.) These are not on the computer, which is the single source of truth.

  4. Merge the routes into OpenCPN. Make any manual edits.

We’re focused on step 2, and the various comparisons between waypoints to determine what merge should be done. Step 2 decomposes into three phases:

  • Survey of differences. This is an text (or HTML) file with a comparison using all of rules.

  • Preparation of modifications; this is a GPX file that can be used to load OpenCPN. Some manual changes may be needed before these waypoints can be used.

  • Preparation of adds; this is a GPX file that is simply loaded into OpenCPN, since the waypoints are all new.

Comparisons

We have a number of comparison rules among waypoints. We can meaningfully compare waypoints on any of the following attributes:

  • “name” – While names change, they also reflect old technology limitations. So, some names are sometimes rewritten on a new device. There’s no near-miss matching here because “CHPTNK6” may have become “Choptank Entrance 6” with few overlapping letters.

  • “guid” – These should be immutable, but it’s not clear if it’s preserved in tranfers between devices.

  • “distance” – this is the waypoint-to-waypoint distance computation. This is the equirectangular distance. While accurate it’s also computationally intensive.

  • “geocode” – this is the faster geocode-based proximity test. Intead of computing \(m \times n\) distances, we can compute \(m + n\) geocodes, and use string comparison for a simple proximity check. The loxodromic or equirectangular distance involves a lot of computation. Using truncated OLC permits flexible adjacency via simple string-based processing. Less math. See https://en.m.wikipedia.org/wiki/Open_Location_Code

    positions

    degrees

    distances

    6

    1/20

    5566 meters, 3 nmi

    8

    1/400

    278 meters, .15 nmi

    10

    1/8000

    13.9 meters, 45 feet

This leads to a four comparison outcomes.

  • Same Name – Different Locations. This means a waypoint was moved. It can also mean two waypoints were created near each other with coincidentally identical names. This is a GPX file of waypoints which must be modified in OpenCPN.

  • Different Names – Proximate Locations. These are likely simple duplicates; one of the two must be removed, and the other used for all routes. Depending on the use within OpenCPN routes, this may be a complex change to modify reoutes to replace a waypoint.

  • Completely Different. In this case, Chartplotter points need to be added to the OpenCPN computer points. This should be visible as a GPX file of waypoints to add.

  • The Same. These are simple duplicates that can be ignored.

Classes and Functions

The state of the matching operation.

Each History reflects a waypoint and the matches against other waypoints from the same source, or waypoints from a different source.

Given a comparison function, updates two collections of History objects, to reflect matches between the waypoints.

This does a brute-force \(m \times n\) comparison of all items in both lists. It applies the comparison() function to all elements to locate matches.

The remaining items are exclusive to list 1 or list 2, representing the unmatched items.

Applies the rule to the History to accumulate all matches.

Compares names simply. Levenshtein distance might be helpful.

Compares GUID’s. Assumes collection 1 is OpenCPN.

Assumes pt1 is OpenCPN and pt2 is from the chartplotter.

Uses Waypoint definition of near(). Has a hard-coded distance threshold of ±0.05 nmi.

Uses OLC matching to a given number of positions.

positions

degrees

distance

8

1/400

278 meters, .15 nmi

10

1/8000

13.9 meters, 45 feet

default size is 8.

Usaage:

c = CompareByGeocode.range(8)()
c.compare(l1, l2)

Report on duplicates. Also, returns a reduced list of waypoints with duplicates removed.

Given a collection of duplicates, we use the we use the last_updated time to locate the newest copy and keep that.

Parameters

wp_list – list[Waypoint_Plot], usually from a derived list in a chartplotter

Returns

list[Waypoint_Plot] with duplicates removed.

Report on the comparison of two waypoint lists. This is a human-readable DIFF-like report, it uses all of the comparison algorithms to locate candidate duplicates.

Parameters

  • wp_1 – Waypoints, usually from the master list in OpenCPN

  • wp_2 – Waypoints, usually from a derived list in a chartplotter

Output Writing

We translae the two sequences of history information into a single stream of WP_Match instances. We can then summarize these.

We use Jinja2 to write an XML-format file with the waypoints that need to be updated in OpenCPN.

The final match result. There are three states.

  • Both – they passed the given comparison test, and appear to be the same

  • 1 only – From the first source (usually the computer) with no match

  • 2 only – From the second source (usually the chart plotter) with no match

Alias for field number 0

Alias for field number 1

Return a new dict which maps field names to their values.

Make a new WP_Match object from a sequence or iterable

Return a new WP_Match object replacing specified fields with new values

Merge two sequences of History instances into single sequence of WP_Match instances.

There are three subtypes of matches in the final sequence:

  • Something was the same.

  • Only in the first history list (usually the computer) with no match.

  • Only in the second history list (usually the chart plotter) with no match.

Inject waypoint data into an XML template.

Parameters

source – source of Waypoint_Plot instances.

Returns

XML document as text.

Report on a list of WP_Match instances. This is a GPX Upload to get the computer up-to-date with what’s on the chartplotter.

This has two clumps of data.

  1. Common but not proximate: these may need to be updated on the computer to reflect changes on the chartplotter. (Or. They may need to be updated on the chartplotter.)

  2. Chartplotter only: these need to be transferred to the computer.

CLI

A typical command looks like this:

python navtools/waypoint_merge.py -p data/WaypointsRoutesTracks.usr -c "data/2021 opencpn waypoints.gpx" --by name --by geocode

This produces a report comparing the .USR output from the chartplotter with the GPX data dumped from OpenCPN. Waypoints are compared by name for literal matches, then by Geogode for likely matches that have different names.

The output is a list of points that have been created or changed in the chartplotter, plus a less-interesting list of points that are only in the computer.

Waypoint merge. Parses the command line options. Compares two files, and emits a report/summary or GPX.

Todo

parameterize the distance or geocode options.