Parametrize on the metric space

[serenity4]

Originating from #98, it was discussed that we probably should parametrize the library according to a particular metric. Even if not all algorithms may work with arbitrary metrics, it would surely be nice to just have to set a global parameter or package option to have some algorithms work with non-Euclidean metrics.

Concretely, I think we need to:

1. implement custom metrics or reuse those from Distances.jl
2. expose a metric parameter
3. replace all occurrences of distance calculations to use the metric directly
4. find everything that breaks because of implicit assumptions on an Euclidean metric (e.g., that two parallel lines stay parallel ad vitam eternam) and deal with it

I am in favor of adding custom metrics with a custom type hierarchy since Distances.jl was made for a particular use of optimizing distance computations between iterators. A first PR could take care of that, and export them as part of the API.

2. can be as simple as const metric = Ref{MetricType}(Euclidean()). It will need extra thinking to make sure performance stays as good as before the parametrization.

But there is more. The introduction of non-Euclidean metrics gives rise to non-Euclidean geometry. From Wikipedia:

non-Euclidean geometry arises by either relaxing the metric requirement, or replacing the parallel postulate with an alternative

where the parallel postulate says that two parallel lines stay parallel (not true on, e.g., spherical geometry where they must intersect at some point).

For example, in spherical geometry, a line is a circle and a plane is a sphere.

Because of that, 4. is probably the tricky part: some algorithms may not work with weird metrics (I'm thinking of the line intersection algorithm, for example, and of any algorithm that assumes that the angles of a triangle sum up to 180° - which is for spherical geometry, a "nice" metric).

However, I think we can, for the moment, just ignore these non-Euclidean geometries. We'd need to clearly state what is supposed to work with custom metrics, and add support for what doesn't later. I am convinced that there is a clean and efficient way to deal with this, we'll just need some time to figure it out.

[juliohm]

I think we need to have a formal definition of non-Euclidean geometries stated in this issue before we can progress with implementations. I will try to find the time to re-read a book I have to share the definition here.

[serenity4]

I find Wikipedia to be a very good source of information regarding this kind of topics. They have an article about it, though to understand it properly it is required to know a lot more things which revolve around the notion of metrics, manifolds, curvature, and all that. I don't know of a book that summarizes it nicely, I personally go through Wikipedia pages.

[juliohm]

Now that we have full support for CoordRefSystems.jl, the manifold (sphere, ellipsoid) is explicit. This means that for most practical applications, we can trivially dispatch specific algorithms for non-Euclidean geometries.

Thanks for brainstorming this.

[juliohm]

We may actually need an extra type parameter to model the geodesic behavior. It is possible conceive a design where both Euclidean and Geodesic geometries co-exist.