... the user friendly GPS tool


Thread Rating:
  • 1 Vote(s) - 5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Anzeige-Problem (Herunterskalierung)
#1
Hallo Christian,

ich hab mal wieder einen neuen Problemfall entdeckt, bei dem die Herunterskalierung/Ausschnittsauswahl der Kurve für die Anzeige nicht richtig funktioniert.

Beim small.gpx für einen Tag funktioniert es (fast) noch richtig. Bei mehreren Tagen in einem Gpx funktioniert es dann nicht mehr (big.gpx).

Auf den angehängten Screens sieht man etwa gleiche Ausschnitte. Hier sieht man bei Small2.png auch, dass unten rechts eine Linie beginnt, die eigentlich aus dem Off kommen müsste. Deshalb zuvor das "fast".

Die gpx-Files selbst habe ich dir per Mail geschickt. Die Files wollte das Forum nicht akzeptieren (zu groß). Vielleicht findest Du damit ja was.

Was ich sagen kann ist, dass der Fehler schon immer drin war. Ich hab das Ganze bis auf die V2.5 vor einem Jahr zurückverfolgt, als wir schon mal solche Effekte gesucht hatten. Vor der damaligen Optimierung hat es komplett nicht funktioniert und danach war dieser Effekt schon drin.

Gruß
Thomas


Attached Files
.zip   big1.zip (Size: 574.08 KB / Downloads: 703)
.zip   small1.zip (Size: 694.12 KB / Downloads: 656)
.zip   big2.zip (Size: 389.31 KB / Downloads: 642)
.zip   small2.zip (Size: 401.39 KB / Downloads: 690)
Reply
#2
(05.09.2012, 20:45)lundefugl Wrote: Was ich sagen kann ist, dass der Fehler schon immer drin war. Ich hab das Ganze bis auf die V2.5 vor einem Jahr zurückverfolgt, als wir schon mal solche Effekte gesucht hatten. Vor der damaligen Optimierung hat es komplett nicht funktioniert und danach war dieser Effekt schon drin.

Hallo Thomas,

ich habe immer noch ein Archiv von Dir auf dem Desktop liegen, bin jetzt aber nicht dazu gekommen, zu analysieren, ob sich da etwas verbessern läßt.

596039 Positionen, 148 MByte Dateigröße ist auch nicht alltäglich. Das Laden erfordert mehr als 512 MByte Heap für die Java VM und dauert 2 Minuten. Alleine der Douglas-Peucker-Algorithmus rechnet 8 Sekunden, um die auf der Karte dargestellten Datenmenge bei Zoomlevel 3 auf 78 Positionen zu reduzieren, die dann ans Google Maps API übergeben werden.

Bei Zoomlevel 14 und der Hafeneinfahrt von Trelleborg kann man sehen, wie in 4 Stufen die Anzahl der Positionen radikal reduziert werden, damit Dir der Internet Explorer nicht abstürzt:

Code:
Sep 6, 2012 8:45:25 AM slash.navigation.converter.gui.mapview.BaseMapView filterPositionsWithoutCoordinates
INFO: Filtered positions without coordinates to reduce 596039 positions to 596039 in 41 milliseconds

Sep 6, 2012 8:45:25 AM slash.navigation.converter.gui.mapview.BaseMapView filterEveryNthPosition
INFO: Filtered every 11.920780th position to reduce 596039 positions to 50002 in 7 milliseconds

Sep 6, 2012 8:45:49 AM slash.navigation.converter.gui.mapview.BaseMapView filterSignificantPositions
INFO: Filtered significant positions to reduce 50002 positions to 26904 in 23686 milliseconds

Sep 6, 2012 8:46:17 AM slash.navigation.converter.gui.mapview.BaseMapView filterVisiblePositions
INFO: Filtered visible positions to reduce 26904 positions to 164 in 28121 milliseconds

Das könnte noch zu optimieren sein, damit besser passende 164 Positionen herauskommen oder vielleicht 200. Im Moment ist mir das nicht wichtig genug, um meine Zeit drauf zu verwenden. Magst Du vielleicht helfen?

BaseMapView#reducePositions ist ein guter Startpunkt:

Code:
private List<BaseNavigationPosition> reducePositions(List<BaseNavigationPosition> positions, int maximumPositionCount) {
        if (positions.size() < 2)
            return positions;

        if (positions.size() > 50000)
            positions = filterEveryNthPosition(positions, 50000);

        // determine significant positions for this zoom level
        positions = filterSignificantPositions(positions);

        // reduce the number of significant positions by a visibility heuristic
        if (positions.size() > maximumPositionCount) {
            positions = filterVisiblePositions(positions, 2.5, false);
            visibleNorthEast = northEast(positions);
            visibleSouthWest = southWest(positions);
            visibleNorthWest = asPosition(visibleSouthWest.getLongitude(), visibleNorthEast.getLatitude());
            visibleSouthEast = asPosition(visibleNorthEast.getLongitude(), visibleSouthWest.getLatitude());
        } else {
            visibleNorthEast = null;
            visibleSouthWest = null;
            visibleNorthWest = null;
            visibleSouthEast = null;
        }

        // reduce the number of visible positions by a JS-stability heuristic
        if (positions.size() > maximumPositionCount)
            positions = filterEveryNthPosition(positions, maximumPositionCount);

        return positions;
    }
--
Christian
Reply
#3
Hallo Christian,

(06.09.2012, 07:56)routeconverter Wrote: 596039 Positionen, 148 MByte Dateigröße ist auch nicht alltäglich. Das Laden erfordert mehr als 512 MByte Heap für die Java VM und dauert 2 Minuten.
Das geht bei mir zum Glück deutlich schneller. Du hast auch nur die "kleinen" Dateien bekommen. Die wirklich großen sind 600 MB groß. ;-)
Ich fahre den Routeconverter dashalb auch mit 10 GB und das System ist auch nicht das langsamste. ;-)

Hier gibts aber trotzdem gleich mal eine andere Frage, Wenn ich mich nicht irre, hälst du im Hintergrund noch das Original-GPX im Speicher, um nicht modifizierte Einträge wieder identisch speichern zu können.
Vieleicht könnte man hier eine versteckte Option machen, die das nicht macht. Beim konvertieren in ein anderes Format, können beim Speichern die Files auch auf Basis der reinen Daten aufgebaut werden. Der Speicherbedarf dürfte damit bestimmt etwas geringer werden.


(06.09.2012, 07:56)routeconverter Wrote: Magst Du vielleicht helfen?

BaseMapView#reducePositions ist ein guter Startpunkt:

Klar, ich kann mir das mal anschauen, wenn's mal wieder eine ruhige Minute gibt.
Ich hab gerade mal mein Git wiederbelebt und einen kurzen Blick darauf geworfen. Was ich mich frage ist, ob man den Downscale Algorithmus nicht aus BaseMapView in eine eigene Klasse auslagern kann, die dann über ein Interface in BaseMapView angesprochen wird. Natürlich müssten dann noch Infos über den eigentlichen Anzeigebereich mit übergeben werden.

Hintergrund ist folgende Überlegung. Man könnte so verschiedene Implementierungen intern parallel haben, die man nur über eine -D-Option oder eine versteckte Option umschaltet.
Man könnte so z.B. eine Variante machen, die "schnell, aber ungenau" ist. Und eine andere, die "langsam, aber genauer" ist. Hinzu käme, dass man so leichter das Ergebnis der Änderungen/Optimierungen vergleichen kann.

Bei der Optimierung der Punkte geistert mir im Kopf folgendes herum. Eigentlich müsste man ja alle Punkte wegwerfen können, die ausserhalb des Anzeigebereichs (etwas größer natürlich, damit man's nicht gleich beim Bewegen der Karte merkt) sind und wo auch der vorherige/nächste Punkt noch ausserhalb ist und die Linie nicht den Anzeigebereich schneidet.
Wenn man das machen würde (bzw. falls das schon jetzt gemacht wird), so müsste das Ausdünnen der verbleibenden Kurve beim großen und auch beim kleinen File von mir mit den identischen Punkten arbeiten und dann auch ein identisches Ergebnis liefern.

Das ist jetzt nur mal so eine Idee. Ich weiss natürlich nicht, ob das so einfach geht und wo die Fallen sind.
Ihr habt euch mit dem Thema sicher schon deutlich länger beschäftigt, als so ein dahergelaufener Entwickler wie ich.

Gruß
Thomas
Reply
#4
(06.09.2012, 19:20)lundefugl Wrote: Hier gibts aber trotzdem gleich mal eine andere Frage, Wenn ich mich nicht irre, hälst du im Hintergrund noch das Original-GPX im Speicher, um nicht modifizierte Einträge wieder identisch speichern zu können.

Fast. Nicht das GPX sondern die durch JAXB erzeugten Objekte, die das GPX repräsentieren, werden noch im Hauptspeicher gehalten.

(06.09.2012, 19:20)lundefugl Wrote: Vieleicht könnte man hier eine versteckte Option machen, die das nicht macht. Beim konvertieren in ein anderes Format, können beim Speichern die Files auch auf Basis der reinen Daten aufgebaut werden. Der Speicherbedarf dürfte damit bestimmt etwas geringer werden.

Ich habe keine Ahnung, wieviel Speicher das kostet. Das könntest Du mal messen. GpxPosition#origin ist das Attribut, das die JAXB-Daten referenziert.

(06.09.2012, 19:20)lundefugl Wrote: Ich hab gerade mal mein Git wiederbelebt und einen kurzen Blick darauf geworfen. Was ich mich frage ist, ob man den Downscale Algorithmus nicht aus BaseMapView in eine eigene Klasse auslagern kann, die dann über ein Interface in BaseMapView angesprochen wird. Natürlich müssten dann noch Infos über den eigentlichen Anzeigebereich mit übergeben werden.

Klar kann man das - aus meiner Sicht ist das der 2. Schritt vor dem ersten. Ersteinmal möchte ich eine bessere Implementierung des Algorithmus' sehen - gerne als Patch zum existierenden Code - bevor es sinnvoll ist, drüber nachzudenken, wie man den Code integriert. Er könnte z.B. auch die bestehende Implementierung ersetzen und man spart sich die Abstraktion.

(06.09.2012, 19:20)lundefugl Wrote: Bei der Optimierung der Punkte geistert mir im Kopf folgendes herum. Eigentlich müsste man ja alle Punkte wegwerfen können, die ausserhalb des Anzeigebereichs (etwas größer natürlich, damit man's nicht gleich beim Bewegen der Karte merkt) sind und wo auch der vorherige/nächste Punkt noch ausserhalb ist und die Linie nicht den Anzeigebereich schneidet.

Im einzelnen passiert schon derzeit folgendes:
  • Reduktion auf 50000 Positionen durch Auswahl jeder Anzahl/50000. Position, damit der nächste Schritt akzeptable Laufzeit hat
  • Reduktion durch Douglas Peucker mit empirisch ermitteltem Faktor für steigenden Detailgrad mit steigendem Zoomlevel
  • Reduktion auf das 2,5fach des sichtbaren Bereiches - erst jetzt, sonst schneidet der vorige Schritt Kanten zu Linien außerhalb zu früh weg
  • Reduktion auf heuristisch ermittelte Obergrenzen je nach Route, Track, Wegpunktliste bei denen der Internet Explorer noch stabil funktioniert durch Auswahl jeder Anzahl/Obergrenze. Positionen - damit erreichen den IE garantiert nicht mehr Positionen als er vertragen kann

(06.09.2012, 19:20)lundefugl Wrote: Ihr habt euch mit dem Thema sicher schon deutlich länger beschäftigt, als so ein dahergelaufener Entwickler wie ich.

Eigentlich schrauben EddiVonDerAlm und ich da seit der Integration der Karte bei RouteConverter 1.6 herum Shy
--
Christian
Reply
#5
Hallo Christain,

(07.09.2012, 07:44)routeconverter Wrote:
  • Reduktion auf 50000 Positionen durch Auswahl jeder Anzahl/50000. Position, damit der nächste Schritt akzeptable Laufzeit hat

vermutlich wird das schon das Problem sein. Da bleiben bei mir in dem Anzeigebereich wahrscheinlich zu wenige Positionen übrig. Ich denke, dass ich da mal ansetzen werde.


Gruß
Thomas
Reply
#6
(06.09.2012, 19:20)lundefugl Wrote: Hier gibts aber trotzdem gleich mal eine andere Frage, Wenn ich mich nicht irre, hälst du im Hintergrund noch das Original-GPX im Speicher, um nicht modifizierte Einträge wieder identisch speichern zu können.
Vieleicht könnte man hier eine versteckte Option machen, die das nicht macht. Beim konvertieren in ein anderes Format, können beim Speichern die Files auch auf Basis der reinen Daten aufgebaut werden. Der Speicherbedarf dürfte damit bestimmt etwas geringer werden.

Die Undo/Redo Option dürfte bei so großen Positionslisten eine Menge Speicherplatz verbrauchen.

Vielleicht hilft Thomas ja schon ein Switch in den versteckten Optionen, der Undo/Redo abschaltet oder alternativ ein Parameter, der den für Undo/Redo maximal belegbaren Speicher definiert.
--
Matthias
Reply
#7
(07.09.2012, 14:04)kumo Wrote: Die Undo/Redo Option dürfte bei so großen Positionslisten eine Menge Speicherplatz verbrauchen.

Ich hatte die Version 2.7 mit JProfiler auf Speicherlöcher untersucht und zwei Bugs gefunden, bei denen die Undo/Redo-Funktionalität sowie das Datei/Erneut öffnen-Menü dafür sorgten, daß die Daten für die vorher geladene Datei im Speicher blieben.

Nach dem Beheben der Fehler wächst der benötigte Speicher für Undo nur um die für die Verwaltung benötigten Daten plus die geänderten Daten. Das sind z.B. beim Bearbeiten einer Position etwa 100-120 Bytes.

Falls Du/ihr anderes Verhalten beobachtet oder mißt, schickt mir bitte eine Beschreibung wie ich das nachstellen kann.
--
Christian
Reply
#8
Hallo,

das Undo dürfte bei mir kein Problem sein. Auf meiner Edit-Station ist genug Speicher vorhanden. Die Frage zum Speicherverbrauch kam eher daher, dass ich die Dateien auch weitergebe und die Anderen nicht so leistungsstarke Rechner haben. Dort wird der RC allerdings nur als Viewer benutzt.


Zum eigentlichen Grundproblem habe ich auch schon etwas herumexperimentiert.
Nach dem Herunterskalieren der Route bleiben noch viel zu viele Punkte übrig. Danach wird jeder n-te genommen, so dass es zum bekannten Ergebnis kommt.

1. Meine ich einen kleinen Fehler gefunden zu haben. In "filterEveryNthPosition" kamen immer 2 Positionen mehr heraus, als der Maximalwert war.

2. habe ich eine Optimierung vorgeschaltet (neue Funktion "filterVisiblePositionsExt"), die bei gro0en Listen alle Punkte wegwirft, die ausserhalb des 10fachen Anzeigebereiches sind. Für meine Anwendungsfälle hat es da schon eine deutliche Verbesserung gegeben.
Der Effekt, dass eine Linie vor dem Verlassen abgeschnitten wird, ist jedoch noch da. Da wird wohl irgendwo sich um einen Index verrechnet, was ich noch nicht gefunden habe.

Ich habe meine Änderungen (Experimentalcode zu 1. und 2.) bei mir im "downscale-refactor"-Branch eingecheckt, falls Du schon mal schauen willst.
[edit] Vergiss den Satz zuvor. Irgendwas geht doch noch nicht so richtig. Da muss ich noch etwas forschen, aber nicht heute abend mehr... ;-)[/edit]

Zum Schluss noch ein anderer Effekt. Wenn ich relativ tief hineingezoomt habe und dann in der Positionsliste klicke, so wird die Karte korrekt verschoben. Führt diese Verschiebung aus dem aktuellen Anzeigebereich, so erfolgt kein Retrigger für die Kurvenberechnung.
Wo man das einbauen müsste weiss ich nicht. Ich hab' bis jetzt nur "selectPositions" gefunden, wo ich das im Moment ohne Prüfung hart auslöse.


Gruß
Thomas
Reply
#9
Hallo Christian,

das Ganze hat mir nun doch keine richtige Ruhe gelassen, so dass ich jetzt noch etwass experimentiert habe.

Die Ursache für die fehlende Linie habe ich gefunden. Es ist der Algorithmus von "filterVisiblePositions". Wenn eine Position im inneren (wirklich sichtbaren Bereich) und die benachbarte Position ausserhalb des Filterbereiches liegt (bei langen Tunnlen bei mir der Fall), so kommt es zu dem Effekt.

Ich habe nun auch meinen Optimierungsalgorithmus abgeändert und zum laufen gebracht. Er liefert für meine Use-Case sensationelle Ergebnisse.
Knackpunkt war, was ich in der Nacht nicht gesehen habe, der significantPositionCache. Dieser hatte mir immer wieder dazwischen gefunkt. Nachdem ich den nun immer lösche funktionierts.

Mein Ansatz ist nun, zuerst die Punkte im Anzeigebereich zu filtern. Da die Kanten bei der Optimierung, wie du richtig geschrieben hattest, dann Probleme machen, bin ich hergegangen und habe daraus nicht eine Kurve gemacht, sondern sog. Segemente der wirklich zusammenhängenden Punkte. Diese rechne ich über den Douglas Peucker herunter und füge sie erst anschliessend wieder zu einer Positionsliste zusammen.

Was das bei kleineren Files bedeutet und wie die Performance aussieht kann ich mangels Wissen über die RC-typischen Use-Cases und mangels "langsamen" Testsystem nur schlecht beurteilen.
Bezüglich des Caches muss man sicher auch was machen. Mir ist nur nicht klar, was da genau gecached wird und wie man das nun anpassen muss.

Gruß
Thomas
Reply
#10
(08.09.2012, 07:58)lundefugl Wrote: Bezüglich des Caches muss man sicher auch was machen. Mir ist nur nicht klar, was da genau gecached wird und wie man das nun anpassen muss.

Der significantPositionCache cacht für einen Zoomlevel, welche Positionen der Douglas-Peucker-Algorithmus als signifikant erreichnet habt. Der Cache wird gelöscht, wenn eine Position bewegt wird oder sich ändert oder die gesamte Positionsliste sich ändert.

Ein Löschen des Caches "bezahle" ich auf meinem System mit 25 Sekunden Wartezeit für Deine Dateien mit 600000 Positionen. Wie lange dauern die Schritte unten bei Dir und auf wieviele Positionen reduziert der von Dir optimierte Algorithmus pro Schritt?

Quote:Bei Zoomlevel 14 und der Hafeneinfahrt von Trelleborg kann man sehen, wie in 4 Stufen die Anzahl der Positionen radikal reduziert werden, damit Dir der Internet Explorer nicht abstürzt:

Code:
Sep 6, 2012 8:45:25 AM slash.navigation.converter.gui.mapview.BaseMapView filterPositionsWithoutCoordinates
INFO: Filtered positions without coordinates to reduce 596039 positions to 596039 in 41 milliseconds

Sep 6, 2012 8:45:25 AM slash.navigation.converter.gui.mapview.BaseMapView filterEveryNthPosition
INFO: Filtered every 11.920780th position to reduce 596039 positions to 50002 in 7 milliseconds

Sep 6, 2012 8:45:49 AM slash.navigation.converter.gui.mapview.BaseMapView filterSignificantPositions
INFO: Filtered significant positions to reduce 50002 positions to 26904 in 23686 milliseconds

Sep 6, 2012 8:46:17 AM slash.navigation.converter.gui.mapview.BaseMapView filterVisiblePositions
INFO: Filtered visible positions to reduce 26904 positions to 164 in 28121 milliseconds
--
Christian
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)