We work a great deal with geographic data. The most common reason is to count the distance matrix (pairwise distances between a set of points), which is used in route optimization problems to steer resources in an optimal way.
Our STEM-heavy work environment also happens to include employees who have absorbed information of limited relevance from a range of topics. It gives us an edge in pub quizzes, so that’s nice.
One of the topics is geography, and since we already know how to work with geographical data we can generate our own nice little nuggets of information!
One interesting concept in geography is the pole of inaccessibility. These are points that are furthest away from the ocean, land, neighbouring states or similar, within a given geographic region. Prominent examples include
Point Nemo in the Southern Pacific Ocean (distance to nearest land 2705km)
and
the Eurasian Pole of Inaccessibility (distance to nearest ocean 2510km).
Now these are pretty rad, but have you thought about Finnish lakes and their coastlines?
Lakes globally mostly look like this:
(Lake Tahoe, USA; Lake Albert, Uganda & DRC; Lake Vättern, Sweden; Issyk-Kul, Kyrgyzstan).
Simple, well-behaving lakes with few islands. If you closed your eyes now and had to draw one of these from memory, it wouldn’t be that hard.
Whereas Finnish lakes look like this:
Lake Saimaa area is highlighted here, even though it’s a bit questionable whether it even is a single lake due to differences in water elevation between its parts. Its coastline resembles a fractal curve and the number of islands is disputed. Should you count islands that are within another island (there are numerous islands in lakes on islands in Saimaa)?
Due to the fragmented nature of Finnish lakes there are few large open lake areas. Where is the Point Nemo of our lakes? Surprisingly this information doesn’t seem to be available anywhere. Säkylän Pyhäjärvi, Oulujärvi and Saimaa are all provided as candidates for the title, but with varying definitions. Fortunately this is something that can be calculated with the help of an optimization algorithm.
The basic procedure is to generate points at random, select the ones in a lake, draw circles around them of an increasing size, recenter the circles once they start including land and stop when we think we’ve reached the solution.
In pseudocode we could do this as follows
Generate a set of points S
For each point A in S do the following
If point A is not in a lake, terminate procedure
Draw a circle around point A with radius 100m
Check if there’s land within the circle. If not, increase R by 10% and check again.
If yes: Case 1: one point of land, P1
Case 2: two points of land, P1 and P2
Case 3: three or more points of land
Case 1: move point A distance 0.1R directly away from P1 and draw a new circle of the same size.
Case 2: draw a line L between P1 and P2. Move point A distance 0.1R directly away from L’s midpoint
Case 3: reduce R by 5%. Redo procedure.
The hard part is that it’s been 4 years since I wrote a single line of code so this is going to be really painful. But here we go!
Let’s start by generating a set of points. I’m going to cheat a bit and eyeball the most promising locations on osm.org. (62.153, 29.406) in Saimaa (61.032, 22.252) in Pyhäjärvi and (64.297, 27.211) in Oulujärvi seem like good places to start. Drawing a circle around a point is possible using a query in Openstreetmap. In R code it looks like this:
library(osmdata)
circle <- osmdata::opq_around(center_lon, center_lat, radius = 100) %>% osmdata::osm_datasf()
The hard part is checking whether there’s water within the circle. Starting with the Pyhäjärvi location and 150m radius, it seems that the circle is “empty” (contains no features) when it has neither points, lines, polygons, multilines nor multipolygons within it. Already anticipating a lot of mistakes, I’m going to plot the data frequently to understand what’s happening.
I’ll start by plotting the entire lake with shorelines to get a better understanding of where we are … and there we have our next problem.
How hard can it be to plot a simple f’ing lake? I’ve spent an hour searching the web for a “for dummies” tutorial, but to no avail. Using the online map browser on osm.org I finally found out that openstreetmap objects have an ID and this can apparently be used to extract all relevant data about an object using something called an overpass API query. Why “overpass”? No idea, let’s just roll with it.
For Pyhäjärvi the OSM ID is 124564 so the lake can be plotted by:
pyhajarvi <- osmdata::opq_osm_id(124564, type='relation') %>% osmdata_sf()
ggplot(data=pyhajarvi$osm_polygons)+ geom_sf(color="blue", fill="lightblue")
Looks good (apart from the x axis coordinate labels, please ignore them)! Now we just need to add the circle. Should be simple, right? It is indeed, by using my favorite coding trick, which involves stack overflow and copypasting. Since there is no ready-made function for drawing a circle with a given radius in meters (you’d have to start changing map projections on the fly to use the available tools and that sounds like a real pain), the easiest way is to generate some points on the circle.
cleft <- center_lon-radius_km*(360/40075)*cos(center_lat*(pi/180))
cright <- center_lon+radius_km*(360/40075)*cos(center_lat*(pi/180))
cup <- center_lat+radius_km*(360/40075)
cdown <- center_lat-radius_km*(360/40075)
cwidth <- cright-cleft
cheight <- cup-cdown
x_coords <- cos(seq(0, 2*pi, 0.01))
y_coords <- sin(seq(0, 2*pi, 0.01))
x_circ <- (cwidth*2*x_coords)+center_lon
y_circ <- (cheight*0.5*y_coords)+center_lat
So now we have a way to plot circles of any size in any location and see the results. That’s good for verifying the correct answer, but we would need to locate the correct answer first. This brings us back to square number one with the optimization algorithm in pseudocode, which as such isn’t going to work because we still don’t know how to check whether a circle contains land or not.
Also the circles I earlier extracted from OSM data were some kind of hyperdimensional objects with different keys, features, line objects and so on which mere mortals like me can’t comprehend without a couple of days' work.
However it turns out that there is a way to calculate distance to a line using the aptly named dist2Line function. Fortunately it works for polygons and multipolygons too (lakes are multipolygons). Let’s try it out
dist2Line(c(center_lon, center_lat), as((pyhajarvi$osm_multipolygons$geometry), "Spatial"))
gives us
distance lon lat ID
[1,] 3393.373 22.195 61.01925 1
We know the distance to the nearest point on the shore from our location! Then the next step is to find a point even closer to the center of the lake. My tactic is to move the location away from the shore 1% of the distance between it and the closest shore point. In pseudocode our new revised algorithm works like this:
Choose point A within the lake
See where the closest point to the lake multipolygon is (point B).
Move point A 1% of the distance away from point B.
Repeat 100 times
Decrease the increment to 0.01%. Repeat 100 times. Report results.
This method is good for finding local optima. First it converges to the local optimum point and then starts bouncing around it. It is far from elegant, but gets the job done with enough precision as long as the starting point is somewhat sensible. E.g. in the Pyhäjärvi case starting from 61.032°N, 22.252°E we find the local optimum to be 61.03419°N, 22.25092°E and distance to the nearest shoreline is 3451 metres.
Let’s do the same for Oulujärvi. Starting from 64.297°N, 27.211°E we iterate our way to 64.28459°N, 27.19362°E, which is 4961m from the nearest shore.
Could Saimaa have an even larger space of open water? Let’s start from 62.153°N, 29.406°E and see where we end up. The Saimaa Point Nemo is at 62.15394°N, 29.40563°E and the distance to the nearest shore is 4387m. It doesn’t look like much if we plot the entire lake, so I’m choosing a section of it.
To find the global optimum we need to make sure we are looking in all the right places, but that’s a topic for another blog post.
For now we present to you the point furthest away (4961 metres) from the nearest shore in Finnish lakes, 64.28459°N, 27.19362°E, which is located in Ärjänselkä, Oulujärvi.
Are you interested in route optimization? Here you'll find our blog where we dig into the topic deeper.