what is Boost Geometry? • a library dedicated to programmers • collection of types and algorithms • solving computational geometry problems • written in
MySQL (since 5 7) relies on Boost geometry for GIS support (geographic support since 8) ? no homegrown set of GIS functions for MySQL ? both aim in OGC
Boost Geometry Hello World Primitives Algorithms Spatial Index Debugging Helpers intersects, overlaps, relate, relation, within,
A series of boost geometry library proposals from Barend Gehrels and Bruno Lalande [2] have culminated into a tag dispatching based API where a generic free
package available in Boost Geometry, a highly parametrizable spatial index This chapter proposes a strategy for algorithmically optimizing the usage of
20 juil 2022 · data augmentation strategies to boost supervised segmentation of plant disease Computers and Electronics in Agriculture, Elsevier, 2019,
Arrangements and planar maps are ubiquitous in computational geometry, so we can apply the graph algorithms offered by the BOOST library8 [42] on it
28 jui 2019 · strategies in order to make the problem available to parallel comput- ing, thus speeding up the computing The issue with boost geometry
![[PDF] Spatial trajectories in Boost Geometry [PDF] Spatial trajectories in Boost Geometry](https://pdfprof.com/EN_PDFV2/Docs/PDF_6/34865_6FOSDEM20_vissarion.pdf.jpg)
34865_6FOSDEM20_vissarion.pdf
Spatial trajectories in Boost Geometry
Vissarion Fisikopoulos
FOSDEM 2020
Boost.Geometry
I
Part of Boost C++ Libraries
I
Header-only
I
C++03 (conditionally C++11)
I
Metaprogramming, Tags dispatching
I
Primitives, Algorithms, Spatial Index
I
Standards: OGC SFA
I used by MySQL for GIS
How to Get Started?
I
Documentation:www.boost.org/libs/geometry
I
Mailing list:lists.boost.org/geometry
I
GitHub:github.com/boostorg/geometry
Who is Boost.Geometry?
I Boost.Geometry is an open source project (as any other Boost library) I
Anybody can, and is welcome, to contribute
I
Core development team:
I
Barend Gehrels
IBruno Lalande
IMateusz Loskot
IAdam Wulkiewicz
IMenelaos Karavelas
IVissarion Fysikopoulos
I Contributions from about a dozen of other developers I
See Boost.Geometry website for credits and GitHub
repositorys history
Boost.Geometry &
I MySQL (since 5.7) relies on Boost geometry for GIS support (geographic support since 8) I no homegrown set of GIS functions for MySQL I both aim in OGC standard compliance I compatible licences I
MySQL benet from BG open source community
(maintenance, bug xing, gsoc) I BG is C++/header only!no problems with versions of a shared library on dierent platforms for MySQL
Hello, world!
# include < boost/geometry.hpp> # include < boost/geometry/geometries/geometries.hpp> # include < iostream> namespace b g= b oost::geometry; int m ain(){ using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; std::cout << bg::distance( point( 2 3 . 7 2 5 7 5 0 , 3 7 . 9 7 1 5 3 6 ), / /
Athens
,
A cropolis
point( 4 . 3 8 2 6 1 6 9 , 5 0 . 8 1 1 9 4 8 3 )); / /
Brussels
, U LB }result=2088:389km
Hello, world!
# include < boost/geometry.hpp> # include < boost/geometry/geometries/geometries.hpp> # include < iostream> namespace b g= b oost::geometry; int m ain(){ using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; std::cout << bg::distance( point( 2 3 . 7 2 5 7 5 0 , 3 7 . 9 7 1 5 3 6 ), / /
Athens
,
A cropolis
point( 4 . 3 8 2 6 1 6 9 , 5 0 . 8 1 1 9 4 8 3 )); / /
Brussels
, U LB }result=2088:389km
Hello strategies!
# include < boost/geometry.hpp> # include < boost/geometry/geometries/geometries.hpp> # include < iostream> namespace b g= b oost::geometry; int m ain(){ using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; std::cout << bg::distance( point( 2 3 . 7 2 5 7 5 0 , 3 7 . 9 7 1 5 3 6 ), / /
Athens
,
A cropolis
point( 4 . 3 8 2 6 1 6 9 , 5 0 . 8 1 1 9 4 8 3 ) / /
Brussels
,
U LBbg::strategy::distance::vincenty<>()) ;
}result=2088389m result with strategy=2088384m
Boost Geometry Algorithms=
CS-indep endentpa rt
+
CS-sp ecic
part (strategies)
Hello strategies!
# include < boost/geometry.hpp> # include < boost/geometry/geometries/geometries.hpp> # include < iostream> namespace b g= b oost::geometry; int m ain(){ using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; std::cout << bg::distance( point( 2 3 . 7 2 5 7 5 0 , 3 7 . 9 7 1 5 3 6 ), / /
Athens
,
A cropolis
point( 4 . 3 8 2 6 1 6 9 , 5 0 . 8 1 1 9 4 8 3 ) / /
Brussels
,
U LBbg::strategy::distance::vincenty<>()) ;
}result=2088389m result with strategy=2088384m
Boost Geometry Algorithms=
CS-indep endentpa rt
+
CS-sp ecic
part (strategies)
Models of the earth and coordinate systems
I Flat boost::geometry::cs::cartesianI
Sphere (Widely used e.g.google.maps)
boost::geometry::cs::sphericalequatorial
boost::geometry::cs::sphericalequatorial I Ellipsoid of revolution (geographic GIS state-of-the-art) boost::geometry::cs::geogrphic boost::geometry::cs::geogrphic I Geoid (Special applications, geophysics etc)
Models of the earth and coordinate systems
I Flat boost::geometry::cs::cartesianI Sphere (Widely used e.g.google.maps)
boost::geometry::cs::sphericalequatorial boost::geometry::cs::sphericalequatorial I Ellipsoid of revolution (geographic GIS state-of-the-art) boost::geometry::cs::geogrphic boost::geometry::cs::geogrphic I Geoid (Special applications, geophysics etc)
Models of the earth and coordinate systems
I Flat boost::geometry::cs::cartesianI Sphere (Widely used e.g.google.maps)
boost::geometry::cs::sphericalequatorial boost::geometry::cs::sphericalequatorial I Ellipsoid of revolution (geographic GIS state-of-the-art) boost::geometry::cs::geogrphic boost::geometry::cs::geogrphic I Geoid (Special applications, geophysics etc)
Models of the earth and coordinate systems
I Flat boost::geometry::cs::cartesianI Sphere (Widely used e.g.google.maps)
boost::geometry::cs::sphericalequatorial boost::geometry::cs::sphericalequatorial I Ellipsoid of revolution (geographic GIS state-of-the-art) boost::geometry::cs::geogrphic boost::geometry::cs::geogrphic I Geoid (Special applications, geophysics etc)
Spatial trajectories
I trajectories are sequencies of time-stamped locations I generated by GPS, smartphones, infrastructure, computer games, natural phenomena, etc I here we study only the spatial and not the temporal information, i.e. trajectories are modelled aslinestringsTrajetories of major huricanes in Atlantic[W anget al.'17]
Trajectories data-set
GeoLife GPS Trajectories dataset
[do wnload]https://www.microsoft.com/en-us/research/wp-content/ uploads/2016/02/User20Guide-1.2.pdf Two trajectories
Simple operations: size, length, distance
using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; bg::model::linestring ls 1 ,l s 2 ; std::ifstream myfile 1 ( " Geolife_Trajectories_
1 . 3 / Data / 0 0 0 / Trajectory
/ 2 0 0 9 0 5 1 6 0 9 1 0 3 8 . plt " ); std::ifstream myfile 2 ( " Geolife_Trajectories_
1 . 3 / Data / 0 1 0 / Trajectory
/ 2 0 0 8 1 2 2 4 0 1 1 9 4 5 . plt " ); read_linestring(myfile 1 ,l s 1 ); read_linestring(myfile 2 ,l s 2 ); std::cout << boost::size(ls 1 )< 2196.14
718.456
369.504
Note: distances in meters, result by use of non default strategies neglectable Closest points
using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; using l inestring= b g::model::linestring< point> ; linestring ls 1 ,l s 2 ; std::ifstream myfile 1 ( " Geolife_Trajectories_
1 . 3 / Data / 0 0 0 / Trajectory
/ 2 0 0 9 0 5 1 6 0 9 1 0 3 8 . plt " ); std::ifstream myfile 2 ( " Geolife_Trajectories_
1 . 3 / Data / 0 1 0 / Trajectory
/ 2 0 0 8 1 2 2 4 0 1 1 9 4 5 . plt " ); read_linestring(myfile 1 ,l s 1 ); read_linestring(myfile 2 ,l s 2 ); bg::model::segment sout; bg::closest_points(ls 1 ,l s 2 ,s out); Closest points
Simplication of trajectories
I simplication using Douglas-Peucker algorithm I quadratic worst case complexity [Hershb ergeret.al'92] I lineinterpolate: interpolate points on linestring at a xed distance I sampling points on linestrings (https://github.com/boostorg/geometry/pull/618) Simplify and lineinterpolate
using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; using l inestring= b g::model::linestring< point> ; linestring ls; std::ifstream myfile 2 ( " Geolife_Trajectories_
1 . 3 / Data / 0 1 0 / Trajectory
/ 2 0 0 8 1 2 2 4 0 1 1 9 4 5 . plt " ); read_linestring(myfile 2 ,l s); std::cout << " # points i n l s = " < Geolife_Trajectories_ 1 . 3 / Data / 0 0 0 / Trajectory
/ 2 0 0 9 0 5 1 6 0 9 1 0 3 8 . plt " ); std::ifstream myfile 2 ( " Geolife_Trajectories_
1 . 3 / Data / 0 1 0 / Trajectory
/ 2 0 0 8 1 2 2 4 0 1 1 9 4 5 . plt " ); std::ifstream myfile 3 ( " Geolife_Trajectories_
1 . 3 / Data / 0 0 0 / Trajectory
/ 2 0 0 8 1 0 2 6 1 3 4 4 0 7 . plt " ); read_linestring(myfile 1 ,l s 1 ); read_linestring(myfile 2 ,l s 2 ); read_linestring(myfile 3 ,l s 3 ); std::cout << bg::discrete_hausdorff_distance(ls 1 ,l s 2 )< < " , " << bg::discrete_hausdorff_distance(ls 2 ,l s 3 )< < " , " << bg::discrete_hausdorff_distance(ls 1 ,l s 3 ) << std::endl; std::cout << bg::discrete_frechet_distance(ls 1 ,l s 2 )< < " , " << bg::discrete_frechet_distance(ls 2 ,l s 3 )< < " , " << bg::discrete_frechet_distance(ls 1 ,l s 3 ) << std::endl;919.467, 7266.3, 8175.84 1260.76, 12601.7, 12837.9
Hausdor & Frechet distance
Comparing similarity of 160 pairs of trajectoriesnamespaceb f= b oost::filesystem; using p oint= b g::model::point < double , 2 ,b g::cs::geographic< bg::degree> >; linestring = bg::model::linestring ls 1 ,l s 2 ; bf::path p{ " Geolife_Trajectories_
1 . 3 / Data / 0 0 0 / Trajectory
/ " }; bf::directory_iterator it 1 {p}; double m in_frechet= 1 0 0 0 0 0 0 0 ; bf::directory_iterator it 2 {bf::path{ " Geolife_Trajectories_
1 . 3 / Data / 0 1 0 / Trajectory
/ " }}; for ( ;i t 2 ! =b f::directory_iterator{};i t 2 ++) { std::ifstream myfile 1 ((*it 1 ).path().string()); std::ifstream myfile 2 ((*it 2 ).path().string()); read_linestring(myfile 1 ,l s 1 ); read_linestring(myfile 2 ,l s 2 ); double f rechet= b g::discrete_frechet_distance(ls 1 ,l s 2 ); min_frechet = frechet < min_frechet ? frechet : min_frechet; }cartesian: 9.97[sec] spherical: 28.47[sec] geographic: 52.30[sec] Most similar trajectories
Same result for cartesian, spherical, geographic
Thank you! Questions?