Patch für automatische Wegpunktreduzierung

[routeconverter]

Ich habe die neue Version 1.22.3 kurz getestet und ich finde die aktuelle Umsetzung des Douglas Peucker Algorithmus nicht gut. Das Problem dabei ist, dass der Algo aktuell nicht auf Entfernungen Rücksicht nimmt und schon geglättete Routen (z.B. gpsbabel: -x position,distance=5m,all,time=900 -x simplify,error=2m) weiter stark vereinfacht. Diese werden dann in der Karte viel zu grob dargestellt.

Danke für den Hinweis. Daran habe ich gar nicht gedacht, da ich nicht mit durch gpsbabel geglätteten Routen arbeite. Der derzeitige Code

Code:

private static int[] douglasPeuckerSimplify(List<? extends BaseNavigationPosition> positions, int from, int to, double threshold) {
        // find the point with the maximum distance
        BaseNavigationPosition pointA = positions.get(from);
        BaseNavigationPosition pointB = positions.get(to);
        int maximumDistanceIndex = -1;
        double maximumDistance = 0.0;
        for (int i = from + 1; i < to; i++) {
            double d = Math.abs(positions.get(i).getOrthogonalDistance(pointA, pointB));
            if (d > maximumDistance) {
                maximumDistance = d;
                maximumDistanceIndex = i;
            }
        }

        // if max distance is greater than threshold, recursively simplify
        if ((maximumDistanceIndex != -1) && (maximumDistance > threshold)) {
            int[] res1 = douglasPeuckerSimplify(positions, from, maximumDistanceIndex, threshold);
            int[] res2 = douglasPeuckerSimplify(positions, maximumDistanceIndex, to, threshold);

            int[] result = new int[res1.length - 1 + res2.length];
            System.arraycopy(res1, 0, result, 0, res1.length - 1);
            System.arraycopy(res2, 0, result, res1.length - 1, res2.length);
            return result;
        } else
            return new int[]{from, to};
    }

entspricht m.E. dem von Wikipedia:

Code:

function DouglasPeucker(PunkteListe[], epsilon)
// Punkt mit dem maximalen Abstand ermitteln
dmax = 0
index = 0
for i = 2 to (length(PunkteListe) - 1)
  d = OrthogonalerAbstand(PunkteListe[i], Strecke(PunkteListe[1], PunkteListe[end]))
  if d > dmax
   index = i
   dmax = d
  end
end

// Abstand prüfen und ggf. in das Ergebnis eintragen
if dmax >= epsilon
  // rekursiver Aufruf
  rekErgebnis1[] = DouglasPeucker(PunkteListe[1...index], epsilon)
  rekErgebnis2[] = DouglasPeucker(PunkteListe[index...end], epsilon)
  
  // Bilden der Ergebnisliste
  ErgebnisListe[] = {rekErgebnis1[1...end-1] rekErgebnis2[1...end]}
else
  ErgebnisListe[] = {PunkteListe[1], PunkteListe[end]}
end

// Ergebnis zurückgeben
return ErgebnisListe[]
end

Was würdest Du vorschlagen?