find_shortest_path

pyhelpers.geom.find_shortest_path(points_sequence, ret_dist=False, as_geom=False, **kwargs)

Find the shortest path through a sequence of points.

Parameters

• points_sequence (numpy.ndarray) – a sequence of points

• ret_dist (bool) – whether to return the distance of the shortest path, defaults to False

• as_geom (bool) – whether to return the sorted path as a line geometry object, defaults to False

• kwargs – (optional) parameters used by sklearn.neighbors.NearestNeighbors

Returns

a sequence of sorted points given two-nearest neighbors

Return type

numpy.ndarray or shapely.geometry.LineString or tuple

Examples:

>>> from pyhelpers.geom import find_shortest_path
>>> from pyhelpers._cache import example_dataframe

>>> example_df = example_dataframe()
>>> example_df
            Longitude   Latitude
City
London      -0.127647  51.507322
Birmingham  -1.902691  52.479699
Manchester  -2.245115  53.479489
Leeds       -1.543794  53.797418

>>> example_df_ = example_df.sample(frac=1, random_state=1)
>>> example_df_
            Longitude   Latitude
City
Leeds       -1.543794  53.797418
Manchester  -2.245115  53.479489
London      -0.127647  51.507322
Birmingham  -1.902691  52.479699

>>> cities = example_df_.to_numpy()
>>> cities
array([[-1.5437941, 53.7974185],
       [-2.2451148, 53.4794892],
       [-0.1276474, 51.5073219],
       [-1.9026911, 52.4796992]])

>>> cities_sorted = find_shortest_path(points_sequence=cities)
>>> cities_sorted
array([[-1.5437941, 53.7974185],
       [-2.2451148, 53.4794892],
       [-1.9026911, 52.4796992],
       [-0.1276474, 51.5073219]])

This example is illustrated below (see Fig. 11):

>>> import matplotlib.pyplot as plt
>>> import matplotlib.gridspec as mgs
>>> from pyhelpers.settings import mpl_preferences

>>> mpl_preferences(font_name='Times New Roman')

>>> fig = plt.figure(figsize=(7, 5))
>>> gs = mgs.GridSpec(1, 2, figure=fig)

>>> ax1 = fig.add_subplot(gs[:, 0])
>>> ax1.plot(cities[:, 0], cities[:, 1], label='original')
>>> for city, i, lonlat in zip(example_df_.index, range(len(cities)), cities):
...     ax1.scatter(lonlat[0], lonlat[1])
...     ax1.annotate(city + f' ({i})', xy=lonlat + 0.05)
>>> ax1.legend(loc=3)

>>> ax2 = fig.add_subplot(gs[:, 1])
>>> ax2.plot(cities_sorted[:, 0], cities_sorted[:, 1], label='sorted', color='orange')
>>> for city, i, lonlat in zip(example_df.index[::-1], range(len(cities)), cities_sorted):
...     ax2.scatter(lonlat[0], lonlat[1])
...     ax2.annotate(city + f' ({i})', xy=lonlat + 0.05)
>>> ax2.legend(loc=3)

>>> plt.tight_layout()
>>> plt.show()

Fig. 11 An example of sorting a sequence of points given the shortest path.