114 lines
4.3 KiB
Go
114 lines
4.3 KiB
Go
/*
|
||
Timelinize
|
||
Copyright (c) 2013 Matthew Holt
|
||
|
||
This program is free software: you can redistribute it and/or modify
|
||
it under the terms of the GNU Affero General Public License as published
|
||
by the Free Software Foundation, either version 3 of the License, or
|
||
(at your option) any later version.
|
||
|
||
This program is distributed in the hope that it will be useful,
|
||
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
GNU Affero General Public License for more details.
|
||
|
||
You should have received a copy of the GNU Affero General Public License
|
||
along with this program. If not, see <https://www.gnu.org/licenses/>.
|
||
*/
|
||
|
||
package googlelocation
|
||
|
||
import (
|
||
"math"
|
||
)
|
||
|
||
// A Go implementation of the Ramer-Douglas-Peucker Algorithm.
|
||
// Interactive demo and information: https://karthaus.nl/rdp/
|
||
//
|
||
// Borrowed from github.com/calvinfeng/rdp-path-simplification and
|
||
// heavily modified by me.
|
||
//
|
||
// As explained by Karthaus:
|
||
//
|
||
// "The Ramer-Douglas–Peucker algorithm is an algorithm for reducing the
|
||
// number of points in a curve that is approximated by a series of points.
|
||
// It does so by "thinking" of a line between the first and last point in
|
||
// a set of points that form the curve. It checks which point in between
|
||
// is farthest away from this line. If the point (and as follows, all other
|
||
// in-between points) is closer than a given distance 'epsilon', it removes
|
||
// all these in-between points. If on the other hand this 'outlier point'
|
||
// is farther away from our imaginary line than epsilon, the curve is split
|
||
// n two parts:
|
||
//
|
||
// 1. From the first point up to and including the outlier
|
||
// 2. The outlier and the remaining points.
|
||
//
|
||
// The function is recursively called on both resulting curves, and the two
|
||
// reduced forms of the curve are put back together."
|
||
//
|
||
// This implementation was modified to always preserve points that represent
|
||
// clusters, which I feel are too important to drop for the purposes of
|
||
// simplification. Clusters provide a valuable condensation of information.
|
||
func simplifyPath(points []*Location, ep float64) []*Location {
|
||
const dimensions = 2
|
||
if len(points) <= dimensions {
|
||
return points
|
||
}
|
||
|
||
l := line{points[0], points[len(points)-1]}
|
||
|
||
idx, maxDist := seekMostDistantPoint(l, points)
|
||
if maxDist >= ep || maxDist == -1 {
|
||
left := simplifyPath(points[:idx+1], ep)
|
||
right := simplifyPath(points[idx:], ep)
|
||
return append(left[:len(left)-1], right...)
|
||
}
|
||
|
||
// if the most distant point is still too close, then just return the two end points
|
||
return []*Location{points[0], points[len(points)-1]}
|
||
}
|
||
|
||
// seekMostDistancePoint returns the index of the most distant point from the line,
|
||
// using perpendicular distance calculation (may not be ideal on a circle...) -- this
|
||
// is modified to also return for all cluster points, as we don't want to lose those,
|
||
// in that case the maxDist returned will be -1.
|
||
func seekMostDistantPoint(l line, points []*Location) (idx int, maxDist float64) {
|
||
// The library I borrowed this from has an infinite recursion bug that I tracked
|
||
// down and patched, but they have not merged it even a year later:
|
||
// https://github.com/calvinfeng/rdp-path-simplification/pull/1/
|
||
// this for loop has the patch (start at 1, and use -1 in the while part,
|
||
// instead of starting at 0 and not having the -1)
|
||
for i := 1; i < len(points)-1; i++ {
|
||
// don't drop clusters; too important
|
||
if !points[i].Timespan.IsZero() || points[i].Significant {
|
||
return i, -1
|
||
}
|
||
if d := l.distanceToPoint(points[i]); d > maxDist {
|
||
maxDist = d
|
||
idx = i
|
||
}
|
||
}
|
||
return idx, maxDist
|
||
}
|
||
|
||
type line struct {
|
||
start, end *Location
|
||
}
|
||
|
||
// distanceToPoint returns the perpendicular distance of a point to the line.
|
||
// TODO: probably need to implement some great circle formula here for best results, since our coordinates are not cartesian...
|
||
func (l line) distanceToPoint(pt *Location) float64 {
|
||
a, b, c := l.coefficients()
|
||
return math.Abs(float64(a*pt.LatitudeE7+b*pt.LongitudeE7+c)) / math.Sqrt(float64(a*a+b*b))
|
||
}
|
||
|
||
// coefficients returns the three coefficients that define a line.
|
||
// A line can represent by the following equation.
|
||
//
|
||
// ax + by + c = 0
|
||
func (l line) coefficients() (a, b, c int64) {
|
||
a = l.start.LongitudeE7 - l.end.LongitudeE7
|
||
b = l.end.LatitudeE7 - l.start.LatitudeE7
|
||
c = l.start.LatitudeE7*l.end.LongitudeE7 - l.end.LatitudeE7*l.start.LongitudeE7
|
||
return a, b, c
|
||
}
|