Progress update

[adl1995]

@vissarion, @awulkiew - I will use this issue for providing updates on my progress. I believe this will make it convenient for you to provide feedback / review code.

During the community bonding period I

• Made a blog post describing my GSoC project and demonstrated the inaccuracy in current implementation of Boost Geometry for nearly antipodal points;
• Replicated the GenInverse method from GeographicLib to compute distance between two points. The code is present in adl1995/boost-geometry-proposal repository. This allowed me to get a bit familiar with the steps involved in the inverse problem;
• Started the implementation of direct geodesic problem (geometry/util/karney_direct.hpp) from Karney (2011) under the feature/geodesic_direct branch in this repository. I initially started implementing the inverse problem, but found that it was more complex and required additional steps, whereas, the direct problem is simpler and non-iterative. Since the inverse problem builds upon the direct problem, this implementation will allow me to better understand the mathematical details involved (such as series expansion). This is also how I proposed to do so in my project timeline;
• Got familiar with Maxima software and generated the series expansion for an integral (evaluate_series_A1) by making minor modifications in this script.

As I mentioned in #421, there is some preprocessing involved in the approach proposed by Karney. For now, I'm including these functions in geometry/util/math.hpp, as these can be reused in the inverse problem.

Currently, the code is available in karney_direct.hpp file, once this is complete, I will try and bundle this with Vincenty.

[vissarion]

@adl1995 Thanks for the update!

Note that there are formulas about series expansions / maxima scripts / Horner and Clenshaw summation in other places of the library, most notably here: area_formulas.hpp That could be useful to your project. Also feel free to propose a place for all of these utilities to avoid duplicates, geometry/util/math.hpp could be such a place or better geometry/util/series_expansions.hpp or similar.

[adl1995]

Update 19/05/2018:

• [utils] Add function for normalizing and rounding off an angle
• [formulas] Compute sin cos series using Clenshaw summation
• [util] Move series expansion functions to util/series_expansion.hpp

@vissarion Thanks for the suggestion. I looked through area_formulas.hpp, however, the series expansions I've currently used are different from the one present there. But, I will reuse them if I find a duplication.

Also, I have moved the series expansions from formulas/karney_direct.hpp to util/series_expansion.hpp.

[vissarion]

Indeed series for area are different but it is good to keep the same or similar format and eventually move everything related to series in the same folder. I just remembered that I have a prototype implementation for direct formula here. Feel free to use/modify/test it if you like.

[adl1995]

Update 25/05/2018:

Commits:

• [util] Evaluate coefficients for C1p using series expansion
• [formulas] Compute the latitude for second point following Karney's method
• [util] Add functions to evaluate coefficients for A3 and C3 using series expansion
• [formulas] Compute the longitude for second point using the longitudinal difference
• [util] Evaluate series and coefficients for A2 and C2 using series expansion
• [formulas] Compute the reduced length and geodesic scale using Karney's direct method
• [formulas] Make variable declarations constant

The implementation for the direct problem is complete. I'm now working on adding the test cases. The dataset I'm using is GeodTest associated with GeographicLib. It contains 500,000 entries for nearly antipodal points. However, I'm not sure where the current dataset in direct_cases.hpp is collected from. It contains three separate results for Thomas, Vincenty, and Karney's method. In this case, Thomas and Vincenty's method won't provide correct results, so should I only test this against Karney's method? @vissarion, @awulkiew - can you please comment on this?

Also, does Boost Geometry follow a convention for passing / returning data in degrees or in radians? I noticed in the test cases that returned data is converted into degrees before the actual comparison is performed. I'm not sure if user has the ability to specify this as part of the function call.

[vissarion]

The implementation for the direct problem is complete. I'm now working on adding the test cases. The dataset I'm using is GeodTest associated with GeographicLib. It contains 500,000 entries for nearly antipodal points. However, I'm not sure where the current dataset in direct_cases.hpp is collected from. It contains three separate results for Thomas, Vincenty, and Karney's method. In this case, Thomas and Vincenty's method won't provide correct results, so should I only test this against Karney's method? @vissarion, @awulkiew - can you please comment on this?

direct_cases.hpp contains data created by Adam. For the cases of nearly antipodal points there is no need to test against Thomas and Vincenty.

Also, does Boost Geometry follow a convention for passing / returning data in degrees or in radians? I noticed in the test cases that returned data is converted into degrees before the actual comparison is performed. I'm not sure if user has the ability to specify this as part of the function call.

As far as I understand, there is no issue here since formulas are internal i.e. users have access to algorithms. For the inverse case there is distance algorithm that takes a strategy as input and the strategy calls either Andoyer or Thomas or Vincenty formula. For the direct case a similar algorithm is needed.

[adl1995]

Update 01/06/2018:

Commits:

• [formulas][util] Add missing import and function return type
• [test] Add direct Karney's method to direct.cpp test cases
• [util] Modify function for evaluting C3x coefficient
• [util] Add functions for normalizing and evaluating polynomial
• [formulas] Fix direct geodesic method by performing normalization
• [test] Add nearly antipodal points dataset for direct geodesic problem
• [test] Add geodesic length to antipodal points dataset
• [test] Test Karney's method on antipodal points dataset
• [util] Update series expansion for C3x

Other work:

• Made a blog post on using variadic templates with lambda expressions.
• Opened up a pull request introducing Karney's direct method.

As far as I understand, there is no issue here since formulas are internal i.e. users have access to algorithms. For the inverse case there is distance algorithm that takes a strategy as input and the strategy calls either Andoyer or Thomas or Vincenty formula. For the direct case a similar algorithm is needed.

@vissarion Thanks for pointing that out! So, for each direct case i.e. Thomas, Vincenty, and Karney, I will introduce a strategy and add a coordinates algorithm(?) which will call the respective strategy. Which strategy should I select as default?

Also, is there a way to run CircleCI builds for pull requests in the main Boost Geometry repository? I wasn't able to resolve the issue related with running builds on this fork.

[vissarion]

@vissarion Thanks for pointing that out! So, for each direct case i.e. Thomas, Vincenty, and Karney, I will introduce a strategy and add a coordinates algorithm(?) which will call the respective strategy. Which strategy should I select as default?

To be consistent with the distance case (i.e. inverse formula) the default should be Andoyer. However, there is no Andoyer equivalent formula for the direct case. To closest choice could be Thomas with 1st order series (instead of 2nd order) see boostorg#431

For now I would suggest to focus on inverse problem for nearly antipodal points and when is done return back on this. I will try to remove some formulas that appear to be redundant in boostorg#431 and submit a new PL.

Also, is there a way to run CircleCI builds for pull requests in the main Boost Geometry repository? I wasn't able to resolve the issue related with running builds on this fork.

I think you cannot run on main BG repo. One workaround (a bit inconvenient) is to fork on your account and run CircleCI tests on that fork.

@awulkiew what do you think?

[awulkiew]

Are you talking about your PR: boostorg#486? It seems that the test was performed even though you used feature/... branch name (tests should be disabled for branches other than develop and master, see below). I don't know why it is the case, it should simply not exist. But anyway, it seems that the test is performed but the result is failure due to the lack of g++-4.9 package. I don't know why is that since in the main repository everything is fine. If you want to play with it to figure out why it is the case you can add some lines to circle.yml script printing some diagnostics like system version or some packages info etc.

Side note. Running tests on branches different than develop and master is disabled (see: https://github.com/boostorg/geometry/blob/develop/circle.yml#L10). It's because running all of the Boost.Geometry tests takes long time and we share CircleCI containers with all other Boost libraries so we could interfere with others. But also because the sript is sending info about code coverage manually to a single Coveralls account using $COVERALLS_REPO_TOKEN defined in CircleCI by me. This is why the tests for PRs are not performed. This could be changed, i.e. we should execute a lighter test for other branches and not send info about coverage.

[awulkiew]

I see on the PR page that you pushed more commits yet the tests were not performed. Why the test were performed before I don't know. Maybe it was some CircleCI anomaly.

[adl1995]

@awulkiew I actually ran that build manually from CircleCI dashboard. I've tried running tests on BoostGSoC18/geometry and adl1995/geometry before, but they both fail due to the lack of g++-4.9 package.

I will try tweaking the circle.yml script and see if I can find out what's causing the issue.

[adl1995]

@vissarion For the inverse problem, should I handle the case for meridional and equatorial points? Or, is this functionality already implemented in formulas/elliptic_arc_length.hpp?

[vissarion]

It would be better to implement a version of meridional and equatorial that is consistent with the new general method, if possible. Then we can test against the current implementation.

[adl1995]

Update 09/06/2018:

Commits (direct problem):

• [test] Update geodesic scale (M12) in GeographicLib dataset
• [test] Use series order 2 for Karney's direct method
• [util] Use Maxima generated function for computing C3x coefficients
• [util] Move sin_cos_series function to series_expansion.hpp
• [doc] Move Maxima scripts for geodesics to doc/other/maxima/geod.mac
• [test] Add comment providing dataset source and how it is parsed
• [util] Remove duplicated Maxima code from series_expansion.hpp
• [formulas] Use constant type variables for comparison
• [formulas] Move SeriesOrder to the end of template parameter list

Commits (inverse problem):

• [formulas] Add function for computing the length at the meridians
• [formulas] Arrange points in canonical form for inverse geodesic problem
• [util] Add function for returning NaN (not a number)
• [util] Add functions to normalize / sum two given values (angles)

[vissarion]

@adl1995 I have created the PR mentioned above with some direct formulas picked from an old PR. You can have a look here: boostorg#489

[adl1995]

Update 15/06/2018:

Commits (direct problem):

• [doc][util][formulas][test] Add copyright information in updated files
• [formulas][util] Improve code formatting to conform with guidelines
• [formulas] Use updated functions for normalization
• [util] Use existing normalize_spheroidal_coordinates class for normalizing an angle
• [formulas] Use template argument CT instead of double
• [formulas] Fix calculation of t for finding the geodesic scale (M12)
• [test] Calculate geodesic scale (M12) using high precision arithmetic

Commits (inverse problem):

• [formulas] Add function lambda12 to regulate bracketing range in Karney inverse
• [formulas] Perform normalization on starting guess if it passes the sanity check
• [formulas] Solve the astroid equation for inverse problem
• [formulas] Flip sign of cos_lam12
• [formulas] Find starting point for inverse problem (short lines)
• [formulas] Handle case for equatorial points in inverse problem