Tuesday, November 10, 2020

Excursions: The Seven Bridges of Königsberg


Making a little test with a new kind of blog post format where I explore some interesting fact related to geography and some history and fact around it.

For this first one I was going to take a look at the mathematical problem involving the bridges of Königsberg (present day Kaliningrad).

I have an old mathematical chart that I got from my father:



 
I used to study this a lot growing up and I recently was a bit curious as to when it was actually issued. The chart was issued by a company called Original-Odhner (https://sv.wikipedia.org/wiki/Original-Odhner, there is no English article in Wikipedia for it…) and doing some more research I found a mention of this chart in an old issue of a technical magazine called “Teknisk Tidskrift” from 1959 (http://runeberg.org/tektid/1959/0026.html) where the chart is mentioned as being recently published, so that should put it around 1959, or perhaps 1958.
 
In any case, up near the top left corner there is a description of this topological problem outlined above:
 

  So, the subject of this post is the problem with the seven bridges of Königsberg in what was back in Leonard Euler's days in the 18th century Prussia (nowadays Kaliningrad, today a Russian enclave surrounded by Lithuania and Poland). In those days the two islands of city was connected by seven bridges and a common passtime of the recidents was to try to come up with a way of performing a walk crossing all the bridges, but only cross each bridge of time (https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg)
 
Euler managed to prove in 1736 that this is a mathematically impossible problem. Part of the solution involved the abstraction of the problem into one of a pure graph. Thus ignoring the choice of paths in areas on land and the islands, between the bridges. Being irrelevant (for the solution of this specific problem). And this is a very important observation. The same principle applies for the algorithms we use today for finding shortest or quickest routes. By treating the way segments as edges in a graph with weights (corresponding to e.g. distance, time required, or other significant parameters ranking preferred characteristics) ignoring things like the actual bends and twists between each intersection where a choice of direction needs to be taken.
 
To conclude this, we could take a virtual excursion to present-day Kaliningrad.
 

  The central island that the town center in Euler's days, is now a park (it was devastated during WWII)


Of the original seven bridges of the old puzzel, five remain in their position today (only two seems to be the original ones from 1736). And incidentally one can actually make an equivalent walk today, using the present day bridges.


Hope you liked this form of post, and maybe somebody has ideas for other places and stories to explore!

Sunday, October 18, 2020

Maps in GNOME 3.38

 It's been a while since the last blog post and it's been a while since 3.38.0 was released, and in fact there was already the stable on-schedule 3.38.1 release. On top of that a sneaky asynchronous programming bug showed up that in some circumstances such as high-latency connections, or fast typing can give out-of-sync search results I cut an extra 3.38.1.1 patch release.

But now to the summary of the 3.38 user-facing changes. I think all of this has been covered in previous posts, but I guess it's always nice with a bit of a summary.

For one thing, we now have a night mode, utilizing Mapbox' dark tile set:

 





Another feature that had been requested for quite some times was hybrid aerial mode (showing labels for street names, names of places and so on):


And thanks to work by James Westman the first step towards an adaptive UI (for e.g. smaller screen scenarios) has been implemented where a bottom action bar appears “taking over” some of the buttons from the header bar, leaving the search entry and main menu in narrow mode.

And video of the feature in real life says more than pictures here:


We had also planned to make the routing sidebar adaptive for 3.38, enabling it to take over the view (with a back button, as in other similar phone-enabled UIs) when in narrow mode, by utilizing the adaptive widgets from libhandy. But unfortunately some issues showed up under Wayland with some graphics driver (related to Clutter), so we had to roll back this before the release.

And stay tuned for updates on upcoming stuff for GNOME 40!

Wednesday, July 1, 2020

Summer Maps

Since it's been a while since the last post, I thought I should share a little update about some going ons with Maps.

There's now a new night mode, utilizing Mapbox' dark street tile set:











































Another thing that has been requested from time to time is showing labels on the satellite mode (“hybrid” aerial). Originally the plan was more along the line of rendering vector tile data on the client-side and have this rendered as a separate layer on top of the regular “vanilla” aerial tile set. But since vector tile support has not materialized yet, another idea has been to take advantage of Mapbox' hybrid raster tiles (”satellite-streets” as they call them). So I decided to implement that, to finally have this feature:

 So, when selecting the aerial view, a checkbox appears allowing to switch on the hybrid mode.

Another thing I have missed for a while was having some sort of regression testing, e.g. some form of unit tests. I decided to roll a custom quite simplistic solution consisting of a small bit of Meson “code” to dynamically build launch scripts invoking GJS on each of a set of .js files and have the Meson test clause execute them, as can be seen here: https://gitlab.gnome.org/GNOME/gnome-maps/-/tree/master/tests.
It currently only have a few test cases, but it's a start, I guess :-)

Furthermore I took some time to make the rendering of various places where numbers and times are shown to use the locale-depending formatting functionallity in ES (JavaScript) to get rid of some remaining places that still used hard-coded %d-like format strings, resulting in always using western-style digits, as can be seen in the following after this, using a Persian (فارسی) locale:


But, maybe we should keep the most most exiting thing til last… a little over a year ago I started a new project (libshumate) with the intention of trying to build a GTK 4 implementation of a libchamplain-like API for rendering map tiles (and markers and such). Lately Corentin Noël (tintou) took up the ball and has managed to get up to a state where it's working enough to actual display stuff (and scroll and zoom around):

This is the simple “launcher” demo from within the project, actually displaying a map in a GTK 4 world.
And since everything is GTK widget, you can use the GTK Inspector to look around at the internals for testing/debugging:

And “everything is a widget”, like the actual tiles, so you can for example toggle off visibility of a single map tile, since it's just a regular GTK widget, like so:


I'm very impressed with Corentin's work!
It's very exiting, I think it's at a point where it should probably be possible to do WiP work using in Maps (but for now probably with only barebones rendering of actual map view working).

Sunday, March 29, 2020

Maps in GNOME 3.36

There's been quite a while since the last blog post. Since then 3.36.0 was released, and also the first update for the stable 3.36 branch, 3.36.1 has been released.
As I've written about before one of the main features in 3.36 is the support for trip planning for public transit using third party services, as shown here from Paris:


We also support a few other areas for now, such as TriMet in Portland, Sweden (using the Resrobot API), and the Switzerland using the opendata.ch API. A full list is available on a sub page to https://live.gnome.org/Apps/Maps

Another feature implemented by James Westman is that the current location marker should no longer flicker when you have live-updating (e.g. when you have an actual GPS receiver on your device).

James has also implemented the first step towards a responsive UI that can scale to phone and narrow tablet portrait displays, this was finished after the UI change freeze before 3.36, so it will have to wait until 3.38


Oh and another thing, in these times when physical traveling is not an option browsing around in Maps application is another way to explore. And don't forget take advantage of the interlinking with Wikipedia from the OpenStreetMap database (Maps will show a link to a Wikipedia article for a place if available when you press the “Show more“ three-dots icon in a place info bubble). And if it's missing you can always add it yourself.

Be safe everyone!

Monday, December 23, 2019

Christmas Maps

To stick to the tradition I thought that I should write a little post about what's been going on since the stable 3.34 release in September. The main thing that's come since then for the upcoming 3.36 release is support for getting public transit route/itinerary planning using third-party providers. The basic support for public transit routing, based on OpenTripPlanner has been in place since 2017 with the original plan to find funding/hosting to set up a GNOME-specific instance of OTP fed with a curated set of GTFS feed. But since this plan didn't come to fruition, I repurposed the existing support so that it can fetch a list of known providers with defined geographical regions. First by utilising the existing OpenTripPlanner implementation (but rewritten to be instanciated per third-party provider). Later I have added plugins for the Swedish Resrobot and Swiss opendata.ch online API. These have yet not been activated in the service file (it's using the same service file as for tile and search providers). But this will soon be there, so stay tuned.

And since it kinda mandatory with a screenshot, here's one showing a case from Paris:


Happy holidays!

Monday, September 2, 2019

Maps and GNOME 3.34

Just released Maps 3.33.92, the last beta release before the GNOME 3.34.0 release next week.

I've already covered other news earlier, such as “search-as-you-type” auto-complete search and the new sharing dialog, allowing opening locations with any application capable of handling geo: URIs. I also implemented support for opening URLs pointing to objects in OpenStreetMap directly in Maps. This can be handy in cases when someone pastes such a URL in a chat for example (and the new sharing dialog allows to copy the same type of URL to the clipboard, or as an e-mail).

James Westman has also implemented a change in how startup works, so that Maps now will open directly at the location you last viewed, instead of starting from a view of the entire world and then animating to the location. We now also remember the map type as set when closing the app the last time (“normal” or aerial view).

Another thing (that is also already available in older versions as well) is that we have updated the tile style we use from MapBox.


I also started working on an idea I've been thinking about for a while, but that will not come in 3.34, so more on that later…

And one last thing, I also sneaked in a small little hidden feature for 3.34, let's see if anyone finds it… 😎

Wednesday, June 19, 2019

Midsomer Maps

Since it's been kindof a tradition for me to do some blogging around midsomer, I thought we might as well keep with that tradition this year as well… And there's been some nice news in latest beta release of Maps, 3.33.3.

First James Westman has implemented a new improved “Send to” dialog, as the old one had some problems. The way it interacted with the Clocks and Weather apps was a bit strange, adding the exact place (let's say a shop or a pub) as an entry in e.g. Weather, which is most likely not what the user intended. So the new dialog will offer to add the nearest city (or rather METAR weather station):

  


It also includes a summary with the name and address of the place, it's raw coordinates, and a link to the corresponding raw object in the OpenStreetMap database  as well as buttons to copy this information to the clipboard to be able to paste it elsewhere and also a button to initiate an e-mail message using the default e-mail client with this information, and the title of the place as the subject. Furhermore, along with the entries to add the nearby location to the Weather and Clocks apps, additionally if you have other apps capable of opening geo: URIs, they will appear at the end. In the case above I have JOSM (an OpenStreetMap editor written in Java, allowing nitty-gritty editing of OpenStreetMap data), so selecting that would open an area centered around this location in that app (however I also discovered a couple of bugs in JOSM's geo: handling, so you'll need their latest snapshot release for it to work).

Along with this, I started tinkering with allowing to enter the OpenStreetMap URL as a search term in Maps, so that you could open such URLs directly, without resorting to a browser. Ideally I would have liked if it was somehow possible to register as some kind of “partial” URL handler for http(s) restricted to certain patterns, but this is not currently possible with the mime support we have. So that would seems like a distant dream for now… Oh, and a somewhat crazy idea might be to attempt grocking some (subset) of Google Maps URLs.

The other big thing is that I completely rewrote the search engine, so now it uses either GraphHopper's API, or the search API of the Photon project. GraphHopper also uses Photon, but using their legacy API layer. The reason I implemented support for both is that GraphHopper was fine with using their service. The good thing is that quite a lot of the JSON parsing could be handle by a common module. And I also made it so that the search provider is auto-configured through the service file, so when/if GraphHopper switches to standard Photon, we can switch, and existing Maps clients will automagically use the new endpoint. Or if we want to change provider, that could also be done seamlessly this way.

What's more is that this finally gives us “search-as-you-type”, and this is something that calls for a video:





Thanks to the dynamic service file, it was also possible add attribution information that shows in the ”About“ box:


This is a pretty nice thing to do, I think.

And there was also time to fix a 4-odd year old bug, namely that in turn-by-turn routing our icons for roundabout navigation where always showing counter-clockwise variants. This has now been rectified to use clockwise variants for locations in drive-on-the-left countries/territories:


This might come in handy for this guy:


Not only those things, I also got around to fix an old, actually crashing bug when a user has more than some 250 contacts with addresses associated in their Evolution address book (such as when coupling with an enterprize Exchange server.

That's it for now, I guess… :-)