Home
Dieses Dokument beschreibt einen Algorithmus, der das Speichern von Änderungen, die Wheelmap-Benutzer machen, verbessern soll. Verbessern bedeutet dabei, dass diese Änderungen eine kleinere geografische Größe haben.
Um dieses Dokument gut verstehen zu können, ist es vorteilhaft, wenn man die Wheelmap und OpenStreetMap(OSM) kennt und mit grundlegenden Informatik-Themen, wie beispielsweise Programmablaufpläne oder einer Programmiersprache, vertraut ist.
Hier gibt es ein Video über die Problematik.
Die Wheelmap ermöglicht es jedem, den wheelchair tag in OSM zu bearbeiten. Diese Bearbeitung wird als Änderungen in der OSM-Datenbank gespeichert. Das Speichern übernimmt das „Wheelmap-Backend“. Dazu fordert es von dem OSM-Server ein „Changeset“ an. Ein Changeset dient dem OSM-Server als Zusammenfassung von mehreren Änderung. Der OSM-Server speichert nur eine eingeschränkte Menge von Änderungen in einem Changeset. Zusätzlich verwendet der OSM-Server ein Changeset auch nur eine bestimmte Zeit lang. Sobald er ein Changeset nicht mehr verwenden kann, „schließt“ er dieses Changeset. Danach bekommt das Wheelmap-Backend ein neues Changeset, wenn es wieder eine Änderung speichern will.
Ein Merkmal eines Changesets ist seine geografische Größe. Diese ergibt sich aus den Änderungen, die ein Changeset enthält. Die geografische Größe eine Changesets schließt alle Änderungen ein. Wenn ein Changeset beispielsweise ein Änderung aus Berlin und eine Änderung aus Johannesburg (Südafrika) enthält, dann ist das Changeset in Nord-Süd-Richtung so lang, wie lange der Abstand zwischen Berlin und Johannesburg ist.
Besonders diese großen Changesets stören Mitglieder (Mapper) der OSM-Community (siehe https://github.com/sozialhelden/wheelmap/issues/29). Manche Mapper überwachen den geografischen Bereich, in dem sie bevorzugt arbeiten (mappen). Man kann Bereiche überwachen, indem man die Changesets inspiziert, die in diesem Bereich liegen (oder ihn schneiden). Durch das oben beschriebene Changeset mit Änderungen aus Berlin und Johannesburg, bekommt ein Mapper, der in Dresden seinen Bereich überwacht den Eindruck, dass in seinem Bereich eine Änderung stattgefundene hat, obwohl die Änderungen nur in Berlin und Johannesburg stattgefunden haben. Der Mapper aus Dresden sucht erst mal ein Zeit lang erfolglos die Änderung, bevor er merkt, dass sie von der Wheelmap kommen.
Diese großen Changeset entstehen, weil weder der OSM-Server noch das Wheelmap-Backend darauf achten, die Changesets klein zu halten. Das soll sich nun ändern, indem das Wheelmap-Backend Changesets so einsetzt, dass ihre geografische Größe klein bleibt. Dies soll funktionieren, indem das Wheelmap-Backend eine „Flächen-Wächter-Algorithmus“ implementiert, der in den folgenden Kapitel detailliert beschrieben ist.
Es soll ein Algorithmus gefunden werden, mit dem die Wheelmap kleinere Changesets erzeugt.
Es wurde eine Flächen-Wächter-Algorithmus implementiert und mit historischen Daten aus den Jahren 2010 und 2011 getestet. Dieser Algorithmus überwacht, dass die Kantenlänge eines Changesets unterhalb einer festgelegten Größe bleibt. Dadurch kann die geografische Größe der Changesets begrenzt werden. Dabei entstehen aber mehr Changesets, die zusätzlich weniger Änderungen enthalten.
Betrachtet werden nur die Changesets, die eine Fläche > 0 haben, da es bei diesem Optimierungs-Projekt darum, die Fläche der Changesets zu verringern. Changesets die eine Fläche <= 0 haben, sind entweder Changesets, die leer geblieben sind oder Changesets, die nur eine Änderung enthalten.
| original wheelchair_visitor (2010) | optimiert mit Kantenlänge 0.00146° (~ 2km) | optimiert mit Kantenlänge 0.0073° (~ 10km) | optimiert mit Kantenlänge 0.0365° (~ 50km) | original roald-linus (2011) | |
|---|---|---|---|---|---|
| Anzahl Changesets | 258 | 2750 | 2529 | 1819 | 43 |
| durchschnittliche Fläche der Changesets | 4.798549e+02 | 4.649216e-07 | 1.172182e-05 | 0.0001408914 | 1.202933e-04 |
| Verhältnis der Flächen (ca.) | 1000000000 | 1 | 25 | 300 | 260 |
| durchschnittliche Anzahl von Changes pro Changeset | 49.2 | 2.9 | 4.5 | 6.8 | 50.0 |
Folgender Programmablaufplan stellt den Algorithmus dar, der als "Flächen-Wächter" implementiert ist. Dabei wird auch immer auf die Zeile im Sourcecode verwiesen.
Zu einem „unbestimmten“ Zeitpunkt 
wird die Wheelmap gestartet.
Sobald eine User eine Änderung eines Wheelchair-Status macht - also die Wheelmap benutzt -, bekommt der Flächen-Wächter ein Nachricht 
[Code Z37]. Der Flächen-Wächter hat immer eine Liste mit Changesets, die er benutzen kann, um neue Änderungen zu speichern. Bevor er aber eines dieser Changesets erneut benutzt, muss er den OSM-Server "fragen", ob er dieses Changeset noch verwenden kann. Dazu fragt der Flächen-Wächter für alle Changesets nach, ob er diese noch verwendet darf 
[Code Z50]. Alle Changesets, die er nicht mehr verwenden darf, löscht er von seiner Liste 
[Code Z63] und [Code Z67].
Im nächsten Schritt 
prüft der Flächen-Wächter, ob die neue Änderung in eines der Changesets passt, die er noch zur Verfügung hat [Code Z53]. Passen bedeutet dabei, dass eine Changeset mit der neuen Änderung nur so groß wird, dass es die kleiner (oder gleich) als die erlaubte Größe bleibt [Code Z34].
Wenn es so ein Changeset gibt [Code Z61], wird es benutzt um die neue Änderung darin zu speichern 
, 
, [Code Z64ff]. Wenn es so ein Changeset nicht gibt [Code Z57], fordert der Flächen-Wächter vom OSM-Server ein neues Changeset an 
[Code Z58].
Bevor der Flächen-Wächter die neue Änderung in dem Changeset, das er nun ausgewählt hat, speichert und somit dem OSM-Server übergibt [Code Z64ff], speichert der Flächen-Wächter das Changeset mit seiner aktuellen Größe in seiner internen Liste von Changesets [Code Z68].
Es genügt nicht, dass die (geografische) Fläche eines Changesets klein bleibt. Dann könnte es nämlich Flächen geben, die entweder extrem breit oder extrem hoch sind. Diese Flächen würde wieder riesige Gebiete einschließen und so die Mapper weiterhin stören.
Damit ein Changeset klein bleibt, muss geprüft werden, wie groß die größte Kante der Changeset-Fläche wird, wenn man eine neue Änderung hinzufügen würde.
Folgende Grafik stellt obige Ergebnisse in einem Diagramm dar. Die Y-Achse stellt die durchschnittliche Anzahl von Änderungen pro Changeset dar- Die X-Achse stellt die Summe der Changesets dar. Die Quadrate stellen die durchschnittliche Fläche eines Changeset dar. Eine Ausnahme ist dabei der "Mapper wheelchair_visitor", weil dessen durchschnittliche Größe der Changesets 1000000000x so groß ist, wie das durchschnittliche Changeset des "Mappers area_guard 0.00146°".
