Changes between Version 5 and Version 6 of SoC2017

Timestamp:

Feb 8, 2017, 5:42:51 PM (6 years ago)

Author:

awulkiew

Comment:

Add Boost.Geometry GSoC 2017 projects.

SoC2017

@@ -243 +243 @@
 3. fit in one header file
 
+=== 3. Boost.Geometry ===
+
+Potential mentors: Vissarion Fysikopoulos, Adam Wulkiewicz
+
+All projects requires knowledge of C++ template metaprogramming techniques. 
+
+==== Background ====
+
+Boost.Geometry part of collection of the Boost C++ Libraries, defines concepts, primitives and algorithms for solving geometry problems.
+
+See http://www.boost.org/libs/geometry
+
+==== PROJECT 1. Filtering of compare distance predicates. ====
+
+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.
+
+==== PROJECT 2. R-tree serialization. ====
+
+The goal is to implement serialization of Boost.Geometry R-tree with Boost.Serialization library. It should be done in a form of optional extension, i.e. Boost.Geometry shouldn't depend on Boost.Serialization by default. The example result could look like this:
+
+{{{
+#!c++
+#include <boost/archive/binary_oarchive.hpp>
+#include <boost/geometry.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/index/serialization/rtree.hpp>
+
+int main() {
+    namespace bg = boost::geometry;
+    namespace bgi = bg::index; 
+    typedef bg::model::point<double, 2, bg::cs::cartesian> point_type;
+    typedef bg::model::box<point_type> box_type;
+
+    bgi::rtree<box_type, bgi::rstar<16> > rtree;
+
+    // fill rtree with data 
+    std::ofstream file("serialized_rtree.bin",
+                       std::ios::binary | std::ios::trunc);
+    boost::archive::binary_oarchive archive(file);
+    archive << rtree;
+}
+}}}
+
+The project will require the student to understand parts of Boost.Geometry, in particular primitives and the internals of R-tree and the interface of Boost.Serialization library.
+
+==== PROJECT 3. Nearly antipodal points distance accuracy improvement. ====
+
+Compute accurately the distance between two nearly antipodal points on the ellipsoid of revolution. Currently Boost.Geometry does not handle this case correctly. A solution is proposed in [1] as a solution of a so called astroid problem. It is also implemented in C++ in [2].
+
+ * [1] Karney - Algorithms for geodesics (https://arxiv.org/pdf/1109.4448.pdf)
+ * [2] http://geographiclib.sourceforge.net
+
+==== Potential project extension funded by Boost
+
+N/A
+
 '''[wiki:GSoCIdeaTemplate To any potential mentor adding a proposal HERE please use this template]'''