[PDF] Spatial trajectories in Boost Geometry




Loading...







[PDF] Introduction to BoostGeometry - FOSS4G 2010

what is Boost Geometry? • a library dedicated to programmers • collection of types and algorithms • solving computational geometry problems • written in 

[PDF] Spatial trajectories in Boost Geometry

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 

[PDF] Introduction to BoostGeometry (slides)

Boost Geometry Hello World Primitives Algorithms Spatial Index Debugging Helpers intersects, overlaps, relate, relation, within,

[PDF] Geometry Template Library for STL-like 2D Operations

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 

[PDF] R-tree performance evaluation and optimization - IKEE

package available in Boost Geometry, a highly parametrizable spatial index This chapter proposes a strategy for algorithmically optimizing the usage of 

[PDF] Novel data augmentation strategies to boost supervised

20 juil 2022 · data augmentation strategies to boost supervised segmentation of plant disease Computers and Electronics in Agriculture, Elsevier, 2019, 

Advanced programming techniques applied to CGAL's arrangement

Arrangements and planar maps are ubiquitous in computational geometry, so we can apply the graph algorithms offered by the BOOST library8 [42] on it

[PDF] Parallelization of Computational Geometry Algortihms

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 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 bene t from BG open source community

(maintenance, bug xing, gsoc) I BG is C++/header only!no problems with versions of a shared library on di erent 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 eci c

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 eci c

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

Simpli cation of trajectories

I simpli cation 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?