Hi Barend,

Barend Gehrels wrote:

Hi Adam,

[snipped]

Adam Wulkiewicz wrote On 28-11-2014 3:26:

I'm not sure if there is something like "great elliptic arc" or "great ellipse". AFAIU shortest paths on spheroid aren't fragments of spheres or ellipses.

http://en.wikipedia.org/wiki/Great_ellipse

According to wikipedia (http://en.wikipedia.org/wiki/Geodesics_on_an_ellipsoid), geodesics which supposed to be the shortest paths between points, in general aren't closed.

That is right.

Ok, so an intersection of a plane containing 2 endpoints and a spheroid's center is indeed an ellipse. Even though it's fragment is not the shortest path AFAIU it's mapping into a sphere is commonly used because it's a great simplification. Still AFAIU an approximation, but probably good enough.

(From wikipedia)
If the Earth is treated as a sphere, the geodesics are great circles (all of which are closed) and the problems reduce to ones in spherical trigonometry. However, Newton (1687) showed that the effect of the rotation of the Earth results in its resembling a slightly oblate ellipsoid and, in this case, the equator and the meridians are the only closed geodesics. Furthermore, the shortest path between two points on the equator does not necessarily run along the equator.

Though I'm not really sure if the side of this geodesic can be checked comparing azimuths calculated using Vincenty formula. And how precise it is.

In other words, it would be true if all intermediate points of a segment was going through the same coordinates. Are you sure that this is the case? I'm not. My test seems to prove that this is not true or at least that a method (Vincenty) which is known for giving precise results for an ellipsoid gives different results than SSF. Of course this is more visible for greater flattening.

OK. Vincenty is precise but very slow (maybe you have to compare performance too). At least distance calculations and comparisons I did in the past, comparing with Andoyer, Vincenty was much slower.

If we are going to use side-information on ellipsoids we have to have a reasonably fast algorithm, the side calculations are used very very often. The SSF is already slower of course than the cartesian calculation.

If the difference is very small, and the results of SSF-only are mutually consistent, and we don't use it together with distances (I don't think we do - but we use fractions which have to be comparable) it is not impossible that we can still use it (needs more research). It is just a different method to calculate the side, and if we can use that for turn-calculations and point-in-polygon calculations, it might give the correct results. Other libraries or packages first project to a Cartesian coordinate system, do the operation and convert back - you will also loose some information there too.
I don't state that it is possible, we just can research the possibilities.

Furthermore the formulas given (on that blog) and probably also what is implemented for SSF are about spheres. For the ellipsoid x,y,z have to be calculated differently, taking axis lengths into account. That might (most probably will) result in different results. It has to be implemented. That is the phase where we are.

Hmm, do you mean by this that we could place the plane with more precision on a spheroid, as perpendicular to the surface in 2 endpoints? Which maybe could result in a plane oriented differently? But still use the SSF for calculation, so assuming that the segment is a fragment of a sphere?

That segment is a fragment of an ellipse, the cut of a plane with the spheroid is an ellipse.
But for the rest, sure, I mean that. We should do that.

So the difference would be the way how the orientation of the plane was calculated. It might as well give the same result because he definition of geographical coordinates is the same as for spherical - latitude is an arc between XY plane and a line perpendicular to the surface. So it's possible that this plane would have the same orientation. But it's definietly something worth checking.

But the xyz coordinates are different so the plane will be different.

Ok, AFAIU our discussion is about various mappings of the coordinates into a sphere. Because at this point, when we had the sphere we'd be able to handle the arc as a part of a great circle, so e.g. use SSF. In the case of side calculation the radius of a sphere is not important, only angles. Furthermore the longitude would be the same on a sphere so only the latitude matters. On the wikipedia page mentioned by you above there are 3 methods of mapping mentioned.

When you mentioned about a great ellipse I assumed that you'd like to use the 2nd one θ (theta), so to use latitude being an angle corresponding to the line between the center and the point (the green one on the picture above). So to project an elliptic arc radially into the surface of a sphere. Did I missunderstood you?

Anyway, I wanted to preserve the latitude Φ (fi) (use plane perpendicular to the surface, the red one) which is the same as the 3rd mapping (the blue one). I felt that the arc would be closer to the shortest one. The difference is that they're using radius = a and I wanted to calculate it from the endpoints to better represent the original arc, but in the case of side calculation on a sphere the radius is not important.

So AFAIU the last mapping preserves lon and lat, so it's basically the same as the original SSF. And since it states (on the wiki) that:

The last method gives an easy way to generate a succession of way-points on the great ellipse connecting two known points A and B. Solve for the great circle between (\phi_1,\lambda_1) and (\phi_2,\lambda_2) and find the way-points on the great circle. These map into way-points on the corresponding great ellipse.

I think we don't need to do anything additional with the SSF. We could think about a totally different formula but we probably won't improve the SSF. Still I don't know if we need to improve it.

But, I feel that we could play with the distance calculation. I.e. use one of the mappings, calculate the position and the radius of a corresponding sphere and then use haversine. Actually I'm thinking about the 3rd mapping (or rather the red one). So we could take the coordinates, calculate their position in 3D, then calculate the 3D plane perpendicular to the surface. Then somehow calculate the mid point. Using those 3 points in 3D calculate the radius of a circle/sphere containing all 3 points and the position of the center. Then the angle between the endpoints in 3D. Then the length of the arc would be the distance. Assuming that the above could be done I'd say that it'd be a method corresponding to SSF. This would also be an approximation but most certainly faster than Vincenty distance. And most certainly good enough in some situations.

Do you have an idea how we could verify this?

No... or basically it is probably already clear now. The methods are different.

I came out with somethign like this. Please say if I'm missing something or if it's completly wrong.

A hypothesis:

If we gathered points of geodesic (coordinates where left side changes to right side between the segment's endpoints), form a path, smooth it e.g. by running bg::simplify(), and then calculate the length by suming all distances between the path's points, we should be able to check which curve is the shortest when measured on spheroid and sphere. This way we could check which one better represents the shortest path on both models.

It is known that the path over a great ellipse is not the shortest path. See in "Geometrical Geodesy: Using Information and Computer Technology" (google gives a preview, search for great elliptic arc", quote: "The great Elliptic arc is not the shortest possible connection between two points".

Ok, so AFAIU if we used it, it'd be an approximation. I'm not saying that a bad approximation. So ok, I think we agree.

Furthermore if a hypothesis about a different coordinates (shape) of geodesic on spheroid and sphere was true, when calculating the length of geographical geodesic on spheroid we should get smaller result than when calculating the length of spherical geodesic. And the other way around spherical geodesic should be shorter on sphere.

And finally if we also took a naiive cartesian-like segment between endpoints in the coordinates space, e.g. the result of a cartesian side_by_triangle. The length of this segment "projected" on the surface of a sphere or spheroid should be different than the "true" distance between endpoints calculated using haversine or vincenty. What is more, it should be longer than the spherical segment on a sphere and geographical segment on a spheroid. It's because the shortest path e.g. on a sphere is defined by a great circle so any other path should be longer.

I've implemented this in test-geoside and this is what I've got:

All results are for a segment (-31 -31, 31 31).
distance is the result of a bg::distance(s1, s2, strategy)
length is the sum of distances between points of a geodesic/curve of left/right edge points.
length geo is the length of a curve of side change according to azimuths calculated with Vincenty formula
length sph is the length of a curve of side change according to SSF
length car is the length of a curve of side change according to side_by_triangle (also verified algebraically)
A letter in brackets is a strategy used to calculate distances
(V) - vincenty, (A) - andoyer : so assuming that points are on spheroid
(H) - haversine mean radius = (2a+b)/3, (M) - haversine max radius = a : assuming that points are on sphere

1. a=1 b=1 - unit sphere

distance (V) = 1.4910384559056726 distance (A) = 1.4910384559056726 distance (H) = 1.4910384559056729 distance (M) = 1.4910384559056729 length geo (V) = 1.4904379394565843 length sph (V) = 1.4904379394565843 length car (V) = 1.4897397736057592// the shortest? length geo (A) = 1.4904379394565841 length sph (A) = 1.4904379394565841 length car (A) = 1.4897397736057592 // ? length geo (H) = 1.4904379394565841 length sph (H) = 1.4904379394565841 length car (H) = 1.4897397736057592 // ? length geo (M) = 1.4904379394565841 length sph (M) = 1.4904379394565841 length car (M) = 1.4897397736057592 // ?
All geo and sph distances are the same, ok.

But the length of cartesian segment is the smallest. It's shorter than the distance calculated using directly. It's quite late so it's possible that I'm missing something. But it seems that either my assumptions are bad or the method is wrong or not precise enough.

But let's go forward...

2. a=1 b=1-1/300 - unit Earth

distance (V) = 1.4867431728537253 distance (A) = 1.4867328035365481 distance (H) = 1.4893817465102219 distance (M) = 1.4910384559056729 length geo (V) = 1.4856765746677782// smaller than sph, ok length sph (V) = 1.4861482692673844 length car (V) = 1.4854692836326653 // the shortest again? length geo (A) = 1.485666275142842 // also smaller than sph length sph (A) = 1.4861379754374746 length car (A) = 1.485459072084804 // ? length geo (H) = 1.4883117296448467// but this shouldn't be smaller than sph length sph (H) = 1.4887818973016325 length car (H) = 1.4880813951276908 // ? length geo (M) = 1.4899672488101912// also this shouldn't be smaller length sph (M) = 1.4904379394565841 length car (M) = 1.4897366580811147 // ?
So the length of geographical segment seems to be smaller no matter how distances are calculated. This is rather impossible since the shortest path on a sphere is a great arc fragment. Ok, maybe the method's error is too big in this case. Maybe the flattening is too small to get meaningful results.

Cartesian the shortest again.

3. a=1 b=0.9 - unit Saturn

distance (V) = 1.3716008213860109 distance (A) = 1.3618688848319354// now the difference between A and V is greater distance (H) = 1.4413371740421503 distance (M) = 1.4910384559056729 length geo (V) = 1.3705358784007811 // smaller than sph, ok length sph (V) = 1.3711112408432529 length car (V) = 1.3709916809430027 // also this is greater than geo, but the closest to distance length geo (A) = 1.3608547786450773 // the smallest! length sph (A) = 1.3614390188832899 length car (A) = 1.3614090781917894 length geo (H) = 1.4403203633519746 // damn, this shouldn't be smaller than sph length sph (H) = 1.4407566748080314 length car (H) = 1.4400787694784105 // and this is the smallest now length geo (M) = 1.4899865827779046 length sph (M) = 1.4904379394565841 length car (M) = 1.4897366580811147 // the smallest
So again the geo segment seems to be smaller than sph in all cases, which is AFAIU wrong.

Cartesian still confusing. E.g. the smallest for Vincenty but the length is the closest to directly calculated distance.

3. a=1 b=0.75

distance (V) = 1.2321397094677933 distance (A) = 1.1681145282213292// note the difference between V and A distance (H) = 1.3667852512468668 distance (M) = 1.4910384559056729 length geo (V) = 1.2294812729423881 // the smallest length sph (V) = 1.2316859225469647 length car (V) = 1.2319096796713431 // finally, the greatest but the closest to the distance length geo (A) = 1.165467037015419 // here ok too length sph (A) = 1.1679406380233488 length car (A) = 1.168887231887985 length geo (H) = 1.3649878832500875 // but this should be greater than sph length sph (H) = 1.3662347778352022 length car (H) = 1.3655723783015628 // and this too should be greater than sph length geo (M) = 1.4890776908182768 // same as above length sph (M) = 1.4904379394565841 length car (M) = 1.4897153217835226
Cartesian confusing again.

4. a=1 b=0.5

distance (V) = 1.1102958385138535 distance (A) = 0.8451906005369858// andoyer can be ignored I guess distance (H) = 1.2425320465880607 distance (M) = 1.4910384559056729 length geo (V) = 1.1064353530360909 // smaller than sph, but the furthest from distance length sph (V) = 1.1146694840023121 length car (V) = 1.1087899062397581 // this is the closest length geo (A) = 0.83893092464406038// smaller than sph length sph (A) = 0.84544333659011361 length car (A) = 0.84807843141588624 length geo (H) = 1.2432889622300805 // greater than sph, still may be a coincidence length sph (H) = 1.2420316162138203 length car (H) = 1.241438095270917 // the smallest length geo (M) = 1.4919467546760965 // greater than sph length sph (M) = 1.4904379394565841 length car (M) = 1.4897257143251006
Similar story, if the length is the smallest it's the furthest from the distance calculated directly.

So I'm guessing that the length and the distance depends mainly on the algorithm used for distance calculation. The variance in the result of calculation using various distance strategies seems to be so big that the possible error based on the method (gathering pixels + simplification) influences the result a lot more than the shape of a path. Hence, we wouldn't check anything like this.

Or do you have some ideas what may be happening?

Not yet.

The assumption about the length of geodesics should at least be good for sphere.
Any help would be welcome.

Vincenty distance is always shorter than haversine which I guess is good.
Should Vincenty give good results for different flattening than Earth's?
Should Andoyer give good results only for Earth?

Might be, it is AFAIK designed for Earth...

It's less precise approximation but it uses flattening and radius but still gives worse results than haversine. Is this a bug or a limitation to flattenings near Earth's?

I also noticed that the greater the flattening, the longer it takes to use Vincenty formula. Maybe we should calculate the threshold based on the flattening?

Furthermore at flattening 0.8 the formula falls into an infinite loop in which lambda and previous_lambda (also sigma) swapps between 2 values all of the time but the difference is greater than the threshold. So we could add a test for this effect. So add some test for local minimum. And maybe some iterations counter just in case. If you're curious, it's for (in radians):
lon1 = -0.54105206811824214lat1 = -0.54105206811824214lon2 = 0.89709923552509452lat2 = -1.0646508437165410a = 1.0000000000000000b = 0.20000000000000001

Thanks a lot. This requires more study, will come back later.

Ok, for now I don't have any other ideas ;)

Regards,
Adam