Skip to content

Reports

Jump to bottom Edit New page
Rylynnn edited this page Aug 25, 2017 · 34 revisions

Table of Contents

Pre Bonding

Change to Boost

Programming competency test

  • Understand traits
  • Understand Boost.Geometry
  • Finish Programming competency test of project 1&3
  • Fix remarks

Study git branching model & commands

Link to study

Bonding

Previous Work

  • Continue improve Proposal.
  • Finish fix the test code review from Zheng Luo.
  • Learn C++ meta programming.
  • Learn Boost.Geometry functions with documents
  • Learn Boost.Geometry Contribution Tutorial.

Learn knowledge of geodesic from differential geometry and map projection.

  • Make a wiki page (TODO lists and weekly reports).

Learn C++ meta programming

Week 1

Discuss and Refine the Project Goal 1

  • Write a simple program using Boost.Geometry to show the performance(maybe in running times and memory used)between the performance of spherical distance computation vs. the comparable distance.test_spherical_comparable_distance.cpp
  • Improve the test tasks.
  • Improve Proposal with Vissarion's comment.

Improve Proposal with Vissarion's comment 1

  • List some algorithms from Boost Geometry that need to compare distances.
  • A similar problem we could study is the compare azimuths. Given p1, p2, q1, q2 we want to compare azimuth(p1,p2) vs. azimuth (q1,q2). The result again will be {larger than, less than, equal}. This problem appear in relational operations in Boost Geometry.Find places in the library that need to compare two azimuths.
  • Read and learn a Link, which not directly related but a useful reference for filtering in computational geometry is the following.

Getting start with Boost

  • OS: Linux Unbuntu 16.04
  • Boost: Boost 1.64.0
  • Path: ~/GSoC17/boost_1_64_0

Compile code with the following command:

c++ -I ~/GSoC17/boost_1_64_0 example.cpp -o example

To test the result, type:

./example

Test spherical comparable distance

The test code is test_spherical_comparable_distance.cpp

The compiled command is:

c++ -I ~/GSoC17/boost_1_64_0 test_spherical_comparable_distance.cpp -o test_spherical_comparable_distance

The simple result is;

rylynnn@rylynnn:~/GSoC17$ ./out
distance:17ms
comparable_distance:1ms

Week 2

Discuss and Refine the Project Goal 2

Debug buffer

Using GDB not to find a bug but to see the execution of the program and understand what functions are called. The target code is debug_buffer.cpp. the command of debug:

g++ -I ~/GSoC17/boost_1_64_0 -g debug_buffer.cpp -o debug_buffer
gdb debug_buffer
(gdb)b 44
(gdb)s
(gdb)n
(gdb)l
(gdb)q

The result is debug_buffer_result.txt.

Implement the test tasks

Test spherical comparable distance

The test code is test_spherical_comparable_distance.cpp

The compiled command is:

c++ -I ~/GSoC17/boost_1_64_0 test_spherical_comparable_distance.cpp -o test_spherical_comparable_distance

The simple result is;

rylynnn@rylynnn:~/GSoC17$ ./out
distance:17ms
comparable_distance:1ms

Improve the test case

Week 3

Improve Proposal with Vissarion's comment 2

Implement the test_geographic file

PR: https://github.com/boostorg/geometry/pull/401

Implement test_geographic.cpp

Implement comparable_geographic_distance.hpp

Week 4

Implement a function compare_length_of_two_segments

Implementation

  • Implement a function compara_length_of two_segments(p1, p2, p3, p4).
  • Compute lehgth of p1, p2 and the length of p3, p4 using Euclidean distance and return the result of comparion.
  • Use 2D geographic points.

Report and expandation

  • Implement and test also two other methods instead of pythagoras.
  • haversine
  • local earth approximation as a flat. should be implemented from here, and used in the special case when p1=p3 that is when the two segments have a common endpoint.
  • Create several examples to test for this case and observe where inconsistencies appear.
  • Keep the cartesian version
  • Fix the problems with indentation in your file
  • Fix the problem with add the following command in ~/.vimrc:
set expandtab

then command

:retab!
  • Use comments in code, keep them short but descriptive

Week 5

Improve a function compare_length_of_two_segments

  • Learn Geodesic calculations about reduced length, geodesic scale, area from Link

reduced length. If we fix the first point and increase azi1 by dazi1 (radians), the second point is displaced m12 dazi1 in the direction azi2 + 90°. The quantity m12 is called the "reduced length" and is symmetric under interchange of the two points. On a curved surface the reduced length obeys a symmetry relation, m12 + m21 = 0. On a flat surface, we have m12 = s12. The ratio s12/m12 gives the azimuthal scale for an azimuthal equidistant projection. geodesic scale. Consider a reference geodesic and a second geodesic parallel to this one at point 1 and separated by a small distance dt. The separation of the two geodesics at point 2 is M12 dt where M12 is called the "geodesic scale". M21 is defined similarly (with the geodesics being parallel at point 2). On a flat surface, we have M12 = M21 = 1. The quantity 1/M12 gives the scale of the Cassini-Soldner projection. area. The area between the geodesic from point 1 to point 2 and the equation is represented by S12; it is the area, measured counter-clockwise, of the geodesic quadrilateral with corners (lat1,lon1), (0,lon1), (0,lon2), and (lat2,lon2). It can be used to compute the area of any simple geodesic polygon.

Implement compare_distance headers

Learn Guidelines for Developers

Link: https://github.com/boostorg/geometry/wiki/Guidelines-for-Developers Issue from learning:

  • Do not know the meaning of

References and pointers should be formatted emphasizing type, not syntax:

T const& t;
T* t;
T* const t;
T const* t;
T const* const t;

Implement compare_distance headers

Week 6

Improve Proposal with Vissarion's comment 3

On the surface of a sphere, geodesics lie along great circles (i.e. a circle with its center at the center of the sphere). An ellipsoid geodesic is a minimum-distance path on an ellipsoid, and you might be tempted to think it's a great-ellipse (an ellipse where the center of the ellipse is located at the center of the Earth). If you think it's a great-ellipse, you are right in some cases; in other cases, it is not an ellipse but an ill-defined oval of some sort.

Learn and optimize Andoyer distance 1

Goal

  • Could we chop out some trigonometric or other functions to create a comparable andoyer?

Report

Week 7

Test Approximations

Report

All the test files are here

For Haversin: Before I started the work of testing: I studied Haversine formula, as we know that haversin(θ) = sin2(θ/2) is monotonicallly increaseing with θ in (0,π), then we can see the haversine formula: haversine In spherical model, r is constant value, and we calculate the length of two points, value d / r will always in the range of (0,π), so we can simply approximately calculate length by haversine, and we need to find the point when haversine calculation different from vincenty calculation.

I tried to create example, I fixed the first segment's starting point p1 on (0,0), and then make it's ending point p2 active from p1's symmetrical location to approach p1, then for every p1, p2, I fixed the second segment's first point p3 on (0, 10), then putted p4 same operation with p2.

  • the code of creating test haversine case is tc_equator.cpp
  • the code of tesr haversine formula is testcase_begin_equator.cpp, I output the result if haversine calculation is different from vincenty calculation.
  • the input file is tc_begin_equator.in, and the output file is tc_begin_equator.out
  • As we can see for segments close to equator with latitude less than 23 the haversine suffices for comparison,

For flat_approximation: I used the same method to create test cases, but the difference is I made p3 equal to p1.

  • the code of creating test flat_approximiation case is tc_equator_flat.cpp
  • the code of tesr haversine formula is testcase_begin_equator_flat.cpp, I output the result if haversine calculation is equal to vincenty calculation.
  • the input file is tc_begin_equator_flat.in, and the output file is tc_begin_equator_flat.out
  • As we can see for segments close to equator use flat_approximiation have more complicated, may be it related to subtraction of the length of two segments, I need to make it clearer.

Question

Issues from learing or contribution 1

Guidelines for Developers
  • Do not know the meaning of

References and pointers should be formatted emphasizing type, not syntax:

T const& t;
T* t;
T* const t;
T const* t;
T const* const t;

Week 8

This week I asked Vissarion for 10 days off because of my sickness, after that I came back and worked harder to finished the task.

Week 9

Comment

Remember that your final goal is to have a faster way to compare lengths of segments(mostly care about one common point ie. p1=p3). If you can have it for some specific inputs only, it's a partial solution which is not bad. Also if some solution e.g. haversine does not work for some inputs this sis also interesting should be noted down.

Improve flat_approximation

  • There are repeated parts in my formula, to avoid this we have functions ;)
  • The formula in http://www.edwilliams.org/avform.htm#flat is defined for two points p0=(lon0,lat0) (which is the fixed point) and p=(lon,lat). So then when you have the formula you should call it with p1,p2 first and p1,p4 then compare.
  • Get your parameters like radius from the input spheroid and note handwritten r.e. use get_radius<>(spheroid)on.hpp

Learn and optimize Andoyer distance 2

Goal

On the surface of a sphere, geodesics lie along great circles (i.e. a circle with its center at the center of the sphere). An ellipsoid geodesic is a minimum-distance path on an ellipsoid, and you might be tempted to think it's a great-ellipse (an ellipse where the center of the ellipse is located at the center of the Earth). If you think it's a great-ellipse, you are right in some cases; in other cases, it is not an ellipse but an ill-defined oval of some sort.

Week 10

Implement area of a sector of the ellipse

* [ ] Implement area of a sector of the ellipse with Proposal.

Change the goal of project

Discuss and Refine the Project Goal 3

  • Implement the code

-- flat earth approximation

-- area of a sector of the ellipse

-- comparable andoyer

Add: -- comparable lambert

Learn Unit Test and Documentation

Issues from learing or contribution 2

Add issue on boost/geometry:

https://github.com/boostorg/geometry/issues/414

UPDATE: Successfully fixed

Fix error:
pyconfig.h no such file or directory boost

with:

sudo apt-get python-dev install
Add PATH in ~/.bashrc:
export http_proxy=http://localhost:8123
export INCLUDE=/home/rylynnn/boost:$INCLUDE
export LIBRARY_PATH=/home/rylynnn/boost/stage/lib:$LIBRARY_PATH
export BOOST_ROOT=/home/rylynnn/boost:$BOOST_ROOT

export PATH=/home/rylynnn/boost:/home/rylynnn/boost/dist/bin:/home/rylynnn/bin:/home/rylynnn/.local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin:/home/rylynnn/.vimpkg/bin

Inverse problem

Week 11

Learn and implement Andoyer and Lambert

Implement of Andoyer and Lambert:

Reference:

https://archive.fosdem.org/2017/schedule/event/geo_boost_geography/attachments/slides/1748/export/events/attachments/geo_boost_geography/slides/1748/FOSDEM17_vissarion.pdf

Andoyer:

http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5115/Geographic-Distance-and-Azimuth-Calculations.htm

http://jmst.ntou.edu.tw/marine/21-3/287-299.pdf

Lambert:

http://www.ilouzhu.com/yuedu/9vnt.html

http://jmst.ntou.edu.tw/marine/21-3/287-299.pdf

Test result of Andoyer and Lambert

Test Andoyer

https://github.com/BoostGSoC17/geometry/tree/feature/filter/example/test_approximation/test_andoyer

  • The code of test andoyer:test_andoyer.cpp
  • I random almost 10000 test case to test the code, and the result is:
The number of testcase:98367
The number of different result:24366

Test Andoyer

https://github.com/BoostGSoC17/geometry/tree/feature/filter/example/test_approximation/test_lambert

  • The code of test lambert:test_lambert.cpp
  • I random almost 10000 test case to test the code, and the result is:
The number of testcase:98367
The number of different result:24406

To make the test more convenient, I implement a header of comparable vincenty: compare_length_vincenty.hpp

Week 12

Add a custom footer

Boost

Table of Contents

Clone this wiki locally