multi_stop_search(optimize_order=True) silently drops waypoints when the distance matrix has no finite tour

[brendancol]

Describe the bug

multi_stop_search(optimize_order=True) can return a finite path that silently skips waypoints instead of raising ValueError. Two holes in _optimize_waypoint_order / _held_karp (xrspatial/pathfinding.py) combine here:

1. When no finite tour through all waypoints exists, every dp[full][j] + dist[mid[j]][end] in _held_karp is inf, so best_last stays -1 and the reconstruction loop exits immediately. The function returns [start] + [] + [end], dropping every interior waypoint. multi_stop_search then routes start -> end directly and returns a normal-looking result whose waypoint_order attr has fewer entries than the input. With optimize_order=False the same input raises no path between waypoints 0 and 1.

2. With snap=True, the distance matrix reads each segment cost at the unsnapped goal pixel (_get_pixel_id(waypoints[j], ...)). If waypoint j sits on a NaN/barrier cell, a_star_search snaps the goal and finds a path, but the unsnapped pixel is NaN in the segment image, so dist[i][j] stays inf for every i. That feeds hole 1: a waypoint that is fully reachable after snapping gets dropped. The main segment loop already handles this case (it relocates the goal to the max-finite-cost pixel); the ordering pass doesn't.

The non-exact path (_nearest_neighbor_2opt, N > 12) is not affected by the dropping: it always returns a complete tour, and the segment loop raises later if a leg is unreachable.

Reproduction (current main, numpy backend)

import numpy as np
import xarray as xr
from xrspatial import multi_stop_search

def make_raster(data):
    h, w = data.shape
    r = xr.DataArray(data.astype(np.float64), dims=['y', 'x'],
                     attrs={'res': (1.0, 1.0)})
    r['y'] = np.linspace(h - 1, 0, h)
    r['x'] = np.linspace(0, w - 1, w)
    return r

# Case 1: unreachable interior waypoint
data = np.ones((8, 8))
data[4, :] = np.nan                      # wall
agg = make_raster(data)
wps = [(7.0, 0.0), (0.0, 0.0), (7.0, 7.0)]   # middle one is below the wall

# multi_stop_search(agg, wps)  -> ValueError: no path between waypoints 0 and 1
r = multi_stop_search(agg, wps, optimize_order=True)
print(r.attrs['waypoint_order'])   # [(7.0, 0.0), (7.0, 7.0)]  <- middle dropped
print(r.attrs['total_cost'])       # 7.0 (finite, looks fine)

# Case 2: snap=True with a reachable (snappable) waypoint
data2 = np.ones((8, 8))
data2[3, 3] = np.nan
agg2 = make_raster(data2)
wps2 = [(7.0, 0.0), (4.0, 3.0), (0.0, 7.0)]  # middle sits on the NaN cell

r0 = multi_stop_search(agg2, wps2, snap=True)
print(len(r0.attrs['waypoint_order']))   # 3 (correct)
r1 = multi_stop_search(agg2, wps2, snap=True, optimize_order=True)
print(len(r1.attrs['waypoint_order']))   # 2  <- reachable waypoint dropped

Observed output:

[(7.0, 0.0), (7.0, 7.0)]
7.0
3
2

Expected behavior

• Case 1: raise ValueError, matching the optimize_order=False contract documented in the docstring ("Raises ValueError ... or a segment is unreachable").
• Case 2: keep all three waypoints; the ordering pass should use the same snapped-goal cost lookup as the segment loop.

Additional context

Found by the accuracy sweep. waypoint_order, segment_costs, and total_cost all report the truncated route, so downstream code has no signal that stops were skipped.