Path through sightseeings in Paris

For some reason the phrase "planning tourist visits" grabbed my attention today. It made me think about the way we visit sightseeings at new places and the way excursions are organized. "Planning" is key, since without it, we may travel too much or spend more time than we like. Or because of wasting time, we might be unable to see more of them.

So I thought about illustrating a case. I asked myself, "How would you go if you had to visit the sightseeings of Paris?" Not just the Eiffel Tower or the Louvre, but all of them. For two points, the answer would be simple, but for many it's not immediately obvious. What can we do if we are looking for a path?

First, we can extract a list of the sightseeings and enrich the labels with their geo-coordinates. To find which sightseeings are close, we will use the Euclidean distance. Here is the full code:

```from heapq import heappush, heappop import matplotlib.pyplot as plt def dist(p1,p2): p1lat, p1lon = p1 p2lat, p2lon = p2 return ((p2lat - p1lat)**2 + (p2lon - p1lon)**2) ** 0.5 # https://www.cometoparis.com/paris-guide/paris-monuments-s1032 sightseeing_names = """ Eiffel Tower, 48.858370, 2.294481 Palace of Versailles, 48.804865, 2.120355 Louvre Museum, 48.860611, 2.337644 Sacré Cœur, 48.886705, 2.343104 Notre-Dame Cathedral, 48.852968, 2.349902 Arc de Triomphe, 48.873792, 2.295028 Garnier Opera House, 48.871970, 2.331601 National Library of France, 48.833584, 2.375766 Pere Lachaise Cemetery, 48.861393, 2.393328 Hôtel de Ville, 48.856483, 2.352414 Hôtel des Invalides, 48.855186, 2.312584 Madeleine Church, 48.870044, 2.324550 Park Zoologique, 48.833354, 2.414208 Assemblée Nationale, 48.861699, 2.318217 Palais Brongniart, 48.869150, 2.341407 Palais Royal, 48.863757, 2.337126 Panthéon, 48.846222, 2.346414 Place de la Concorde, 48.865633, 2.321236 Stade de France, 48.924459, 2.360164 Grand Palais, 48.866109, 2.312454 Pont Alexandre III, 48.863900, 2.313559 Ecole Militaire, 48.852516, 2.303489 The Catacombs of Paris, 48.833832, 2.332422 Sainte Chapelle, 48.855420, 2.344987 Orsay Museum, 48.859961, 2.326561 La Sorbonne, 48.848380, 2.343459 Centre Pompidou, 48.860642, 2.352245 The Quai Branly Museum, 48.860889, 2.297894 Rodin Museum, 48.855307, 2.315835 Pont des Arts, 48.858342, 2.337508 Pont Neuf, 48.857050, 2.341325 Musée de l'Orangerie, 48.863788, 2.322672 Tuileries Garden, 48.863492, 2.327494 """ lines = sightseeing_names.split('\n')[1:-1] total_sightseeings = len(lines) coords = {} node_names = [] sightseeings = [] for line in lines: name, lat, lon = line.split(',') lat = float(lat) lon = float(lon) plt.scatter(lon, lat, s=25, color='#999999') node_names.append(name) sightseeings.append([name, lat, lon]) coords[name] = (lat, lon) # Show labels of the few points that are far away from the rest if lon < 2.15 or lon > 2.40 or lat > 48.90: plt.annotate(name, xy=(lon, lat), xytext=(lon, lat-0.005), ha='center', va='center', fontsize=9, color='darkred') start_node = 'Palace of Versailles' path = [start_node] while len(path) != total_sightseeings: distances = [] for name, lat, lon in sightseeings: if name not in path: heappush(distances, (dist(coords[start_node], (lat, lon)), name)) start_node = heappop(distances)[1] path.append(start_node) # Show the path for idx, sightseeing in enumerate(path): if idx < total_sightseeings - 1: p1lat, p1lon = coords[path[idx]] p2lat, p2lon = coords[path[idx+1]] plt.plot((p1lon, p2lon), (p1lat, p2lat), lw=1.4) plt.title('Locations of the sightseeings in Paris') plt.xlabel('longitude') plt.ylabel('latitude') plt.xlim(2.07, 2.458) plt.ylim(48.795,48.93) plt.tight_layout() plt.show() print(path) """ ['Palace of Versailles', 'Eiffel Tower', 'The Quai Branly Museum', 'Ecole Militaire', 'Hôtel des Invalides', 'Rodin Museum', 'Assemblée Nationale', "Musée de l'Orangerie", 'Place de la Concorde', 'Madeleine Church', 'Tuileries Garden', 'Orsay Museum', 'Pont des Arts', 'Louvre Museum', 'Palais Royal', 'Palais Brongniart', 'Garnier Opera House', 'Pont Neuf', 'Sainte Chapelle', 'Notre-Dame Cathedral', 'Hôtel de Ville', 'Centre Pompidou', 'La Sorbonne', 'Panthéon', 'The Catacombs of Paris', 'Pont Alexandre III', 'Grand Palais', 'Arc de Triomphe', 'Sacré Cœur', 'Stade de France', 'Pere Lachaise Cemetery', 'National Library of France', 'Park Zoologique'] """```

Initially we make ourselves a picture of the situation: plotting the point coordinates on a scatterplot and hoping that they are correct.

We see that some points are far away from most others. We can label them with a conditional statement and the annotate function. This makes them good candidates to be starting points on the path we are looking for. We can choose to start at Palace of Versailles, for instance.

Then we start building the path, one sightseeing at a time. As long as our path length isn't the same as the total number of the sightseeings, we check the distance between the start node and all other nodes, not currently on the path, and find the shortest one. We append the label corresponding to it and make that label the new start node. We repeat this process until all nodes are visited. Then we only connect the subsequent coordinates on the path and to arrive at this graphic:

The path has some sharp edges, but looks nice in its own way. In a short time, the generic phrase "planning tourist visits" received some concrete context.