Hoi zäme
Ich hatte kürzlich eine kleine Projektidee.
Wenn man einen neuen Ort kennenlernen möchte, wäre es ein netter Challenge, zu Fuss oder mit dem Fahrrad jeden begehbaren Weg in einem Gebiet (z.B. ein Dorf oder ein Stadtviertel) zu besuchen. Also 100% Highway/Footway-Coverage.
Idealerweise könnte man in so einer Applikation gleich GPX-Traces von einer beliebigen Tracking-App hochladen. Die Traces würden dann auf Strassen gemappt (snap trace to road), so dass die Coverage berechnet werden kann.
Gibt es schon etwas in der Art? Und wenn nicht, mit welchen Libraries könnte man sowas am besten bewerkstelligen?
Grüsse Danilo
Hoi Danilo
Das Problem erinnert mich an raumfüllende Kurven, sog. "FASS"-Kurven (https://de.wikipedia.org/wiki/Raumf%C3%BCllende_Kurve ).
Hilbert- bzw. Moore-Kurven sind so FASS-Kurven. Diese werden auch hier verwendet: https://inventingsituations.net/2015/11/28/space-filling-curves-in-simulated...
Ob und wie sich das auf beliebige (europäische) Netzwerke übertragen lässt, ist mir noch unklar.
:Stefan
Am 12. März 2017 um 01:19 schrieb Danilo mail@dbrgn.ch:
Hoi zäme
Ich hatte kürzlich eine kleine Projektidee.
Wenn man einen neuen Ort kennenlernen möchte, wäre es ein netter Challenge, zu Fuss oder mit dem Fahrrad jeden begehbaren Weg in einem Gebiet (z.B. ein Dorf oder ein Stadtviertel) zu besuchen. Also 100% Highway/Footway-Coverage.
Idealerweise könnte man in so einer Applikation gleich GPX-Traces von einer beliebigen Tracking-App hochladen. Die Traces würden dann auf Strassen gemappt (snap trace to road), so dass die Coverage berechnet werden kann.
Gibt es schon etwas in der Art? Und wenn nicht, mit welchen Libraries könnte man sowas am besten bewerkstelligen?
Grüsse Danilo _______________________________________________ talk-ch mailing list talk-ch@openstreetmap.ch http://lists.openstreetmap.ch/mailman/listinfo/talk-ch
Google StreetView hat ja ein ähnliches Problem ... :-) Ich habe dazu u.a. folgendes Paper gefunden: "Optimal Traversal Planning in Road Networks with Navigational Constraints" http://www.vincent-net.com/luc/papers/07acmgis_OptimalTraversal.pdf Sie vergleichen dort zwei Ansätze: einen Graph-Traversierungs-Algorithmus und einen modifizierten Travelling-Salesman
:Stefan.
Am 13. März 2017 um 00:32 schrieb Stefan Keller sfkeller@gmail.com:
Hoi Danilo
Das Problem erinnert mich an raumfüllende Kurven, sog. "FASS"-Kurven (https://de.wikipedia.org/wiki/Raumf%C3%BCllende_Kurve ).
Hilbert- bzw. Moore-Kurven sind so FASS-Kurven. Diese werden auch hier verwendet: https://inventingsituations.net/2015/11/28/space-filling-curves-in-simulated...
Ob und wie sich das auf beliebige (europäische) Netzwerke übertragen lässt, ist mir noch unklar.
:Stefan
Am 12. März 2017 um 01:19 schrieb Danilo mail@dbrgn.ch:
Hoi zäme
Ich hatte kürzlich eine kleine Projektidee.
Wenn man einen neuen Ort kennenlernen möchte, wäre es ein netter Challenge, zu Fuss oder mit dem Fahrrad jeden begehbaren Weg in einem Gebiet (z.B. ein Dorf oder ein Stadtviertel) zu besuchen. Also 100% Highway/Footway-Coverage.
Idealerweise könnte man in so einer Applikation gleich GPX-Traces von einer beliebigen Tracking-App hochladen. Die Traces würden dann auf Strassen gemappt (snap trace to road), so dass die Coverage berechnet werden kann.
Gibt es schon etwas in der Art? Und wenn nicht, mit welchen Libraries könnte man sowas am besten bewerkstelligen?
Grüsse Danilo _______________________________________________ talk-ch mailing list talk-ch@openstreetmap.ch http://lists.openstreetmap.ch/mailman/listinfo/talk-ch
Hallo,
wir hatten das mal am Passauer Stammtisch diskutiert. Zum einen um systematisch alle Hausnummern erfassen zu können aber auch für eine Route um mit Mapillary/OSC von allem mal ein Bild zu machen.
Die Lösung ist das Briefträgerproblem¹ (bzw Chinese postman problem) das man sehr einfach lösen kann. Es gibt zwar ein paar Einschränkungen bzw bei gewissen Nebenbedingungen wird es schnell mal NP-vollständig, aber das kann man umgehen indem man dann halt wenige Strecken doch zweimal fährt, man einen etwas längeren Weg in Kauf nimmt oder auch mal bereit ist gegen die Einbahnstraße zu fahren :-)
Implementierungen gibt's dazu einige, auch ein QGIS-Plugin afair. Bei uns blieb es aber bei einer Stammtischunterhaltung bzw. als Vorschlag für eine BA-Arbeit an der Uni Graz.
Gruß, Peda
Hoi zäme
Danke für die Antworten und Ideen! Darin ging es primär darum, ein Strassennetz möglichst effizient abzufahren, oder?
Darum ging es mir gar nicht, bei mir ist die Problemstellung viel einfacher: Mit einem Datensatz an GPS-Traces möchte ich wissen, wie viel Prozent eines Strassennetzes ich bereits besucht habe. Eine lineare Suche würde reichen, algorithmisch ist der Check selbst also nicht sonderlich schwierig.
Die Frage ist wie man das praktisch umsetzt. Welche Tools gibt es dafür? Wie kann ich GPS-Traces auf Strassen "snappen"? Und wie kann ich einfach prozentuale Überschneidung von zwei Pfaden (z.B. in PostGIS) berechnen?
Grüsse Danilo
Hoi Danilo
OSRM kann das zum Beispiel:
https://www.mapbox.com/blog/map-matching/
Hoffe das hilft
Grüsse Michael
On 27/03/17 18:13, Danilo wrote:
Hoi zäme
Danke für die Antworten und Ideen! Darin ging es primär darum, ein Strassennetz möglichst effizient abzufahren, oder?
Darum ging es mir gar nicht, bei mir ist die Problemstellung viel einfacher: Mit einem Datensatz an GPS-Traces möchte ich wissen, wie viel Prozent eines Strassennetzes ich bereits besucht habe. Eine lineare Suche würde reichen, algorithmisch ist der Check selbst also nicht sonderlich schwierig.
Die Frage ist wie man das praktisch umsetzt. Welche Tools gibt es dafür? Wie kann ich GPS-Traces auf Strassen "snappen"? Und wie kann ich einfach prozentuale Überschneidung von zwei Pfaden (z.B. in PostGIS) berechnen?
Grüsse Danilo _______________________________________________ talk-ch mailing list talk-ch@openstreetmap.ch http://lists.openstreetmap.ch/mailman/listinfo/talk-ch
Guter Hinweis "Map matching", Michael !
Nebst OSRM (C++) ist Map Matching auch im GraphHopper (Java) realisiert. Zu besagten Markow-Ketten (Achtung: Mathe!) finde ich u.a. diese Open Source Python-Implementationen: https://github.com/ustroetz/OSM-Map-Matcher, https://github.com/mapillary/map_matching .
Als "naiver" Ansatz mit PostGIS mit nur teilweiser Berücksichtigung der GPX-Zeitabfolge könnte folgendes dienen: ST_SharedPaths und/oder ST_HausdorffDistance (siehe [1]) oder der "Trick" mit ST_Line_Locate_Point [2][3].
Bei letzterem Ansatz ist es ev. nötig, die OSM-Daten vorzuverarbeiten, d.h. u.a. die Strassen zu extrahieren, in einzelne Kanten aufzuteilen und Abbiege-Restriktionen (wo vorhanden) zu berücksichtigen.
Bin gespannt, welche Lösung du findest.
LG, Stefan
[1] https://lists.osgeo.org/pipermail/postgis-users/2012-January/031980.html [2] https://lists.osgeo.org/pipermail/postgis-users/2008-July/020613.html (http://blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html ), [3] http://gis.stackexchange.com/questions/143909/map-matching-gps-points-to-the...
Am 27. März 2017 um 19:56 schrieb michael spreng mailinglist@osm.datendelphin.net:
Hoi Danilo
OSRM kann das zum Beispiel:
https://www.mapbox.com/blog/map-matching/
Hoffe das hilft
Grüsse Michael
On 27/03/17 18:13, Danilo wrote:
Hoi zäme
Danke für die Antworten und Ideen! Darin ging es primär darum, ein Strassennetz möglichst effizient abzufahren, oder?
Darum ging es mir gar nicht, bei mir ist die Problemstellung viel einfacher: Mit einem Datensatz an GPS-Traces möchte ich wissen, wie viel Prozent eines Strassennetzes ich bereits besucht habe. Eine lineare Suche würde reichen, algorithmisch ist der Check selbst also nicht sonderlich schwierig.
Die Frage ist wie man das praktisch umsetzt. Welche Tools gibt es dafür? Wie kann ich GPS-Traces auf Strassen "snappen"? Und wie kann ich einfach prozentuale Überschneidung von zwei Pfaden (z.B. in PostGIS) berechnen?
Grüsse Danilo _______________________________________________ talk-ch mailing list talk-ch@openstreetmap.ch http://lists.openstreetmap.ch/mailman/listinfo/talk-ch
talk-ch mailing list talk-ch@openstreetmap.ch http://lists.openstreetmap.ch/mailman/listinfo/talk-ch
-
Danilo -
michael spreng -
Peter Barth -
Stefan Keller