// This module defines a PolylineEncoder class to encode
// polylines for use with Google Maps together with a few
// auxiliary functions. Documentation at
// http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/PolylineEncoder.html
//
// Google map reference including encoded polylines:
//   http://www.google.com/apis/maps/documentation/
//
// Details on the algorithm used here:
//   http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/
//

#ifndef GOOGLEPOLYLINE_H
#define GOOGLEPOLYLINE_H

#include <string>
#include <vector>
#include <cmath>
#include <limits>

struct Point {
	double x, y;
	Point() {}
	Point(double x, double y) : x(x), y(y) {}
	double lat() const { return x; }
	double lng() const { return y; }
	friend bool operator == (const Point &lhs, const Point &rhs) {
		return fabs(lhs.x - rhs.x) < 0.000005 && fabs(lhs.y - rhs.y) < 0.000005;
	}
	friend Point operator - (const Point &lhs, const Point &rhs) {
		return Point(lhs.x - rhs.x, lhs.y - rhs.y);
	}
	friend Point operator * (double lhs, const Point &rhs) {
		return Point(lhs * rhs.x, lhs * rhs.y);
	}
	friend double operator * (const Point &lhs, const Point &rhs) {
		return lhs.x * rhs.x + lhs.y * rhs.y;
	}
	double lengthSquared() const {
		return x * x + y * y;
	}
};
typedef std::vector<Point> PolyLine;

static const double undefined = std::numeric_limits<double>::infinity();

class PolylineEncoder {
	typedef std::pair<size_t, size_t> Range;

	int numLevels;
	double zoomFactor, verySmall;
	bool forceEndpoints;
	std::vector<double> zoomLevelBreaks;
public:
	// This function is very similar to Google's, but I added
	// some stuff to deal with the double slash issue.
	static std::string encodeNumber(unsigned int val);
	// This one is Google's verbatim.
	static std::string encodeSignedNumber(int val);

	// Constructor:
	//   PolylineEncoder polylineEncoder(numLevels,
	//     zoomFactor, verySmall, forceEndpoints);
	// where numLevels and zoomFactor indicate how many
	// different levels of magnification the polyline has
	// and the change in magnification between those levels,
	// verySmall indicates the length of a barely visible
	// object at the highest zoom level, forceEndpoints
	// indicates whether or not the  endpoints should be
	// visible at all zoom levels.  forceEndpoints is
	// optional with a default value of true.  Probably
	// should stay true regardless.
	PolylineEncoder(int numLevels = 18, double zoomFactor = 2, double verySmall = 0.00001, bool forceEndpoints = true);

	// The main function.  Essentially the Douglas-Peucker
	// algorithm, adapted for encoding. Rather than simply
	// eliminating points, we record their distance from the
	// segment which occurs at that recursive step.  These
	// distances are then easily converted to zoom levels.
	void dpEncode(const PolyLine &points, std::string &encodedPoints, std::string &encodedLevels);

	PolyLine simplifyPath(const PolyLine &points);

	// The decoding functions.
	PolyLine decodePoints(const std::string &encodedPoints);
	std::vector<unsigned int> decodeLevels(const std::string &encodedLevels);

private:
	// distance(p0, p1, p2) computes the distance between the point p0
	// and the segment [p1,p2].	This could probably be replaced with
	// something that is a bit more numerically stable.
	double distance(const Point &p0, const Point &p1, const Point &p2, double segLength);

	// The createEncodings function is very similar to Google's
	// http://www.google.com/apis/maps/documentation/polyline.js
	// The key difference is that not all points are encoded,
	// since some were eliminated by Douglas-Peucker.
	std::string createEncodings(const PolyLine &points, const std::vector<double> &dists);

	// This computes the appropriate zoom level of a point in terms of it's
	// distance from the relevant segment in the DP algorithm.	Could be done
	// in terms of a logarithm, but this approach makes it a bit easier to
	// ensure that the level is not too large.
	int computeLevel(double dd);

	// Now we can use the previous function to march down the list
	// of points and encode the levels.	Like createEncodings, we
	// ignore points whose distance (in dists) is undefined.
	std::string encodeLevels(const PolyLine &points, const std::vector<double> &dists, double absMaxDist);
};

#endif