# name
Automated Generation of POI Maps from Open Data

# nameMap.de
Automatische Erzeugung von POI-Karten aus Offenen Daten

# nameMap.en
Automated Generation of POI Maps from Open Data

# content
The website of the Chaos Computer Club features a map of Germany and its surrounding countries, where hackerspaces who consider themselves as part of the CCC are marked.

Up until now, this map (shown in Figure 1) had been created and updated manually in a time consuming process. Not only did this cause the map to be almost always outdated, but the process was also error-prone, with many hackerspaces being misplaced.

Figure 1: The old, manually created map of hackerspaces, last updated 2018.

The desire to automate the creation of this map had been voiced multiple times over the last few years, but all previous attempts have never been finished. Since I was one of the last persons asking for the map to be updated, I went ahead and started my own attempt at generating this map automatically.

My plan was to generate the map entirely from Open Data sources (apart from the actual hackerspace locations, where the "single source of truth" is a password-protected MediaWiki server). I also planned to generate the map background, rather than using a preexisting map, in order to avoid dealing with map projection issues.

Country Borders from Wikidata

In order to generate the map's background layer, the borders of Germany's federal states as well as surrounding countries were retrieved from Wikidata. Geographic regions in Wikidata are (or can be) equipped with the «geoshape» property, describing the outline of the region as a GeoJSON file.

For the federal states, the SPARQL query to retrieve these geoshape files is fairly simple:

SELECT DISTINCT ?item ?map WHERE {
  # ?item is instance of "Federal State of Germany"
  ?item wdt:P31 wd:Q1221156.
  # ?item has geoshape ?map
  ?item wdt:P3896 ?map.
}

Unfortunately, the same can't be said for the query to retrieve the geoshapes of all European countries, due to data being somewhat inconsistent:

When multiple properties of the same type are defined for a subject, they may carry different ranks. If one of these properties has a preferred rank, Wikidata will consider it «truthy» and not return any other properties of the same type.

Some countries had multiple geoshape properties, differing in resolution («zoom level»), with the most accurate geoshape being considered preferred. However, in order to properly render a map, all countries borders needed to have the same resolution and come from the same data source, so that the borders of two neighbouring countries would coincide. To achieve this, the query needed to be crafted so that even non-preferred geoshapes were returned.

The type (preferred «instance of» property) of some countries was "instance of country", while others were considered "instance of sovereign state". Both requirements needed to be included in the query.

While some countries are labeled as "part of Europe", some others are labeled as e.g. "part of Central Europe", which would then again be "part of Europe". The "part of Europe" constraint thus needed to be declared transitively.

Some countries were labeled neither "part of Europe" nor "on continent Europe" at all. However, coincidentally, all the countries where these relationships were not defined, were labeled as "part of the European Economic Area".

Finally, taking all these inconsistencies into consideration, the query to retrieve the borders of all European countries looked like this:

SELECT DISTINCT ?item ?map WHERE {
  # ?item is instance of country or sovereign state (see filter below)
  ?item wdt:P31 ?stateclass.
  # ?item is transitively (+) part of Europe (Contintent) or EEA (see filter below)
  ?item wdt:P361+ ?euroclass.
  # ?item has geoshape ?map (including all non-deprecated results)
  ?item p:P3896 ?st.  # ?item has geoshape statement ?st
  ?st ps:P3896 ?map;  # ?st has geoshape value ?map
  MINUS { ?st wikibase:rank wikibase:DeprecatedRank }  # Exclude results where the ?st rank is "deprecated"
  # ?stateclass is "Country" or "Sovereign State"
  FILTER (?stateclass = wd:Q6256 || ?stateclass = wd:Q3624078).
  # ?euroclass is "Europe (Continent)" or "European Economic Area"
  FILTER (?euroclass = wd:Q46 || ?euroclass = wd:Q8932).
}

This query returned all the countries required for the map. It also included some of these countries' overseas territories, but those were then filtered at a later stage by comparing them to the chosen viewport of the generated map.

Hackerspace Names and Addresses from Semantic MediaWiki

There is a CCC-internal MediaWiki instance which makes heavy use of the Semantic MediaWiki (SMW) extension. Among lots of other things, every hackerspace which considers itself part of CCC is listed there, along with their properties (e.g. street addresses).

SMW makes these properties machine-readable and queryable through different interfaces. For example, queries can be formulated directly within MediaWiki pages to automatically generate and update tables or lists based on these properties. Another interface is a collection of HTTP API endpoints, making SMW queryable from the outside.

Among these API endpoints, I ended up using the Semantic Search JSON API to retrieve a list of all hackerspaces along with their addresses, display names (there can be multiple) and website URLs:

GET /index.php?title=Spezial:Semantische_Suche&x=[[Category:Erfa-Kreise]][[Chaostreff-Active::wahr]]/?Chaostreff-City/?Chaostreff-Nickname/?Chaostreff-Physical-Address/...&format=json HTTP/1.1

{
    "printrequests": [...],
    "results": {
        "Chaos Computer Club Basel": {
            "printouts": {
                "Chaostreff-City": [
                    "Basel"
                ],
                "Chaostreff-Physical-Address": [
                    "Birsfelderstrasse"
                ],
                "Chaostreff-Physical-Housenumber": [
                    "6"
                ],
                "Chaostreff-Physical-Postcode": [
                    "4132"
                ],
                "Chaostreff-Physical-City": [
                    "Muttenz"
                ],
                "Chaostreff-Country": [
                    "Schweiz"
                ],
                "Public-Web": [
                    "https://www.ccc-basel.ch/"
                ],
                "Chaostreff-Longname": [
                    "Chaos Computer Club Basel"
                ],
                "Chaostreff-Nickname": [
                    "CCC Basel"
                ],
                "Chaostreff-Realname": [
                    "Chaos Computer Club Basel"
                ]
            },
            "fulltext": "Chaos Computer Club Basel",
            "fullurl": "https://doku.ccc.de/Chaos_Computer_Club_Basel",
            "namespace": 0,
            "exists": "1",
            "displaytitle": ""
        },
        ...
    },
    "serializer": "SMW\\Serializers\\QueryResultSerializer",
    "version": 2,
    "rows": 16
}

Of course the request params would be URL-encoded, in this example they are unencoded for better readability.

Now that we have the full list of hackerspaces, there is one more step required to display them on a map: Only the street addresses are entered in this wiki. In order to display them on a map, the addresses need to be geocoded, i.e. translated into coordinates. One such geocoding service is Nominatim. It uses OpenStreetMap to look up addresses and return WGS84 coordinates.

However, not all the street addresses returned by SMW are resolvable: Some hackerspaces encode additional information (e.g. the building level) in unstandardized, non-machine-readable formats. Others temporarily don't have a street address at all, e.g. because they are moving between places. In order to handle these special cases, less accurate addresses are queried, if a more accurate address fails to resolve. For example, in order to resolve the location of CCC Basel, the following address formats would be considered:

1. Birsfelderstrasse 6, 4132 Muttenz, Schweiz

2. 4132 Muttenz, Schweiz

3. Muttenz, Schweiz

Automatic Label Layouting

Finally, we have all the data to render the map. In a first step, both the country borders and the hackerspace locations are transformed from their polar 3D longitude/latitude representation to a 2D Cartesian projection suitable for display on a map.

However, the map should also display labels for some of the hackerspaces (so-called Erfas), and these labels should neither overlap with each other, nor should they obstruct other hackerspaces marked on the map. On the old map, these labels had been laid out manually to avoid overlap. For the new map, this too should be automated.

For each label to be placed, the text is rendered using the chosen font, and measured to compute its bounding box. From this bounding box, a discrete set of candidates for placement of this label is generated. Figure 2 depicts a set of bounding box candidates for CCC Berlin, placed around the marker of CCC Berlin.

Figure 2: Bounding boxes of all label position candidates around CCC Berlin.

Weights are assigned to each candidate based on multiple factors. The exact weights are magic numbers obtained through trial and error, but it mainly boils down to these factors:

Prefer candidates closer to their marker

Prefer candidates furthest away from other markers and (already placed) labels

Prefer candidates to the left and right over those at the top or bottom

Prefer candidates to the right over those to the left (unless close to the right-hand side of the map)

Penalize candidates overlapping with other elements with a huge weight

The actual label placement happens in three steps:

1. If a label has at least one candidate that doesn't overlap with any other label candidate or marker, this candidate is chosen. Since this step eliminates the other candidates of the label, it may render candidates of other labels usable again, if they were were obstructed before.

2. If there are still some unplaceable labels, they are placed where they cause the least overlap.

3. All weights are recomputed and already placed labels are optimized based on these weights. This will reduce possible overlap and spread labels further apart, making the map better readable.

This algorithm may not be perfect, but it seems to find a locally-optimized solution which at least to the human eye does not look too bad.

Conclusion

After all the labels are laid out, an SVG image is generated and written to a file. A CSS stylesheet is embedded in the SVG file so it can be used standalone, either for directly displaying it in a web browser, or for further processing. The markers and labels in the SVG image are amended with clickable links, leading the user to each hackerspace's website.

Additionally, a PNG image is generated, alongside with a HTML imagemap file (with the same links as in the SVG) so that the map can be used interactively in web browsers with limited or no SVG support.

Figure 3: The new, fully automatically created map, as it is now also available on ccc.de.

The new map (as seen in Figure 3) has now replaced the old one on ccc.de. The entire script to generate the map can be found in my Gitea repo. However, in order to actually use this script as-is, you need to know the Basic Auth credentials for the CCC MediaWiki instance. If you just want to check it out, you can use the example data in the repo, as described in the README.

# contentMap.de
Die Website des Chaos Computer Clubs enthält eine Karte von Deutschland und den umliegenden Ländern, auf der Hackerspaces verzeichnet sind, die sich als Teil des CCC betrachten.

Bisher wurde diese Karte (siehe Abbildung 1) händisch erzeugt und aktualisiert, was jeweils sehr zeitaufwändig war. Das hat nicht nur dazu geführt, dass die Karte oft nicht mehr aktuell war, sondern der Prozess war auch fehleranfällig, und die einzelnen Hackerspaces waren oft nicht ganz korrekt platziert.

Abbildung 1: Die alte, händisch erzeugte Karte der Hackerspaces.

Der Wunsch, die Erzeugung dieser Karte zu automatisieren, wurde in den letzten Jahren mehrfach geäussert, aber bisherige Ansätze wurden nie fertiggestellt. Da ich eine der letzten Personen war, die mal wieder darum gebeten hatten, die Karte zu aktualisiert, habe ich einfach kurzerhand selber versucht, die Erzeugung der Karte zu automatisieren.

Mein Plan war, die gesamte Karte aus offenen Daten zu erzeugen (ausgenommen von den Adressen der Hackerspaces, die aus einem passwortgeschützten MediaWiki kommen). Auch den Hintergrund der Karte wollte ich dynamisch erzeugen, anstatt eine bestehende Karte zu verwenden, um mich nicht mit abweichenden Kartenprojektionen herumschlagen zu müssen.

Ländergrenzen aus Wikidata

Um den Hintergrund der Karte zu erzeugen, wurden die Grenzverläufe der Bundesländer Deutschlands sowie der umliegenden Länder von Wikidata heruntergeladen. Geografische Regionen werden in Wikidata mit dem Attribut «geoshape» versehen (resp. können damit versehen werden), welches den Grenzverlauf der Region als GeoJSON-Datei beschreibt.

Die geoshape-Dateien für die Bundesländer können via SPARQL recht einfach abgerufen werden:

SELECT DISTINCT ?item ?map WHERE {
  # ?item ist vom Typ "Bundesland von Deutschland"
  ?item wdt:P31 wd:Q1221156.
  # ?item hat die geoshape ?map
  ?item wdt:P3896 ?map.
}

Leider ist es nicht mehr ganz so einfach, die Grenzverläufe aller europäischen Länder abzurufen, da die Daten nicht sonderlich konsistent sind:

Wenn ein Object in Wikidata mehrere Attribute vom gleichen Typ besitzt, können diesen unterschiedliche «Ränge» («ranks») zugewiesen werden. Falls eins dieser Attribute den Rang «bevorzugt» («preferred») trägt, wird es von Wikidata als «die Wahrheit» betrachtet, und andere Attribute vom gleichen Typ werden nicht zurückgegeben.

Einige Länder haben mehrere geoshapes, die sich in ihrer Auflösung («zoom level») unterschieden, wobei der am höchsten aufgelöste Grenzverlauf bevorzugt wird. Um allerdings aus den Grenzverläufen sinnvoll eine Karte zu erzeugen, sollten alle Verläufe die gleiche Auflösung haben und idealerweise aus der gleichen Quelle stammen, damit die Grenzen von benachbarten Ländern genau übereinander liegen. Um an diese zusätzlichen Auflösungsstufen zu kommen, muss die SPARQL-Abfrage angepasst werden, um auch nicht bevorzugte Attribute zurückzugeben.

Der Typ (bevorzugtes «instance of»-Attribute) ist bei manchen Ländern «country», bei anderen Ländern «sovereign state». Um alle Länder abzudecken, müssen beide Werte berücksichtigt werden.

Manche Länder sind als Teil von Europa («part of Europe») gekennzeichnet, während andere z.B. als Teil on Zentraleuropa («part of Central Europe») gekennzeichnet sind, welches wiederum «part of Europe» ist. Der «part of Europe»-Filter muss daher transitiv angegeben werden.

Manche Länder waren weder «part of Europe» noch «on continent Europe». Zufälligerweise waren aber alle solche Länder auch Teil des Europäischen Wirtschaftsraums («part of the European Economic Area»).

Wenn man diese Inkonsistenzen alle in Betracht zieht, kommt man auf folgende SPARQL-Query, um die Grenzverläufe aller Länder in Europa abzurufen:

SELECT DISTINCT ?item ?map WHERE {
  # ?item ist vom Typ «country» oder «sovereign state» (siehe FILTER weiter unten)
  ?item wdt:P31 ?stateclass.
  # ?item ist transitiv (+) Teil von «Europe (Contintent)» oder «EEA» (siehe FILTER weiter unten)
  ?item wdt:P361+ ?euroclass.
  # ?item hat die geoshape ?map (inklusive aller Resultate, die nicht den Rang «veraltet» («deprecated») haben)
  ?item p:P3896 ?st.  # ?item hat ein geoshape-Statement ?st
  ?st ps:P3896 ?map;  # Das statement ?st hat die geoshape ?map
  MINUS { ?st wikibase:rank wikibase:DeprecatedRank }  # Alle Resultate ignorieren, deren Rang «deprecated» ist
  # ?stateclass ist "Country" oder "Sovereign State"
  FILTER (?stateclass = wd:Q6256 || ?stateclass = wd:Q3624078).
  # ?euroclass ist "Europe (Continent)" oder "European Economic Area"
  FILTER (?euroclass = wd:Q46 || ?euroclass = wd:Q8932).
}

Mit dieser Query kommen alle Länder zusammen, die für die Karte benötigt werden. Zwar sind dort bei einigen Ländern noch die Übersee-Territorien mit dabei, diese werden aber später entfernt, wenn die Kartenränder festgelegt werden.

Hackerspace-Namen und -Adressen von Semantic MediaWiki

Das CCC-interne MediaWiki macht starken Gebrauch von der Erweiterung Semantic MediaWiki (SMW). Unter vielen anderen Daten ist dort jeder Hackerspace aufgeführt, der sich als Teil des CCC sieht, inklusive seiner Attribute (wie z.B. Postanschriften).

SMW macht diese Attribute maschinenlesbar und ermöglicht die Abfrage dieser Attribute über verschiedenen Schnittstellen. Zum Beispiel können so direkt in MediaWiki-Seiten Abfragen eingebunden werden, die automatisch Tabellen oder Listen aus diesen Daten generieren und aktualisieren. Zudem gibt es noch verschiedene HTTP-Schnittstellen, durch welche SMW auch durch die Aussenwelt abgefragt werden kann.

Um die Liste aller Hackerspaces inklusive ihrer Adressen, Namen (wovon es mehrere geben kann) und Website-URLs abzufragen, habe ich die Semantic Search JSON-API verwendet:

GET /index.php?title=Spezial:Semantische_Suche&x=[[Category:Erfa-Kreise]][[Chaostreff-Active::wahr]]/?Chaostreff-City/?Chaostreff-Nickname/?Chaostreff-Physical-Address/...&format=json HTTP/1.1

{
    "printrequests": [...],
    "results": {
        "Chaos Computer Club Basel": {
            "printouts": {
                "Chaostreff-City": [
                    "Basel"
                ],
                "Chaostreff-Physical-Address": [
                    "Birsfelderstrasse"
                ],
                "Chaostreff-Physical-Housenumber": [
                    "6"
                ],
                "Chaostreff-Physical-Postcode": [
                    "4132"
                ],
                "Chaostreff-Physical-City": [
                    "Muttenz"
                ],
                "Chaostreff-Country": [
                    "Schweiz"
                ],
                "Public-Web": [
                    "https://www.ccc-basel.ch/"
                ],
                "Chaostreff-Longname": [
                    "Chaos Computer Club Basel"
                ],
                "Chaostreff-Nickname": [
                    "CCC Basel"
                ],
                "Chaostreff-Realname": [
                    "Chaos Computer Club Basel"
                ]
            },
            "fulltext": "Chaos Computer Club Basel",
            "fullurl": "https://doku.ccc.de/Chaos_Computer_Club_Basel",
            "namespace": 0,
            "exists": "1",
            "displaytitle": ""
        },
        ...
    },
    "serializer": "SMW\\Serializers\\QueryResultSerializer",
    "version": 2,
    "rows": 16
}

(Üblicherweise würden die HTTP-Request-Parameter URL-encoded werden, in diesem Beispiel sind sie zwecks Lesbarkeit aber nicht encoded.)

Jetzt haben wir die gesamte Liste an Hackerspaces, aber bevor diese auf einer Karte dargestellt werden können, ist noch ein weiterer Schritt nötig: Das Wiki enthält nur Adressen. Um die Hackerspaces auf einer Karte darzustellen, müssen diese erst geocoded werden, d.h. in Geokoordinaten übersetzt werden. Ein solcher Geocoding-Dienst ist Nominatim. Nominatim verwendet OpenStreetMap, um Adressen nachzuschlagen und in WGS84-Koordinaten zu übersetzten.

Leider sind nicht alle der Adressen, die vom SMW zurückkommen, auflösbar: Manche Hackerspaces tragen in den Adress-Attributen zusätzliche Informationen (wie z.B. das Stockwerk) ein, die weder standardisiert, noch maschinenlesbar sind. Andere Spaces haben vorübergehend gar keine Adresse, z.B. weil sich gerade am umziehen sind. Um diese Fälle zu behandeln, werden zusätzliche, weniger genaue Adressen abgefragt, wenn eine genauere Adresse nicht auflösbar ist. So werden z.B. für den CCC Basel die folgenden Adressformate in Erwägung gezogen:

1. Birsfelderstrasse 6, 4132 Muttenz, Schweiz

2. 4132 Muttenz, Schweiz

3. Muttenz, Schweiz

Automatische Anordnung von Beschriftungen

Nun haben wir endlich alle Daten, um die Karte zu erzeugen. Zunächst werden sowohl die Grenzverläufe als auch die Hackerspace-Koordinaten von ihrer 3-dimensionalen polaren Darstellung aus Latitude und Longitude in eine 2-dimensionale kartesische Projektion umgerechnet, die für eine Kartendarstellung geeignet ist.

Einzelne der Hackerspaces (die sogenannten Erfas) sollen allerdings auch auf der Karte beschriftet werden. Diese Beschriftungen sollen weder mit den Markern auf der Karte, noch mit sich selbst überlappen. Auf der alten Karte wurde die Beschriftungen noch händisch angeordnet, um Überlappungen zu vermeiden.

Für jede Beschriftung, die auf der Karte platziert werden soll, wird zunächst der Text einmal mit der gewählten Schriftart gerendert und ausgemessen, um den Rahmen um den Text zu bestimmen. Aus diesem Rahmen wird ein diskretes Set an Platzierungs-Kandidaten erzeugt. Abbildung zeigt die Kandidaten, die für den CCC Berlin generiert wurden, und rund um dessen Marker platziert wurden.

Abbildung 2: Rahmen aller möglichen Beschriftungs-Positionen des CCC Berlin.

Jedem Kandidaten wird anhand von verschiedenen Faktoren eine Gewichtung zugeordnet. Die genaue Gewichtungen der einzelnen Faktoren sind magic numbers, die durch Ausprobieren zustandegekommen sind. Grundsätzlich gelten aber folgende Regeln:

Bevorzuge Kandidaten, die nahe an ihrem Marker stehen.

Bevorzuge Kandidaten, die weit weg von anderen Markern und anderen, bereits platzierten Kandidaten stehen.

Bevorzuge Kandidaten, die links oder rechts von ihrem Marker stehen, über solche, die oberhalb oder unterhalb ihres Markers stehen.

Bevorzuge Kandidaten, die rechts von ihrem Marker stehen über solche, die auf der linken Seite stehen. Nahe am rechten Rand der Karte wird diese Regel umgekehrt.

Bestrafe Kandidaten, die mit anderen Objekten überlappen, mit einem hohen Gewicht.

Die Platzierung der Beschriftungen findet in drei Schritten statt:

1. Wen es für eine Beschriftung mindestens einen Kandidaten gibt, der mit keinem anderen Objekt oder Kandidaten überlappt, wird dieser Kandidat als Platzierung festgelegt. Dieser Schritt eliminiert die anderen Kandidaten für diese Beschriftung, daher werden für die Beschriftung anderer Marker eventuell wieder weitere Kandidaten «frei», die vorher mit den eliminierten Kandidaten überlappt waren.

2. Wenn es immer noch Beschriftungen gibt, die nicht überlappungsfrei platziert werden können, werden diese dort platziert, wo die Überlappung minimal ist.

3. Alle Gewichte werden (jetzt, wo die allermeisten Kandidaten eliminiert wurden) neu berechnet, und die bereits platzierten Beschriftungen werden anhand der neuen Gewichte optimiert. Dadurch werden allfällige Überlappungen reduziert, und auch nicht überlappende Beschriftungen werden weiter voneinander weggeschoben, um die Lesbarkeit der Karte zu erhöhen.

Dieser Algorithmus ist nicht perfekt, aber er scheint lokale Optima finden zu können, die zumindest für das menschliche Auge akzeptabel aussehen.

Fazit

Nachdem alle Beschriftungen platziert wurden, wird eine SVG-Vektorgrafik erzeugt und in eine Datei geschrieben. In dem SVG wird ein CSS-Stylesheet eingebettet, damit es alleinstehend verwendet werden kann, z.B um direkt in einem Webbrowser dargestellt zu werden, oder um weiterverarbeitet werden zu können. Die Marker und Beschriftungen werden zusätzlich noch mit klickbaren Links ergänzt, die auf die Websites der einzelnen Hackerspaces weiterleiten.

Aus dem SVG wird auch noch ein PNG-Bild erzeugt, zusammen mit einer HTML Image Map (mit den gleichen Links wie im SVG), sodass die Karte auch in solchen Browsern interaktiv verwendet werden können, die nur reduziert oder gar nicht mit SVG-Dateien umgehen können.

Abbildung 3: Die neue, vollständig automatisch erzeugte Karte, wie sie nun auch auf ccc.de verfügbar ist.

Die so erzeugte neue Karte (siehe Abbildung 3) hat nun auch auf ccc.de die bisher händisch erzeugte Karte ersetzt. Das ganze Skript zur Generierung der Karte ist in meinem Gitea-Repo verfügbar. Um das Skript verwenden zu können, musst du allerdings die Basic Auth-Zugangsdaten für das CCC MediaWiki kennen. Wenn du das Skript nur kurz ausprobieren willst, kannst du aber auch auf die Beispieldaten im Repo zurückgreifen, wie im README beschrieben.

# contentMap.en
The website of the Chaos Computer Club features a map of Germany and its surrounding countries, where hackerspaces who consider themselves as part of the CCC are marked.

Up until now, this map (shown in Figure 1) had been created and updated manually in a time consuming process. Not only did this cause the map to be almost always outdated, but the process was also error-prone, with many hackerspaces being misplaced.

Figure 1: The old, manually created map of hackerspaces, last updated 2018.

The desire to automate the creation of this map had been voiced multiple times over the last few years, but all previous attempts have never been finished. Since I was one of the last persons asking for the map to be updated, I went ahead and started my own attempt at generating this map automatically.

My plan was to generate the map entirely from Open Data sources (apart from the actual hackerspace locations, where the "single source of truth" is a password-protected MediaWiki server). I also planned to generate the map background, rather than using a preexisting map, in order to avoid dealing with map projection issues.

Country Borders from Wikidata

In order to generate the map's background layer, the borders of Germany's federal states as well as surrounding countries were retrieved from Wikidata. Geographic regions in Wikidata are (or can be) equipped with the «geoshape» property, describing the outline of the region as a GeoJSON file.

For the federal states, the SPARQL query to retrieve these geoshape files is fairly simple:

SELECT DISTINCT ?item ?map WHERE {
  # ?item is instance of "Federal State of Germany"
  ?item wdt:P31 wd:Q1221156.
  # ?item has geoshape ?map
  ?item wdt:P3896 ?map.
}

Unfortunately, the same can't be said for the query to retrieve the geoshapes of all European countries, due to data being somewhat inconsistent:

When multiple properties of the same type are defined for a subject, they may carry different ranks. If one of these properties has a preferred rank, Wikidata will consider it «truthy» and not return any other properties of the same type.

Some countries had multiple geoshape properties, differing in resolution («zoom level»), with the most accurate geoshape being considered preferred. However, in order to properly render a map, all countries borders needed to have the same resolution and come from the same data source, so that the borders of two neighbouring countries would coincide. To achieve this, the query needed to be crafted so that even non-preferred geoshapes were returned.

The type (preferred «instance of» property) of some countries was "instance of country", while others were considered "instance of sovereign state". Both requirements needed to be included in the query.

While some countries are labeled as "part of Europe", some others are labeled as e.g. "part of Central Europe", which would then again be "part of Europe". The "part of Europe" constraint thus needed to be declared transitively.

Some countries were labeled neither "part of Europe" nor "on continent Europe" at all. However, coincidentally, all the countries where these relationships were not defined, were labeled as "part of the European Economic Area".

Finally, taking all these inconsistencies into consideration, the query to retrieve the borders of all European countries looked like this:

SELECT DISTINCT ?item ?map WHERE {
  # ?item is instance of country or sovereign state (see filter below)
  ?item wdt:P31 ?stateclass.
  # ?item is transitively (+) part of Europe (Contintent) or EEA (see filter below)
  ?item wdt:P361+ ?euroclass.
  # ?item has geoshape ?map (including all non-deprecated results)
  ?item p:P3896 ?st.  # ?item has geoshape statement ?st
  ?st ps:P3896 ?map;  # ?st has geoshape value ?map
  MINUS { ?st wikibase:rank wikibase:DeprecatedRank }  # Exclude results where the ?st rank is "deprecated"
  # ?stateclass is "Country" or "Sovereign State"
  FILTER (?stateclass = wd:Q6256 || ?stateclass = wd:Q3624078).
  # ?euroclass is "Europe (Continent)" or "European Economic Area"
  FILTER (?euroclass = wd:Q46 || ?euroclass = wd:Q8932).
}

This query returned all the countries required for the map. It also included some of these countries' overseas territories, but those were then filtered at a later stage by comparing them to the chosen viewport of the generated map.

Hackerspace Names and Addresses from Semantic MediaWiki

There is a CCC-internal MediaWiki instance which makes heavy use of the Semantic MediaWiki (SMW) extension. Among lots of other things, every hackerspace which considers itself part of CCC is listed there, along with their properties (e.g. street addresses).

SMW makes these properties machine-readable and queryable through different interfaces. For example, queries can be formulated directly within MediaWiki pages to automatically generate and update tables or lists based on these properties. Another interface is a collection of HTTP API endpoints, making SMW queryable from the outside.

Among these API endpoints, I ended up using the Semantic Search JSON API to retrieve a list of all hackerspaces along with their addresses, display names (there can be multiple) and website URLs:

GET /index.php?title=Spezial:Semantische_Suche&x=[[Category:Erfa-Kreise]][[Chaostreff-Active::wahr]]/?Chaostreff-City/?Chaostreff-Nickname/?Chaostreff-Physical-Address/...&format=json HTTP/1.1

{
    "printrequests": [...],
    "results": {
        "Chaos Computer Club Basel": {
            "printouts": {
                "Chaostreff-City": [
                    "Basel"
                ],
                "Chaostreff-Physical-Address": [
                    "Birsfelderstrasse"
                ],
                "Chaostreff-Physical-Housenumber": [
                    "6"
                ],
                "Chaostreff-Physical-Postcode": [
                    "4132"
                ],
                "Chaostreff-Physical-City": [
                    "Muttenz"
                ],
                "Chaostreff-Country": [
                    "Schweiz"
                ],
                "Public-Web": [
                    "https://www.ccc-basel.ch/"
                ],
                "Chaostreff-Longname": [
                    "Chaos Computer Club Basel"
                ],
                "Chaostreff-Nickname": [
                    "CCC Basel"
                ],
                "Chaostreff-Realname": [
                    "Chaos Computer Club Basel"
                ]
            },
            "fulltext": "Chaos Computer Club Basel",
            "fullurl": "https://doku.ccc.de/Chaos_Computer_Club_Basel",
            "namespace": 0,
            "exists": "1",
            "displaytitle": ""
        },
        ...
    },
    "serializer": "SMW\\Serializers\\QueryResultSerializer",
    "version": 2,
    "rows": 16
}

Of course the request params would be URL-encoded, in this example they are unencoded for better readability.

Now that we have the full list of hackerspaces, there is one more step required to display them on a map: Only the street addresses are entered in this wiki. In order to display them on a map, the addresses need to be geocoded, i.e. translated into coordinates. One such geocoding service is Nominatim. It uses OpenStreetMap to look up addresses and return WGS84 coordinates.

However, not all the street addresses returned by SMW are resolvable: Some hackerspaces encode additional information (e.g. the building level) in unstandardized, non-machine-readable formats. Others temporarily don't have a street address at all, e.g. because they are moving between places. In order to handle these special cases, less accurate addresses are queried, if a more accurate address fails to resolve. For example, in order to resolve the location of CCC Basel, the following address formats would be considered:

1. Birsfelderstrasse 6, 4132 Muttenz, Schweiz

2. 4132 Muttenz, Schweiz

3. Muttenz, Schweiz

Automatic Label Layouting

Finally, we have all the data to render the map. In a first step, both the country borders and the hackerspace locations are transformed from their polar 3D longitude/latitude representation to a 2D Cartesian projection suitable for display on a map.

However, the map should also display labels for some of the hackerspaces (so-called Erfas), and these labels should neither overlap with each other, nor should they obstruct other hackerspaces marked on the map. On the old map, these labels had been laid out manually to avoid overlap. For the new map, this too should be automated.

For each label to be placed, the text is rendered using the chosen font, and measured to compute its bounding box. From this bounding box, a discrete set of candidates for placement of this label is generated. Figure 2 depicts a set of bounding box candidates for CCC Berlin, placed around the marker of CCC Berlin.

Figure 2: Bounding boxes of all label position candidates around CCC Berlin.

Weights are assigned to each candidate based on multiple factors. The exact weights are magic numbers obtained through trial and error, but it mainly boils down to these factors:

Prefer candidates closer to their marker

Prefer candidates furthest away from other markers and (already placed) labels

Prefer candidates to the left and right over those at the top or bottom

Prefer candidates to the right over those to the left (unless close to the right-hand side of the map)

Penalize candidates overlapping with other elements with a huge weight

The actual label placement happens in three steps:

1. If a label has at least one candidate that doesn't overlap with any other label candidate or marker, this candidate is chosen. Since this step eliminates the other candidates of the label, it may render candidates of other labels usable again, if they were were obstructed before.

2. If there are still some unplaceable labels, they are placed where they cause the least overlap.

3. All weights are recomputed and already placed labels are optimized based on these weights. This will reduce possible overlap and spread labels further apart, making the map better readable.

This algorithm may not be perfect, but it seems to find a locally-optimized solution which at least to the human eye does not look too bad.

Conclusion

After all the labels are laid out, an SVG image is generated and written to a file. A CSS stylesheet is embedded in the SVG file so it can be used standalone, either for directly displaying it in a web browser, or for further processing. The markers and labels in the SVG image are amended with clickable links, leading the user to each hackerspace's website.

Additionally, a PNG image is generated, alongside with a HTML imagemap file (with the same links as in the SVG) so that the map can be used interactively in web browsers with limited or no SVG support.

Figure 3: The new, fully automatically created map, as it is now also available on ccc.de.

The new map (as seen in Figure 3) has now replaced the old one on ccc.de. The entire script to generate the map can be found in my Gitea repo. However, in order to actually use this script as-is, you need to know the Basic Auth credentials for the CCC MediaWiki instance. If you just want to check it out, you can use the example data in the repo, as described in the README.