Basic Operations

Operations On Points

The tracktable namespace has most of the operations we want to perform on two or more points. Here are a few common ones, a comprehensive list of operations can be found in the tracktable core detail reference documentation. Arguments of type Geometry can be base_point_type, trajectory_point_type, trajectory_type, or linestring_type. Arguments of type Point can be base_point_type or trajectory_point_type. The data types of different arguments can be different (for example, computing the distance between a point and a trajectory, or a trajectory and a linestring), but all arguments must come from the same point domain (terrestrial, 2D Cartesian, or 3D Cartesian).

  • distance(Geometry const& from, Geometry const& to): Compute distance between from and to

  • bearing(Point const& from, Point const& to): Compute the bearing from the origin to the destination

  • speed_between(Point const& start, Point const& finish): Compute speed between two trajectory points

  • signed_turn_angle(Point const& a, Point const& b, Point const& c): Angle between vectors AB and BC

  • unsigned_turn_angle(Point const& a, Point const& b, Point const& c): Absolute value of angle between vectors AB and BC

Analysis

Once the points or trajectories have been generated and annotated we need to perform analysis to determine information about the points or trajectories such as clustering, distance geometry, nearest neighbors or greatest/best fit circle.

The tracktable Analysis module contains the following components necessary to to perform these types of analyses on points or trajectories.

  • The AssembleTrajectories class will take a set of points and combine them into a trajecotry sorted by non-decreasing timestamp.

  • The cluster_with_dbscan() and build_cluster_membership_lists() functions will perform the density-based spatial clustering of applications with noise analysis to determine the clustering of the feature vector points.

  • The distance_geometry_by_distance() and distance_geometry_by_time() functions will compute the multilevel distance geometry for a trajectory based on either distance or time.

  • The great_circle_fit_and_project_in_place(), great_circle_fit_and_project(), find_best_fit_plane() and project_trajectory_onto_plane() functions will generate a circle that best fits the given trajectory and projects it onto the specified plane.

  • The RTree class will generate an R-tree to efficiently compute the nearest neighbors based on provided points within a clustering box.

Trajectory Assembly

Creating trajectories from a set of points is simple conceptually but logistically annoying when we write the code ourselves. The overall idea is as follows:

  1. Group points together by object ID and increasing timestamp.

  2. For each object ID, connect one point to the next to form trajectories.

  3. Break the sequence to create a new trajectory whenever it doesn’t make sense to connect two neighboring points.

When assembling trajectories from a sequence of points we can specify two parameters that control when to start a new trajectory:

  • separation_time: A boost::posix_time object specifying the longest permissible gap between points in the same trajectory. Any gap longer than this will start a new trajectory.

  • separation_distance: A float value representing the maximum permissible distance (in kilometers) between two points in the same trajectory. Any gap longer than this will start a new trajectory.

We can also specify a MinimumTrajectoryLength. Trajectories with fewer than this many points will be silently discarded.

Trajectory Assembly
 1 #include <tracktable/Domain/Terrestrial.h>
 2 #include <tracktable/Analysis/AssembleTrajectories.h>
 3
 4 typedef tracktable::domain::terrestrial::trajectory_point_reader_type reader_type;
 5 typedef tracktable::domain::terrestrial::trajectory_type trajectory_type;
 6 typedef tracktable::AssembleTrajectories<trajectory_type, reader_type::iterator> assembler_type;
 7
 8 reader_type point_reader;
 9 assembler_type trajectory_builder;
10
11 trajectory_builder.set_separation_time(tracktable::minutes(20));
12 trajectory_builder.set_separation_distance(100);
13 trajectory_builder.set_minimum_trajectory_length(500);
14
15 std::string filename = "point_data.csv";
16 std::ifstream infile(filename.c_str());
17
18 if (!infile)
19   {
20     std::cerr << "ERROR: Could not open file '" << filename << "'\n";
21     return -1;
22   }
23
24 point_reader.set_input(infile);
25 point_reader.set_object_id_column(0);
26 point_reader.set_timestamp_column(1);
27 point_reader.set_longitude_column(2);
28 point_reader.set_latitude_column(3);
29
30 trajectory_builder.set_input(point_reader.begin(), point_reader.end());
31
32 for (assembler_type::iterator iter = trajectory_builder.begin(); iter != trajectory_builder.end(); ++iter)
33   {
34     // Process trajectories here
35   }

DBSCAN Clustering

The DBSCAN module is responsible for performing box based density based clustering for any given set of feature vector points for a given search area. The number of points that define a cluster can be adjusted as needed. Additional information on DBSCAN clustering can be found at: https://en.wikipedia.org/wiki/DBSCAN

Note

Our implementation of DBSCAN is templated on point type and uses boost::geometry for all of its distance math. This means that it will automatically adapt to whatever coordinate system you’re using for your points as long as Boost knows what to do with it.

This is usually great. However, there are times when it will slow you down tremendously. For example, if you’re clustering a bunch of points that are very close together on the surface of a sphere, you might do just fine by pretending that the space is Cartesian (flat) instead of spherical. That will run dramatically more quickly and with greater precision than the trigonometry necessary for doing distance computations on a sphere.

DBSCAN Clustering
 1 #include <tracktable/Analysis/ComputeDBSCANClustering.h>
 2 #include <tracktable/Domain/Terrestrial.h>
 3
 4 typedef tracktable::domain::terrestrial::TerrestrialPoint TerrestrialPoint;
 5
 6 TerrestrialPoint point_one;
 7 TerrestrialPoint point_two;
 8 std::vector<tracktable::domain::terrestrial::TerrestrialPoint> my_points;
 9 std::vector<std::pair<int, int>> cluster_labels;
10 TerrestrialPoint search_box(0.5, 0.5);
11 int min_cluster_size = 10;
12
13 point_one.set_longitude(40);
14 point_one.set_latitude(50);
15
16 point_two.set_longitude(41);
17 point_two.set_latitude(51);
18
19 my_points.push_back(point_one);
20 my_points.push_back(point_two);
21
22 int num_clusters = cluster_with_dbscan<TerrestrialPoint>(
23   my_points.begin(),
24   my_points.end(),
25   search_box,
26   min_cluster_size,
27   std::back_inserter(cluster_labels)
28 );

Distance Geometry

The Distance Geometry module is responsible for computing the mutilevel distance geometry signiture of a given trajectory sampled by distance or time. Each level d approximates the input trajectory with d equal-length line segments. The distance geometry values for that level are the lengths of all d line segments, normalized to lie between 0 and 1. A value of 1 indicates the length of the entire trajectory. The D-level distance geometry for a curve will result in (D * (D+1)) / 2 separate values.

Distance Geometry by Distance and Time
 1#include <tracktable/Analysis/DistanceGeometry.h>
 2#include <tracktable/Domain/Terrestrial.h>
 3
 4typedef tracktable::domain::terrestrial::trajectory_point_type TerrestrialTrajectoryPoint;
 5typedef tracktable::domain::terrestrial::trajectory_type TerrestrialTrajectory;
 6
 7double terrestrial_coordinates[][2] = {
 8  {0, 80},
 9  {90, 80},
10  {180, 80},
11  {-90, 80},
12  {0, 80},
13  {-1000, -1000}
14};
15
16const char* timestamps[] = {
17  "2000-01-01 00:00:00",
18  "2000-01-01 02:00:00",
19  "2000-01-01 03:00:00",
20  "2000-01-01 04:00:00",
21  "2000-01-01 06:00:00"
22};
23
24TerrestrialTrajectory trajectory;
25int i = 0;
26while (terrestrial_coordinates[i][0] > -1000)
27{
28  TerrestrialTrajectoryPoint point;
29  point.set_object_id("terrestrial_dg_test");
30  point.set_longitude(terrestrial_coordinates[i][0],);
31  point.set_latitude(terrestrial_coordinates[i][1]);
32  point.set_timestamp(tracktable::time_from_string(timestamps[i]));
33
34  trajectory.push_back(point);
35
36  ++i;
37}
38
39std::vector<double> terrestrial_dg = tracktable::distance_geometry_by_time(trajectory, 4);

Great Circle Fit

The Great Circle Fit module is responsible for generating the great circle that best fits each given trajectory or set of points with the option to project the circle onto a specified plane. The functions in this module provide options for generating and projecting great circles.

Great Fit Circle and Projection
 1#include <tracktable/Analysis/GreatCircleFit.h>
 2#include <tracktable/Domain/Terrestrial.h>
 3
 4using TrajectoryT = tracktable::domain::terrestrial::trajectory_type;
 5using PointT = TrajectoryT::point_type;
 6
 7auto NUM_POINTS = 100u;
 8auto HEADING_EAST = 90.0;
 9auto HEADING_NORTH = 0.0;
10auto SPEED = 30.0;
11auto ALTITUDE = 1000.0;
12auto ZIG = 0.01;
13auto ZAG = -ZIG;
14auto NORMAL_TOLERANCE = 0.0001;
15
16// Generate points and accompanying trajectory
17
18auto p = tracktable::arithmetic::zero<PointT>();
19p.set_property("altitude", ALTITUDE);
20
21// Generator for a trajectory with a speed of .01(deg/s), an update interval of 60s and a heading of 90deg
22tracktable::ConstantSpeedPointGenerator generatorEast(p, tracktable::minutes(1), SPEED, HEADING_EAST);
23
24TrajectoryT hundredPointEast;
25
26for (auto i = 0u; i < NUM_POINTS; ++i) {
27  hundredPointEast.push_back(generatorEast.next());
28}
29
30// Fit a circle
31
32auto normal = tracktable::find_best_fit_plane(hundredPointEast);
33
34// Project the circle onto a plane
35
36tracktable::project_trajectory_onto_plane(hundredPointEast, normal);

R-Tree

The RTree class is responsible for generating an R-tree data structure. An R-tree data structure is used for spatial access methods such as indexing geographical coordinates or polygons. The functions within this module will generate the r-tree structure as well as finding find all of the points within a given bounding box as well as find the K nearest neighbor for a given search point.

RTree: Finding Points and Neighbors
 1#include <tracktable/Analysis/RTree.h>
 2#include <tracktable/Domain/Terrestrial.h>
 3#include <boost/tuple/tuple.hpp>
 4
 5std::vector<tracktable::domain::terrestrial::base_point_type> base_points;
 6
 7// This function algorithmically creates a point grid that will produce an R-Tree structure
 8create_point_grid<base_point_type>(1, 9, std::back_inserter(base_points));
 9
10base_point_type search_point;
11for (unsigned int i = 0; i < search_point.size(); ++i)
12  {
13    search_point[i] = 0;
14  }
15search_point[0] = -20;
16
17tracktable::RTree<base_point_type> rtree(base_points.begin(),
18                                        base_points.end());
19
20std::vector<base_point_type> query_results_bare, query_results_pair, query_results_tuple;
21rtree.find_nearest_neighbors(
22  search_point,
23  1,
24  std::back_inserter(query_results_bare)
25);
26
27rtree.find_nearest_neighbors(
28    std::make_pair(search_point, 1000),
29    1,
30    std::back_inserter(query_results_pair)
31  );
32
33rtree.find_nearest_neighbors(
34    boost::make_tuple(search_point, 10000),
35    1,
36    std::back_inserter(query_results_tuple)
37  );