Automatische Erzeugung von POI-Karten aus Offenen Daten
de enDie 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.
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:
- Birsfelderstrasse 6, 4132 Muttenz, Schweiz
- 4132 Muttenz, Schweiz
- 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.
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:
- 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.
- Wenn es immer noch Beschriftungen gibt, die nicht überlappungsfrei platziert werden können, werden diese dort platziert, wo die Überlappung minimal ist.
- 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.
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.