Home
Implementation of Boost's 2017 GSoC Project: Boost.Geometry: Filtering of compare distance predicates
Boost is a collection of free, peer-reviewed C++ libraries. We emphasize libraries that work well with the C++ Standard Library. Boost libraries are intended to be widely useful, and usable across a broad spectrum of applications. The Boost license encourages both commercial and non-commercial use.
Boost.Geometry (aka Generic Geometry Library, GGL), part of collection of the Boost C++ Libraries, defines concepts, primitives and algorithms for solving geometry problems. Boost.Geometry contains a dimension-agnostic, coordinate-system-agnostic and scalable kernel, based on concepts, meta-functions and tag dispatching. On top of that kernel, algorithms are built: area, length, perimeter, centroid, convex hull, intersection (clipping), within (point in polygon), distance, envelope (bounding box), simplify, transform, and much more. The library supports high precision arithmetic numbers, such as ttmath.
In some algorithms there is the need to compare two distances of two point pairs. That is, use the predicate compare_distance(p1, p2, q1, q2) that returns (1, 0, -1) if the length of segment (p1, p2) is larger, equal or smaller respectively than the length of segment (q1, q2). Since, computing distances could be costly especially when computing on the ellipsoid (i.e. geographic computations) we would like to avoid that computation whenever possible.
One approach could be to compute the 3D cartesian distances first and if these numbers are not "far enough" then fall back to expensive geographic distance calculation otherwise return the result by comparing those numbers obtained by less expensive cartesian compuation. There are some issues that should be further clarified, e.g. declare the "far enough" value that works in practice. Several other approaches could be used and tested, e.g. perform a local spheroid approximation and return the 2D distance.
The project will require the student to understand parts of Boost.Geometry, in particular algorithms and strategies. Some knowledge of computational geometry is a plus.
All the details of my proposal of GSoC 2017.
All the branch information during the whole process of GSoC 2017, including formal coding and programming competency test.
All commits I have done can be found from here:
Open and closed issues recorded the problems and the solutions I done during the program. Open and closed milestones cut the works into four sections.
The weekly reports, which can demonstrate the work that was done during the program.
All the references I read and learn during the program.
Thank my mentor Vissarion Fysikopoulos([email protected]), Adam Wulkiewiczand([email protected])and Boost C++ Libraies for the superb guidance and support which gave throughout the project.As well as I would like to thank GOOGLE for giving me this opportunity to have a valuable,amazing Summer. I am willing to continue developing and contributing to Boost.Geometry and Boost community . And I would like to expand and optimize other functions from Boost, the work I do will indeed improve engineering ability and abundant my experience of coding for open source community.
