Thanks @hadbn. What a fantastic contribution.

Doing some comparisons between the old and new test fixtures, have the "*-degrees" tests been broken all along? This current test output suggests the ellipses have never been the right size longitudinally, let alone the correct shape?

Also, and I need to apologise for not mentioning it sooner, there is another ellipse issue open - #1767 It has a solution suggested, and I'm wondering if that could be incorporated into your PR without much extra effort?

It would mean (I think) adding an optional accuracy config option.

Again, sorry for not mentioning this sooner. Didn't expect you to surge ahead with a PR right away! If that's not possible for you let me know and I will have a look myself.

To be honest, I didn't spend much time studying the old tests so I couldn't say what was functional and what wasn't. However, I did notice a lot of errors like the ones you point out, which motivated me to change how the tests are run. It might also be worth thinking about more "robust" tests. The “in”/“out” comparison tests only allow you to check that the geometry doesn't “change” according to the implementation, but they don't verify the accuracy of the geometry. It was with this in mind that I introduced the two tests of comparison with a circle and invariance by rotation. If you have any other idea of comparison feel free to tell me and I will add them.

I actually saw the other issue you are mentionning. As it's my first PR I wasn't sure if I could resolve two issues in a single PR, so I did not.
I will have a look at it and integrate the suggested modifications in my branch. I'll let you know.

In this case closing two issues in the same module will be fine. And happy to stick with the tests the way you're doing them.

@smallsaucepan here are the modifications.
All ellipses are now calculated so that points are equally distributed along the circumference.
I based my work on the issue you mentionned earlier. However I had to do some modifications because the proposed implementation led to problems when considering big ellipses. Quickly, this was due to the fact that when considering "big" ellipses the distance between two points is quite different from the arc length between those points. This led to a difference between Ramanujan's circumference and the one calculated using the discretization.

Moreover, this method gives prettier ellipses but I have to admit that it's quite expensive.

Are you happy with that ?

Thanks @hadbn. Discussing with the other maintainers about the performance impact.

@smallsaucepan as I was concerned about the cost of the new method, I updated the function. The parameter "accuracy" is now optionnal. When not used (or set to 0) the ellipse will be calculated using the historical method. When the parameter is used, the new method will be used.
It could also be relevant to use a threshold on the thickness of the ellipse, as the new method is usefull for thin ellipses but useless when considering "round" ellipses. However according to me the users of the function should decide the method they use by themselves, so I chose not to use the threshold in the function.

I am -of course- opened to every comment you (or other maintainers) could make.

Thanks @hadbn. Let's talk through our options.

Firstly, the other maintainers weren't too concerned if the new method is slower, as ellipse isn't really a work horse function that gets called thousands of times by other packages. Compare to distance or coordEach for example.

It's probably ok for us to admit the old algorithm doesn't provide satisfactory results for most cases, and we probably shouldn't use it any more or keep the code.

Your point about the new algorithm being of limited value the closer we get to a circle makes me wonder if we can base the default accuracy on the ratio between major and minor axis? Did some tests below:

L-R is old method (red), then accuracy 1, 2 and 3 in shades of green.

Major:minor ratio 2:1

Hard to distinguish much of a difference.

Major:minor ratio 5:1

Starting to see slight differences - third row of accuracy 1 points are noticeably lower than same points for accuracy 2.

Major:minor ratio 10:1

Differences for accuracy 1 are very noticeable. 2 and 3 still seem pretty similar.

What would you think about defaulting accuracy to:

ratio < 5 accuracy 1
ratio 5 - 10 accuracy 2
ration > 10 accuracy 3

and letting the user override it if they want to? No need to implement that yet. Let's discuss and agree on an approach first 👍

Thanks. Your examples are very relevant.

I'm happy with the thresholds you suggest for the ratio being >= 5, and for letting the user override the accuracy.
However we could split the first bound as :

ratio < 2 : accuracy 0 (which is ~half the cost of 1 accuracy)
ratio 2 - 5 : accuracy 1
and as you suggested for ratio > 5

Hmm. I tried plugging 0 into the latest PR code and got the blue ellipse below:

Do you have some uncommitted code that handles that case?

I don't have uncommitted code.
However, the dark blue ellipse has a high aspect ratio so this is not the configuration where accuracy=0 should be used.
I recommended to use it at low aspect ratio (<2) but it can be (<1.5)

We can hardly see the difference between acc = 0 and acc = 1 for an aspect ratio of 2.
With an aspect ratio of 1.333 there is -according to me- no need to have an accuracy of 1 or more and keeping accuracy=0 should be precise enough

Of course! Silly of me. I forgot that would be for more circular ellipses. Apologies.

I was playing around with a couple of other ideas. Notably, found this solution: https://stackoverflow.com/a/20257593/3606644

It seems to work better with those high aspect ratio ellipses, without having to do the expensive perimeter calculation first. Only problem is steps would have to be a multiple of four (it calculates a single quadrant). Which led me to wonder what happens if a user puts in a steps not divisible by four?

Turf has probably done this for forever, so I suspect if anyone was doing that they would have raised it as a bug.

Would you mind if I investigate that other approach a bit, and if it performs better than the perimeter method maybe we can look at merging that with your initial commits? Appreciate your patience working though this.

This other approach looks interesting. I'm looking forward to see how it will perform. Would you mind keeping me in touch ?

I'm not sure to understand what you meant by saying "Turf has probably done this for forever, so I suspect if anyone was doing that they would have raised it as a bug.". Is there an historical limitation to ensure that steps is a multible of 4 ?

@hadbn of course! Performance is about 5x slower than the old version, which is about 2x faster than accuracy 1. So, it seems promising.

I'm having trouble with the results I'm getting though. Would you mind taking a look if I share the implementation? That way we can both troubleshoot. For some reason my segment lengths aren't as uniform as the example, and the last segment is oversized. My results are the red graph.

I'm not sure to understand what you meant by saying "Turf has probably done this for forever ...

By that I mean Turf has always given the user exactly the number of steps they ask for - even it it's a weird number like 11 that leads to the blunted shape above. I'm presuming that if anyone was actually doing that they'd have probably raised it as a Turf bug, even though the function was giving them exactly what they were asking for.

I assume accuracy 0 to be 2x faster than accuracy 1, so accuracy 0 and your method should be equivalent (performance speaking).

Yes of course, please share the implementation !

I see your point when you assume that 11 steps are required. But what if users are curently asking for 101 steps for instance ? The distance between points would be smaller so it won't lead to the blunted shape (or less), and users would not have raised an issue. However, it's still not a multiple of 4.
If we were to adopt your method, maybe it would be a good practice to take the closest number to the one given for the number of steps, and which is a multiple of 4 ?

@smallsaucepan do you still need me to take a look at your implementation ? In such case, could you share it ?

Sorry @hadbn, I had to prioritise some other stuff. Yes, would be great if you could take a look!

I had the bright idea of pushing my work in progress to a branch of hadbn:fix-ellipse-harversine. Then if we get it to work you could just merge that work in progress branch into your fix-ellipse-harversine branch and the PR could proceed from there.

I don't have permission to do that though i.e. create a branch in your repo. Would you be comfortable to add me as a collaborator to https://github.com/hadbn/turf ?

Just sent you an invite. Thx.

Done! Thanks @hadbn. Have pushed a branch riemann-wip. Currently contains all three versions (for ease of benchmark comparisons), with ellipseRiemann being the one I was working on.

Appreciate your help. Let me know when you've had a chance to take a look and / or if you can see what the problem is!

@smallsaucepan, I just took a look at it, sorry for the delay. You can find the corrections on the branch you pushed on.

The method you took from stackoverflow is usefull to calculate the values of the parameter t where we should calculate the value of x and y so that points are evenly spread.
However this parameter is neither an angle or a distance and I have the feeling that you were using this parameter as if it was a distance.

Given a point corresponding to the parameter t, we know that this point is on the ellipse and its coordinates are x = a * cos(t) ; y = b * sin(t). We can then deduce the angle theta between the x axis and the line going from (0,0) to this point using theta = atan(y/x).

This angle is the one that can be used to calculate the local radius, and the destination.

It was not obvious at all, though ! Took me quite a while to figure it out :)
Thks for the help, I feel like we are converging towards something nice

That's great you were able to track it down @hadbn. Thank you. I've updated from the riemann-wip branch, and am getting the result below though? 7.1.0 is red, riemann-wip is green.

Is there still something I need to do?

Sorry I ran some tests and forgot to revert before pushing. I just fixed it (on Riemann-wip). Sorry about that.

Amazing work @hadbn! They look great 👍 Really pleased we spent the time getting this right, and appreciate your help.

Are you happy to merge riemann-wip back into your fix-ellipse-haversine branch, and then we can ping one of the other maintainers to review the PR?

Yes, seems good to me, I will do so. Do you confirm that I can delete the other implementations and only keep riemann for the pr ?

Definitely. Only had the others in there for ease of comparing performance, which I'll paste below for whoever reviews:

turf-ellipse - old x 274,986 ops/sec ±2.60% (89 runs sampled)
turf-ellipse - new acc 3 x 3,214 ops/sec ±1.47% (85 runs sampled)
turf-ellipse - riemann x 43,504 ops/sec ±2.06% (86 runs sampled)

old - quick but very poor aesthetically
new acc 3 - looks great but 100x slower
riemann - best compromise

Btw, with this code

// Divide steps by 4 for one quadrant
steps = Math.floor(steps / 4);

let's use Math.ceil instead to make sure the quality errs on the high side.