Spatial trajectories in Boost Geometry
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Alternative Title |
| |
| Title of Series | ||
| Number of Parts | 490 | |
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/47050 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
OracleGeometryGeometryMereologyEmailConditional probabilityAlgorithmPrice indexStandard deviationMeta elementComputer programmingElectronic mailing listSource codeLibrary (computing)Core dumpSoftware developerWebsiteRepository (publishing)Computing platformFunction (mathematics)Software maintenanceRevision controlOpen sourceComputer virusPoint (geometry)State diagramDegree (graph theory)Strategy gameIndependence (probability theory)DistanceLink (knot theory)Point (geometry)Dimensional analysisEmailGoodness of fitMappingCodeProcess (computing)Thomas BayesOpen sourceLatent heatComputational geometryFunctional (mathematics)Water vaporSoftware developerLibrary (computing)Set (mathematics)1 (number)Shared memoryStandard deviationNamespaceScaling (geometry)Moment (mathematics)Projektive GeometrieTorusPerspective (visual)MereologyRow (database)Subject indexingDemosceneBitElectronic mailing listMetreSlide ruleDifferent (Kate Ryan album)Bit rateGeometryDoubling the cubeCoordinate systemPhysical systemTrajectoryDegree (graph theory)AlgorithmComputer fileSinc functionGroup actionStrategy gameResultantComputer animation
04:07
Endliche ModelltheorieSystem programmingCurvatureCartesian productGeometrySphereSurface of revolutionEllipsoidCodeDefault (computer science)FeedbackStrategy gameCartesian productAlgorithmPhysical systemResultantGenetic programmingObservational studyFluxDegree (graph theory)CommutatorComputer animation
05:20
TrajectorySequenceGenetic programmingSmartphoneComputerTemporal logicGame theoryInformationString (computer science)TrajectoryPoint (geometry)String (computer science)Video gameSequenceSet (mathematics)Uniform resource locatorGenetic programmingSmartphoneComputational geometryInformationResource allocationGame theoryObject (grammar)Multiplication signLevel (video gaming)Computer animation
06:14
TrajectoryContent (media)Genetic programmingVideo gamePoint (geometry)Process (computing)BenutzerhandbuchVideo gameProjektive GeometrieSet (mathematics)Level (video gaming)Zoom lensGenetic programmingTrajectoryComputer animation
06:56
Operations researchState diagramTrajectoryModul <Datentyp>String (computer science)Point (geometry)AlgorithmQuadratic equationKolmogorov complexityInterpolationGeometrySimilarity (geometry)Hausdorff spaceSequenceString (computer science)InterpolationAlgorithmTrajectoryPoint (geometry)Similarity (geometry)Computational geometryDivision (mathematics)Quadratic equationMeasurementGeometryLine (geometry)MetreError messageDistanceLengthCodeSampling (statistics)Right angleElectronic mailing listSet (mathematics)1 (number)Maxima and minimaProjektive GeometrieStrategy gameDifferent (Kate Ryan album)InformationSequenceGleichverteilungHausdorff-MetrikStructural loadCommutatorDecision theoryCASE <Informatik>Pointer (computer programming)WebsiteTelecommunicationCausalityCondition numberBitResultantMachine visionExpected valueGoodness of fitClosed setCodeComputer clusterLie groupUniformer RaumScheduling (computing)Computer animation
14:49
TrajectoryHausdorff spaceState diagramBitHausdorff-MetrikLine (geometry)TrajectoryResultantCASE <Informatik>Computer animation
15:12
Streaming mediaState diagramTrajectoryHausdorff spaceSphereCompilation albumCartesian productProof theoryResultantComputational geometryLine (geometry)Similarity (geometry)SpheroidSet (mathematics)MereologyDistanceMultiplication signInformationTrajectoryPhysical system2 (number)Maxima and minimaDifferent (Kate Ryan album)Cartesian productCondition numberGraph (mathematics)View (database)Structural loadCodeCommutatorVirtual machineDecision theoryArithmetic meanDemosceneComputer simulationSphereComputer animation
18:46
Point cloudFacebookOpen source
Transcript: English(auto-generated)
00:05
The floor is yours. Okay, so thank you. So today we'll talk about how to work with spatial trajectories in boost geometry. So this is also new for me, the first part, I mean, the title.
00:23
Okay, so usually I have some slides regarding what is boost geometry. So if you followed three talks ago, maybe you have seen most of them. So it's boost C++ libraries. It's yeted only.
00:41
It's written in the old C++ standard. Conditionally you can use some features from the new ones. And yes, it provides primitives, algorithms, and spatial index that I will use today to showcase spatial trajectories computations.
01:06
And yes, it tries to follow the OGC and SFA standards. So these are some useful links about documentation, the mailing list, and the code base which is on GitHub.
01:23
And yes, this is about the developers. So at least three of them in this list are in this room. And there are dozens of other developers. The last three years we also participated in the Google Summer of Code.
01:40
So we usually open some internships for the summer. Yes, that's the credits about the development. And okay, this is boost geometry from the MySQL perspective. So it's used by MySQL to provide GIS support.
02:05
So this is good for MySQL because there are no home group GIS functions there. Both projects are aiming in OGC standard. They have compatible licenses. And also, MySQL benefits from the boost geometry open source community.
02:23
And yes, since it's C++ and header only, there are no problem with shared libraries and all this technical stuff in MySQL. Okay, so this is the same slide as all the previous years I'm presenting here about boost geometry.
02:41
So it's a hello world thing, how to compute a distance from my home place to ULB. So actually it's just a set of header files and then you use the boost geometry namespace. You define one point in two dimensions with double arithmetic.
03:01
And you use the geographic coordinate system in degrees. So you can create those two points with longitude, latitude, coordinates. And okay, boost geometry will compute this distance for you.
03:21
This is more accurate than the one that you get from Google Maps. So it's geographic computation. And you can also do a bit more advanced things. You can define a strategy which gives you more accuracy and plug it into the distance algorithm.
03:41
Then you get a bit more accurate results. So it's only a few meters difference in that particular situation. And this is the whole idea about the algorithm in boost geometry. It's a coordinate independent part which is the combinatorial algorithm.
04:01
It's also a coordinate specific part which we call it strategies. Okay, so again, let me just briefly say that the three coordinate systems that we support. So we have the Cartesian one. And then there is the spherical equatorial.
04:23
This is the one that Google Maps is using. So you can parameterize this either by degrees or radians. And then we have the geographic one. It's more precise but also slower to do computations. So in the whole talk, I'm using the last one, the geographic one, with all the defaults.
04:47
Just to have a simpler code examples, you'll see. So I'm trying to have simpler examples. Yes, you'll give me feedback on this if you are not. But you can use all of them and also you can use, especially with geographic one,
05:06
you can use more detailed strategies. So you can change the geographic algorithm that you use. And you can have various different results and also performances. Okay, so yes, this is not used.
05:23
Okay, so spatial trajectories that we're talking today, it's a sequence of time-stamped locations that can be generated by many devices, GPS and smartphones and also computer games or natural phenomena. So for example, these are the trajectories of major hurricanes in the Atlantic.
05:45
So in this talk, I will give examples with trajectories that I do not consider the temporal information. So as far as I understand, the next talk has some temporal computations.
06:03
And so trajectories can be easily modeled as a line string. So it's just a set of sequence of points with a longitude latitude. Okay, this is the data set that I will use. It's a geolive GPS trajectories data set.
06:22
It's open, you can download it. There is also a user guide. It's a set of trajectories produced by walking, bicycles, cars. Okay, you can see in the user guide the details.
06:42
Most of them are in BiZinc. So this is the heat map of the data set in BiZinc and zoomed. So, okay, I'm just selecting to start, I'm just selecting two trajectories from the whole data set to do some simple computations.
07:02
Okay, so this is how my C++ code looks like. So I'm defining the point again which is geographic. I create two line strings. I load my two trajectories on the line strings and then I can ask what's the size.
07:22
The size means how many points you have in the trajectory. So you can see the first trajectory has 317 points. The second one has 75. And then I can ask what is the length. This is in meters. So I can take the two lengths of the trajectories.
07:41
And then I can also ask what is the distance between those trajectories. So this is the shortest distance from one trajectory to the other. This is again in meters and I get this result. Okay, so if I use strategies here to make it more advanced,
08:01
since all of these are very short, I mean, it's less than two kilometers, the whole distance, I will not see any difference. So I can just use the default algorithms. So I can also compute the closest points between the two trajectories.
08:24
So I'm one trajectory and the other trajectory, which are the two points that are closest between those two. And this, actually this will give me the shortest distance. But the computation is a bit different.
08:41
So I can ask, I can call this closest point algorithm. This is not in boost geometry. It will be a pull request on this. So you cannot use it right now. And you get this blue segment, which gives you the two shortest points there.
09:02
Again, the computation here is geographic, but what I plot is just 2D. So I don't even do a projection, just plotting them. So the projection you can have a slightly different result, but this is just to see how those trajectories
09:20
and the computations look like. Okay, so then I can do some more, let's say, advanced computations, not only lengths and distances. So I can simplify my trajectory. So in boost geometry there is a simplification algorithm that is using this Douglas-Poker algorithm.
09:44
It's quadratic in the worst case, but in practice you probably experience something like n log n. And there is also a line interpolate algorithm that given a measure,
10:02
it interpolates points on your line string. So if you give a short distance, then you will get more points than the line string has. So the line string will be densified. And if you give a larger distance, then you can get less points than the trajectory,
10:24
than your trajectory. You can represent your trajectory with less points. And the last one is, it was a Google Summer of Code project, it's in pull request still. You can also sample points from the line string. And as far as I remember,
10:41
only with uniform distribution right now, but this can be extended. So you can ask, OK, I want 1,000 points uniform distributed on my trajectory. So we'll get all those points. OK, again some code.
11:02
So again I load my trajectory and then I compute how many points I have. So this trajectory has 75 points. This is the length. And then I can call the simplify algorithm with 20 here. So 20 means the new line string
11:25
that approximates my original one, I want to have error 20 meters at most. So this is the 20 there. And then I can call the line interpolate algorithm
11:41
with my trajectory and 70. So this is every 70 meters, I create one point. So I start in my trajectory and I move on the trajectory and every 70 meters I create one point. OK, so I then put the random one. So the random will create random points on the line string.
12:04
OK, and with those parameters, the simplified trajectory has only six points and the interpolation creates nine points. So you can easily see this with the interpolation case,
12:20
you can easily see it by division. It's expected. OK, and this is how this looks like. The red one is the original trajectory. These are my interpolated points. And the green one is the simplified trajectory. So yes, I can use either the points
12:42
or the simplified trajectory to do computations because it's smaller, shorter. OK, and then this is the last computation I'm doing with trajectories is measuring the similarity. So there are many measures in the literature. So maybe the most well-known or used in practice
13:05
as far as I understand is the Hausdorff distance and the Frézé distance. OK, I'm talking about this because these are the ones that are implemented in this geometry. So the Hausdorff, let's say that is a more cruel measure.
13:23
I take the maximum or the minimums of all the possible distances. So here in the example, the Hausdorff is that distance. So it's a different measure, the Frézé distance, because it counts also the sequence, not only.
13:42
So Hausdorff is like taking a set of points, don't care about the sequence. But in Frézé, you also care about the sequence. So you create a coupling between the points of your sequence. It's like if you have, yes, you have probably, maybe you have heard about the problem of walking your dog.
14:02
So there is one person that is walking in one trajectory and the dog is in the other trajectory, and you want to see what is the minimum list that you can use to walk your dog. So actually, this is the Frézé distance. But you can see in this example that the Frézé distance
14:22
gives you more information about the similarity because these are two not very similar, dissimilar curves, line strings. Hausdorff distance will be small, but Frézé distance is large. So Frézé somehow describes better the similarity.
14:46
And there are more. But I will talk about those two here. So I have three trajectories now to do a simple example. Okay, the one is much larger, so that's why the other two are a bit scaled down.
15:04
And I will compute the Hausdorff distance between all the possible pairs. So the first line string, okay, it's like this. So the first is the red, the second is the green, and the third is the blue. And when I compute Hausdorff and Frézé,
15:22
in this case, it gives me the same result. So it tells me that the smaller it is, the more similar are the trajectories. So it tells me that the first two are more similar, and then the green is more similar to blue than the red to blue.
15:43
So those two, the small ones, are more similar, and then the green, maybe because of the shape, is more similar to this than the red to the blue. Okay, this is the information that I'm getting. Okay, and this is the last example.
16:03
Okay, this data set is huge. You can do many computations, but I only do, as a proof of concept, a few of them. So here I took one trajectory from one data set, and I compared it against 160 trajectories.
16:24
And the interesting part I found here is that I can use either Cartesian or spherical or geographic coordinate systems. So in this piece of code, you just go in the third line and you change geographic to either Cartesian or spherical equatorial.
16:45
And you do the computation. So with Cartesian, this means that we'll take the longitude latitude and consider it as an xy. So it does not care about any spherical information.
17:01
So in spherical, you take the longitude latitude as they are on the sphere, and its geographic, it will use it on the spheroid. So I performed this computation to compute the minimum, the minimum Frézé distance. So this means given one trajectory I'm trying to find
17:21
in a set of 160 trajectories, what is the most similar one. And you can see here the difference in performance. So Cartesian is about more than five times faster. And with all of them, I'm getting the same results.
17:41
So from the whole data set, these are the two more similar. So yes, you can understand that the data set has a totally dissimilar trajectory. So in most of them, you cannot even draw them. So yes, using also Cartesian computations, which is a total symbol,
18:04
you can get the same result as in geography. So I guess if you exploit the whole data set and find much more similar trajectories, then Cartesian can give you a different result than geographic.
18:23
So you can take advantage of geographic computation. But even for filtering out a lot of dissimilar trajectories, you can do it just with Cartesian. So yes, this was all. Thanks.