Geo Engine
by Alex Sukholeyster, Vas Mylko
Ingeenee works together with the geo engine. This post is about the geo engine and the problems it tackles.
Intro
We are building our own knowledge graph for travel. The data structure follows the nature of travel. You book a hotel in some city for a couple of days and visit multiple attractions in the city or nearby areas. Then go to another city and so on. Points of Interest (POI), or attractions usually belong to the city, but there are exceptions. Natural parks, lakes, lonely trees, deserts could be anywhere, geographically disconnected from cities. There are many destinations that do not belong to any city. So there are attractions in cities, and there are isolated ones.
Cities and towns could be bound together so tightly, that it’s a real challenge to distinguish between them. Examples are twin cities Urbana-Champaign, San Diego-National City-Chula Vista, Los Angeles-Beverly Hills, Las Vegas-Paradise. Below are a few examples for the US. Original images were taken from Wiki Commons, and edited for better expressiveness.
There are special territories, like Gibraltar. There are disputed territories like West Bank, Crimea. There are micro-states Monaco, San Marino, Lichtenstein, Andorra. There is Vatican City in Rome, and there is a state Sovereign Military Order of Malta inside Vatican City. State within the state within the city! Go verify it yourself, and enjoy the process.
Connecting POIs to Cities
While there are many sources for geo-information, we decided to rely primarily on the data from Wikipedia and OSM. Almost all Wikipedia articles for places, contain location data, as coordinates of point or route. OSM contains location data for cities and boundaries for administrative regions (countries, regions, counties, cities, etc.)
To connect POI to city, we use its geo coordinates — latitude and longitude, and geo area of the city. We apply “point in polygon” algorithm to identify which POI belongs to what city. For some cities, we do not have digital representation of their area boundaries. Alternatively, we can use a combination of distance between POI and city center relative to the size/population of the city.
Get Curiosio’s stories in your inbox
Join Medium for free to get updates from this writer.
Some POI (many rivers, coasts, streets) are represented as ‘Route map’, or polyline, with many coordinates. This makes connecting a challenge. Especially with such long streets as 56 km long Yonge street. Even shorter streets is a challenge. What coordinates to use?
There are interesting cases requiring special handling. For example, New York City coordinates point to City Hall, which is excluded from OSM area for New York City for some reason. Dark areas of the map are routable, while that bright hole in the middle is not.
Some attractions could be approached from multiple countries. Matterhorn could be approached from Italy or Switzerland, Niagara Falls — from the US or Canada. Special handling is required to connect such POIs to the map (to avoid a case when Niagara Falls will be available only for Canada visitors, which is geographically correct, but not good for travelers from the US). Moreover, depending on whether your passport allows you visiting Canada from the US, you can experience the Niagara Falls from the US side only, Canada side or both.
Routing between Cities
Having locations of the cities, we need distance and travel time between them. It could be used directly for trip time optimization, building drive-time isochrones (selecting what’s theoretically reachable to visit within time), picking up other cities to visit along the road and so on. To calculate distances between those points, we use OSRM engine on top of OSM data (and consider Valhalla as an alternative). For a given pair of coordinates, we first locate the nearest routable point (point on the road), and then use directions API to get drivetime and mileage.
Depending on whether you want to travel through the US only, or the US and Canada, the route could be different (there are cases where the shortest trip from one US city to another US city goes through Canadian territories). We are going to support such cases by-design.
Isochrones and Reachable POIs
Drive time isochrones define the area, reachable within certain time for driving. It is not necessarily a round circle, as it depends on road density, quality, speed limits, traffic, and other factors. Back to road trips. You need about 15 hours to drive from Chicago to Boston. If you add New York as a midpoint, the total drive time will be 16 hours. To select all cities reachable within 20 hours on a trip from Chicago to Boston, we filter out ones for which Drivetime ( Chicago -> Some City) + Drivetime ( Some City -> Boston) is less or equal to 20 hours. In practice, the area will be much smaller, but this approach allows us to define the maximum reachable area for routing.
For cyclic road trips, isochrones look like flowers.
The Problem We Solve
Between cities and in the not-urban areas we are focusing on road trips by car. Transportation within the city often is easier by tubes, trams, buses, taxi. Car is the most flexible way of inter-city travel today. Autonomous shared cars will be even more flexible way of travel tomorrow. Especially for the last mile. You could stop anywhere you want, along the scenic road, at ad-hoc vista points, to enjoy the moment. The travel experience formula depends on multiple variables, including the value of individual POIs, matching with user preferences, weather and timing, drive time. To see more and experience more within the same time of travel, you need to drive less and drive through the most scenic ways. The drive time optimization is special case of TSP (Travelling Salesman Problem), while overall experience optimization problem is a case of CSP (Constraint Satisfaction Problem) within time, budget, geo area, and user preferences.
Latest version is available at https://ingeenee.ai
