JavaScript-Tuning
Der Douglas-Peucker-Algorithmus glättet einen Kurvenverlauf durch Punktausdünnung. Lokale Minima und Maxima (im Höhenprofil Täler und Berge) bleiben dabei in Abhängigkeit von einem Schwellwert erhalten. Der Algorithmus lässt sich wie folgt nachvollziehen:
Zur Abstandsberechnung gibt es zwei Verfahren: das eine misst den orthogonalen Abstand, also den lotrecht zur Abszisse des Punktes zur gedachten Linie, die andere lotrecht zur Linie. Einfacher in der Berechnung ist das erste Verfahren — und auch ein bisschen ungenauer als das zweite, aber das ist unerheblich.
Implementierung in Perl
Im folgenden Code-Schnipsel enthält points
die zu vereinfachende
Liste von Punkten. Die Methode orthogonal_distance
liefert den orthogonalen Abstand eines Punktes zu der gedachten Linie zwischen den
zwei an die Funktion übergebenen Punkten.
package GPS::Track; # ... sub _douglas_peucker($$$) { my $self = shift; my ( $lo, $hi, $epsilon ) = @_; my $samples = $self->points; my $d_max = 0; my $idx = 0; for ( my $i = $lo + 1; $i < $hi - 1; ++$i ) { my $d = $samples->[$i]->orthogonal_distance($samples->[$lo], $samples->[$hi]); ($idx = $i) && ($d_max = $d) if $d > $d_max; } return $samples->[$lo], $samples->[$hi] if $d_max < $epsilon; my @res1 = $self->_douglas_peucker( $lo, $idx, $epsilon ); my @res2 = $self->_douglas_peucker( $idx, $hi, $epsilon ); return ( @res1[0..$#res1-1], @res2 ); } sub douglas_peucker($) { my $self = shift; my ( $epsilon ) = @_; my $samples = $self->points; return $self->_douglas_peucker(0, scalar @{$samples}-1, $epsilon); }
Letzte Änderung: $Date: 2009/07/31 12:07:53 $