Proposal
- Name: Ruoyun Jing
- College/University: Northwest University
- Course/Major: Software Engineering
- Degree Program: Bachelor of Engineering
- Email: jingry0321@gmail.com
- Homepage: https://github.com/Rylynnn
- Availability: I will spend at least 40 hours a week for the work. I do not have any conflicts during the official coding periods, because my semester course will ended by the end of April. If time permits, I will try to make efforts doing more work beyond my proposal. Furthermore,I am willing to keep contributing to Boost and Boost.Geometry after this GSoC period.
In some algorithms there is the need to compare two distances of two point pairs. Especially, computing distances on ellipsoid in Boost.Geometry used compare_distance () function, which is a predicate that is it returns three possible values (larger than, less than, equal). To calculate the length of geodesic segments, Boost.Geometry used vincenty_direct.hpp and vincenty_inverse.hpp with Vincenty formula to calculate destination point and distance between points. Although Newton's method has been successfully used to give rapid convergence for this formula, the time complexity of this algorithm is hard to estimate.
To reduce the time complexity, this project will try to use the following approaches:
- Condition Division: Compute the Euclidean distances first, if the length of two segments are very close, defined not “far enough” means “very close”, then fall back to expensive geographic distance calculation, otherwise return the result by comparing those numbers obtained by less expensive cartesian computation.
- Calculation with The Area of a Sector of an Ellipse: Get cross-section through the center of ellipsoid and the geodesic segments, then calculate the area, which is easy to compare distances.
- Calculation with Performing a local spheroid approximation and return the 2D distance by map projection: Perform a local spheroid approximation, then use methods of map projection to calculate the distances. In this project, I use Azimuthal equidistant projection, accommodating equatorial, polar, oblique and Two-point equidistant projection make the 3D point to 2D with reliable functions, then do approximate calculation.
GSoC2017 Boost.Geometry:Filtering of compare distance predicates Proposal
