Weather routing simplification

[sebastien-rosset]

When planning a sailing route using weather routing software, the algorithm typically generates many waypoints to navigate around weather patterns, currents, and other conditions. This often results in routes with dozens or even hundreds of waypoints - far more than necessary for practical navigation.

Route simplification intelligently reduces the number of waypoints while maintaining the essential characteristics of the original route. The goal is to create a simplified route that:

1. Requires substantially fewer waypoints
2. Maintains navigational safety (avoiding land and hazards)
3. Follows a similar path to the original route
4. Has minimal impact on the estimated arrival time (ETA)

Below is a visual representation of routing simplification from 47 waypoints to just 3 segments. The waypoint reduction is exaggerated to help with the discussion.

1. Segment 3 helps to reduce the number of waypoints without any significant loss of performance. There is a reduction of waypoints from 11 to 2.
2. Segment 2 shows a hypothetical scenario the simplified segment crosses an obstacle or land. So the simplification algorithm will need to be carefully designed to evaluate the same weather and navigation constraints as during normal isochron propagation.

Benefits

When a route has been simplified and is activated:

1. The crew has a better understanding of where the next significant waypoint is, as opposed to having many intermediate waypoints that are not very meaningful.

Solution

The algorithm could include multiple phases.

Phase 0: Input parameters

User specifies input parameters to control the routing simplification.

1. Max acceptable ETA loss after simplification.

Phase 1: Reduce number of sailing maneuvers

1. After the initial isochron calculation, get the number of sailing maneuvers (tack, jibe and sail plan change).
2. If the number of maneuvers is high (perhaps configurable), slightly increase the penalty for these maneuvers. This should provide a different optimal route that has fewer maneuvers.
3. Compare the original ETA versus the ETA after maneuver reduction. If the loss of performance is acceptable, then retain the new route.

Phase 2: Split route based on sailing maneuvers

Split the route in segment between each sailing maneuver (tack, jib, sail plan change). A tack, jibe, or sail change represents a fundamental change in the sailing strategy that cannot be simplified away, regardless of geometric considerations.

For example, if a segment has 3 waypoints and a tack occurs in the intermediate waypoint, then the segment cannot be simplified to 2 waypoints. The boat is going upwind.

Phase 3: Simplify each segment

Each segment identified in phase 2 is simplified independently. A geometric simplification algorithm (e.g. Douglaspeucker, angle threshold...) could be used to reduce the number of waypoints. I.e., find waypoints that are colinear within some epsilon value. For example, in the above screenshot, 11 waypoints in segment 3 are almost perfectly colinear and can be simplified to a single segment without loss.

At the end of phase 3, each segment is further sub-divided in sub-segments that approximate the original weather routing plan.

Phase 4: Evaluate Constraints for each simplified sub-segment

There is a possibility that simplified sub-segments might fail constraint validation. This is what is visually represented in "segment 2" in the screenshot. Even though the simplified segment is a close approximation of the original waypoints, it's possible the new segment will no longer satisfy one or more constraints (navigation and weather).

For each sub-segment, the algorithm should apply the same constraint evaluation as what is done in the Propagate() method. I.e. check for land, obstacles, wind, current, max diverted course, max latitude, polars, etc.
If a simplified sub-segment no longer satisfies the constraints, then re-complexify the segment by adding an intermediate waypoint, recursively. In the worst case scenario, the original route cannot be simplified.

In the above screenshot, segment 2 could be split into 2 sub-segment 2a and 2b. That still provides a significant overall simplification.

The simplification algorithm will need a function to Propagate the boat along a simplified rhumb line. This is similar but not quite the same as the existing functions:

1. Propagate() moves the boat forward for a fixed duration. The target point is reached after the boat has sailed the isochron after a fixed duration.
2. PropagateToPoint() moves the boat towards a fixed target point. But currently, this function only works for very short distances. This function takes the weather information at the starting point and assumes the conditions are going to be exactly the same all the way to the endpoint. This is a reasonable approximation if the starting point and endpoint are close (which is typically the case during isochron propagation).

The simplification algorithm needs something like PropagateToPoint(), but extended to work with target points that may be far from the starting point. Because the segments are simplified and the number of waypoints is reduced, the distance between start and end points can be quite far. This means the weather conditions cannot be assumed to be the same everywhere along the simplified segment.

Comparing Propagate() and PropagateToPoint(), these 2 functions evaluate constraints, but the code is duplicated.

[rgleason]

How would routing simplification work with respect to the WR constraints set and the "optimal route"?
Is it just a separate step that is done after the "optimal route" is found?
Would heaving to and other techniques to avoid bad weather be changed?
How does route simplification work, does it run the entire calculation a second time, trying to select route points further and further apart?
Does it just drop out 4 of every 5 points and test a new routing, then compare? Then do that again?
Just how is it going to figure out which points to keep and which to remove?

Maybe it will just run the routing again and try to drop the previous waypoint to see what difference it makes, then do the next isochrone and find the next point on the route, then try dropping the previous waypoint to see what difference it makes, etc.

You show it going through land. Was that intentional?

[rgleason]

I like this:

to find waypoints that are colinear within some epsilon value. For example, in the above screenshot, the 11 waypoints in segment 3 are almost perfectly colinear.

I hadn't thought of

Phase 2: Split route based on sailing maneuvers

[sebastien-rosset]

Hopefully you have the answers to your questions in the description. I'm still working on the description.