Base routing has disconnected road islands

[vshcherb]

Related issues (reverted / not fixed currently)

• OsmAnd did not use the ferry crossing for a shorter route #15384
• Routing to Samsø Rederi in Hou (access=yes node) #14924
• Navigation wrong Route Osterwall-Ismaning Bavaria #11770
• Car route is slower when adding no intermediate point, and faster when adding one #17882

---

1. Algorithm find road clusters by simple connectivity (https://github.com/osmandapp/OsmAnd-tools/blob/fixBaseRoutingRoads/java-tools/OsmAndMapCreatorUtilities/src/main/java/net/osmand/obf/preparation/ImproveRoadConnectivity.java#L48) IMPROVE_ROUTING_ALGORITHM_VERSION = 2 (makeAreaDisconnectedPoints).

Pros:

• Very simple implementation - 200-300 LOC
• Very quick calculation (Denmark region - 30 second)
• Finds very few possible road isolations (100 for Denmark)
• Simple constants to control and possible to run few iterations

Cons:

• Doesn't fix issue with oneways (Routing to Samsø Rederi in Hou (access=yes node) #14924)

2. Algorithm compare Base Routing vs Normal Routing - IMPROVE_ROUTING_ALGORITHM_VERSION = 1.

1. For all isolated points calculate 2 Dijsktra Algorithm on Base Routing and Normal Routing. Start: isolated point, Stop at 20 KM (Constant) from point
2. Compare reachable points, if base point wasn't reached by Base Layer Dijkstra but was reached by Normal Layer Dijkstra should be added "shortcuts"

Pros:

• Finds all "missing routes" from isolated points
• Completeness

Cons:

• Doesn't find "missing route" between 2 parallel roads for example.
• Quite a lot of disconnected points present on some maps ~1000 and requires ~1000 requests

[vshcherb]

Test that mentioned cases are fixed with HH routing.

[RZR-UA]

Tests are done.

Summarized results marked in 1st message's todo list.

Detailed results and screenshots were added to the corresponding issues.

[vshcherb]

Tests to compare A* / HH - Java (Routing time & Geometry):

Ferry Issue #15384

• BRP C++ = BUG

• BRP Java = SOLVED

• HH Java = NOT-OK (longer route, another ferry is used)

• HH != BRP

TODO:

• recheck original issue when Ivan commit C++ changes
• find out the reason why HH != BRP

Gate (before Ferry) Issue #14924

• BRP C++ = SOLVED

• BRP Java = SOLVED

• HH Java = ALMOST-OK (slightly faster route)

• HH ~= BRP

Wrong (non-optimal) car-route with avoid_motorway #11770

• BRP C++ = BUG

• BRP Java = BUG

• HH Java = SOLVED

• HH != BRP

TODO:

• the bug still exist and should be fixed
• compare HH == BRP after BRP fix

Wrong route (slow-by-time / distance) #17882

• BRP C++ = SOLVED

• BRP Java = SOLVED

• HH Java = SOLVED

• HH == BRP

[RZR-UA]

html-report.zip

SLOW:

2-PHASE: