Geographic measures in Boost Geometry: length, area and beyond
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 |
| |
| Title of Series | ||
| Number of Parts | 295 | |
| Author | ||
| Contributors | ||
| License | CC Attribution 3.0 Germany: 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/43325 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
00:00
Series (mathematics)Sheaf (mathematics)Presentation of a groupProjective planeStreaming mediaGeometryMusical ensembleCAN busMereologyLibrary (computing)Lecture/Conference
00:50
GeometryOracleAreaGeometryMereologyEmailConditional probabilityPrice indexAlgorithmStandard deviationMeta elementComputer programmingElectronic mailing listSource codeLibrary (computing)Core dumpSoftware developerWebsiteRepository (publishing)Software maintenanceComputing platformFunction (mathematics)Revision controlOperations researchPredicate (grammar)Relational databaseIntegerComputer virusData modelSocial classSpacetimeImplementationExploit (computer security)NamespaceoutputSystem callLatent heatPhysical systemCurvatureHelixGoogle MapsSphereCoordinate systemCartesian productAxonometric projectionStrategy gameIterationApproximationSeries (mathematics)Symmetry (physics)DistanceAlgorithmGeometrySpheroidGeometryCoordinate systemLine (geometry)Software bugGoodness of fitSet (mathematics)Projective planeConnected spaceLibrary (computing)Different (Kate Ryan album)Finite differenceOpen sourceRevision controlCommitment schemeCodeLink (knot theory)Electronic mailing listInformationWeb 2.0Branch (computer science)Standard deviationCore dumpSubject indexingSoftware developerNumberFunctional (mathematics)Type theoryCategory of beingVisualization (computer graphics)MappingResultantComputing platformMetreAxiom of choiceLevel (video gaming)Message passingImplementationLengthDegree (graph theory)MereologyString (computer science)Envelope (mathematics)Point (geometry)Symmetric matrixStrategy gameSocial classNamespaceAreaMultiplicationOperator (mathematics)EmailState of matterEllipsoidTheory of relativityEndliche ModelltheorieNeuroinformatikParameter (computer programming)Primitive (album)Template (C++)PlanningCartesian productSummierbarkeitCASE <Informatik>QuicksortMassProcess (computing)Scaling (geometry)Machine visionDemosceneBitSinc functionVirtualizationTable (information)Level of measurementElement (mathematics)CausalityMultilaterationVideo gameFlow separationComputer programmingBit rateSurface of revolutionAuthorizationError messageSymmetry (physics)SphereContext awarenessSpacetimePhysical systemLatent heatSource codeComputer animation
10:01
Function (mathematics)Strategy gameStreaming mediaBinary fileGeometryPoint (geometry)Line (geometry)MultiplicationAreaSpacetimeState diagramData modelSystem on a chipRandom numberElectric generatorDiagramStudent's t-testOracleProjective planeStudent's t-testResultantRandomizationBitElectric generatorAxiom of choicePolygonDifferent (Kate Ryan album)WikiSpacetimeGrass (card game)outputUniverse (mathematics)MetreLevel (video gaming)Error messageAreaEllipseApproximationsalgorithmusLine (geometry)Strategy gameDeterminismPoint (geometry)Set (mathematics)Disk read-and-write headDistribution (mathematics)Software testingFigurate numberNeuroinformatikCommutatorMathematicsMachine visionTelecommunicationCondition numberDegree (graph theory)Combinational logicDistancePresentation of a groupNumberCodeGoodness of fit1 (number)Message passingUniformer RaumLogic gateIntegrated development environmentVoronoi diagramSystem callDefault (computer science)Black boxGleichverteilungSpheroidFreewareAlgorithmGeometryLibrary (computing)EllipsoidDistortion (mathematics)Order (biology)String (computer science)InterpolationCellular automatonPartition (number theory)Source codeComputer animation
19:11
CollaborationismWritingComputer fileComplete metric spaceArithmetic meanGeometryBitNeuroinformatikFunctional (mathematics)Projective planeFile formatShape (magazine)Library (computing)DistanceMultiplication signAlgorithmStreaming mediaSoftware developerSpheroidSurfaceImplementationTheory of relativityLinearizationJava appletNetwork topologyDifferent (Kate Ryan album)Reading (process)Object (grammar)VideoconferencingFundamental theorem of algebraLevel (video gaming)Line (geometry)CalculationMixture modelEntropie <Informationstheorie>Form (programming)Process (computing)Point (geometry)Right angleMeeting/Interview
24:01
GeometryMultiplicationLine (geometry)Point (geometry)Function (mathematics)Line (geometry)Parameter (computer programming)Point (geometry)Streaming mediaMetreDimensional analysisMedical imagingDistanceString (computer science)Real numberComputer animation
Transcript: English(auto-generated)
00:08
Hello, you are welcome for the afternoon section. We will have three presentations. The first presentation is Vissarion Physikopoulos who works on
00:24
a project Boost geometry for Oracle and I would like to ask all the presenters to use the microphone, otherwise the live stream watchers cannot hear you.
00:44
Ok, thank you. Thank you. So today I would like to maybe give some brief introduction on what we do in Boost geometry and maybe focusing more on measurements and ok, you will see. So what is Boost Geometry? It's a part of the
01:04
Boost C++ libraries. It's render only. It's following the 0.3 C++ standard but we have plans to go to some more modern one and it's heavily using template techniques like metaprogramming and tag dispatching for
01:24
performance reasons and it supports basically three basic parts like primitives which are the geometries, algorithms and the spatial index and it
01:41
follows the 0.3 C standards. Ok, so to get started, there is a documentation online, there is some mailing list that you can ask questions and the
02:03
whole code is available on the GitHub, on that link. So who is Boost Geometry? It's a branch of people that, it's the core development team. We are welcome to
02:21
contributions of course because open source project and we have contribution for a dozen of developers like we are participating the last three years in the Google Summer of Code and yes, there are more information in the web like credits and history of commit and whatever. So ok, so Boost Geometry is used by
02:46
MySQL for the whole GIS support. So after version 5.7, MySQL relies on Boost Geometry completely for the GIS and after version 6, it also provides
03:02
geographic support. So this talk is mainly focused on geographic support. So some post is that there are no home-grew set of GIS functions in MySQL, so everything is developed outside. Both projects are aiming in
03:21
OGC compliance standards and they have compatible licenses and MySQL can benefit from Boost Geometry being an open source project, so maintenance, bug fixing and also good Summer of Code, some examples. And ok, it's beneficial for Boost Geometry to be here only because there are no problems with
03:45
versioning and there are libraries in different platforms for MySQL. So this is a brief overview of the connection of those two projects. Now we're focusing on Boost Geometry, so there are plenty of algorithms implemented. Most of them are
04:04
in, all of them are in four Cartesian, so 2D geometries and most of them are also supporting spherical and geographic coordinates. So there are creation algorithms, algorithms that support compute properties or set and
04:27
relational operations. And in this talk we'll see examples of distance and some area calculations, so from this whole set of algorithms.
04:45
So these are visually some examples of area of computing the length of a line string. You can compute the envelope of geometry like a line string or multi line string. You can do relational set operations like intersect and occlusive
05:04
or symmetric difference operations. So these are some examples. And this is the first piece of code that you can start with the Boost Geometry. So you
05:21
just include some headers, header only and then there is a Boost Geometry namespace. And then you, this should have a lighter light, okay, then you define your point which for this example will be a double arithmetic, two
05:44
dimensional point with geographic coordinates with degrees. This can be radian and this can also be Cartesian and double is only for the example, this can be any number type. Okay, and we define two points. The one is Athens,
06:06
where I come from, and the other is the coordinates of Phosphor G. And we ask from the library to call the distance algorithm to compute the distance between those two points. Okay, and this is the result that we get in
06:22
meters and this visualization Google Maps with low quality. Okay, so some things about the design. There is a support from three level design. This is the namespace that we show and then there is a dispatch and detail namespace. So this pass contains the dispassing techniques and the classes
06:45
and detail hides the implementation details. Okay, so this is about the development and we distinguish between algorithms and strategies. This is important. The algorithms are template-free functions as the distance that you saw before and each algorithm performs a concept checking and calls a
07:06
dispatch class. So this is the inner details and what is important is that we have strategies that are algorithm specific for coordinate systems. So you can pass a strategy to, for example, distance algorithm and declare that how
07:25
this algorithm will perform on a specific coordinate system. So we'll see an example later. And okay, for now just let me list the possible coordinate systems. So the Earth can be a flat model like if you get it from a
07:43
projection. So here you, this is the geometry type that you can use, the Cartesian one. And then the other choice is to have a sphere, which is widely used. For example, Google Maps uses sphere. So this is how you call
08:04
this in boost geometry. It's a spherical equatorial. It can be parameterized either with a degree or a radian. And this is the geographic state of the Earth. So this model treats the Earth as an ellipsoid. And it can be
08:23
parameterized again as a degree or a radian. So boost geometry supports the three of them and there is also more complicated models that we don't support like geoid. Okay, so there are many strategies or way to, algorithms
08:44
to compute on different, even on the ellipsoid of revolution that I was talking before, the geographic modeling of the Earth. So we have many strategies that actually compute distances. So you can think like, think
09:03
it like this. So it solves some geodesic problem which is actually more or less distance computation. It's done in different ways that has to do with performance and accuracy. So some, the methods I list here has higher
09:20
accuracy and are less performant or the other way around. So we support all these kind of algorithms. This is still in pull request. And there's also a choice of do a projection and then compute it with Cartesian. Okay, so let's
09:44
turn back to the distance example. So we can give an extra argument to the distance function with a strategy. And here we say, we tell the algorithm distance to use this strategy. And this will give us a different result
10:03
because it's more accurate. Okay, for Athens Bucharest it will give a seven kilometer difference. But still it's something you can also from the example see that it's a different computation. Okay, so okay let me pass through
10:25
some other examples that illustrate how distance is involved in various geographic computations. So here we want to compute the distance between two polygons, again in a longitude latitude on the ellipsoid. So we have a
10:48
multi-polygon represents Greece and the polygon represents Romania. Okay, for this example I use just a single polygon. And we define the strategy
11:01
which is called a bit different. Okay, it's not maybe the best name but this strategy is to compute distance between geometries, not only points. And this parameterized with those strategies that we showed with Vinceti and Doyer
11:20
and so on and so forth. So I create this strategy and I pass it to my distance algorithm. And depending on the strategy or not, I have two different examples, two different results again. So this is the shortest distance between those two polygons on the ellipsoid. Okay, here just is two meters of
11:49
difference. Okay, so another example. So now I would like to compute distance, the shortest distance between multi-points or a point and a multi-point. So these
12:02
are two data sets, the green ones are the most populated places in the world and the red ones are airports. So I will do some test computations with those. So here I compute, okay this is again Bucharest and I compute the
12:23
shortest distance between Bucharest and all the airports in the world that are loaded from this file. And what I get is 6,000 meters. So I know if you are from here, is there any airport that listens? Okay, so for sure not
12:42
Autopen, so it should be something closer. So there is one in Google Maps. Okay, I tested that list. Okay, so then you can ask to have a different computation, like I want to compute the shortest distance between the set of most populated places in the world and airports and I get that
13:05
there is a pair of places, an airport and a populated place that are very close. So this is the distance. Okay, and all these computations are still geographic. So my points are geographic with degrees. So all this computation
13:23
has performed on the ellipsoid. So this means that we are supposed to be very accurate. Okay, so one other example, line interpolate points. This is an algorithm that also exists in PostGIS. So I define the line
13:42
string. These are places of my home, places of my colleagues and then I want to interpolate points on this line string. So in order to do this, I defined in boost geometry a line string and then I called the line
14:00
interpolate algorithm with this line string and this value of interpolation. So I want to interpolate point every 500,000, 500 kilometers and the result visually is this one. And this can be represented as a multi-point. Okay, this is again geographic and can be
14:23
also parameterized with a strategy. So I just show the simple call here with a default strategy. You can also add strategies here and make it more complicated, like more accurate or maybe faster and less accurate so
14:42
you can play with it. Okay, so the next example is about area. So we want to compute the area of Belgium. This is a very rough approximation of Belgium but it was useful just to copy paste it in a
15:00
simple example. Then you just call the area again and this should be parameterized again with the same kind of strategies that tells you how to compute closest points on the spheroid. So these are the different results that we get by using different strategies that are implemented
15:22
in boost geometry and you can visually see here that the difference is higher because it's a different algorithm. So the choice of the strategy is reflected in the result. So again, a bit closer, a smaller
15:43
polygon, so this is again in Brussels but it's a free university of Brussels, a place that the Fosdam venue is happening. So I would like to compute the area again and with the same computation I get
16:04
maybe a larger distortion in the results. So there is some discussion here on accuracy of those methods, especially if you use them inside
16:24
high-level algorithms. So area is using geodesic algorithms as a black box and doing more computation. So the possible errors are if you have an inaccuracy then you will see a different result at the
16:47
end by accumulating inaccuracies. So yes, I have a different talk on the subject of accuracy versus performance on those computations.
17:01
So this is more focusing on the library. Okay, so those are my last slides. This is this year's Google Summer of Code project. It was about random point generators and Voronoi diagrams to be implemented in boost geometry. The student was Tinko and we met him along with Adam.
17:28
It was I think a nice project. So I will show you just two pictures to illustrate it. So this is Germany and this is a random uniform,
17:42
random point generators from the uniform distribution from the area of Germany. And you can do this in all the geometry. So you can compute random points in a multi-line string or in a grid or in a
18:02
multi-polygon. So this is quite general. And then you can take the example the set of airports or all German airports and compute a Voronoi diagram. Voronoi diagram is partitioning the space where every cell is all the points that are closer to one input point
18:25
closer than all the others. So it's an intuitive partition of the space. And just a remark here, this code currently is only
18:40
Cartesian so this is a projection. All the other figures I showed you were on the spheroid. Okay, so we would like also to extend this to geographic Voronoi diagrams. Okay, and I
19:00
think that's worth my last slide. Thanks. Thank you for the presentation. I would like to ask anybody who has question wait for the microphone to be thinking about who
19:21
are watching the live stream. Okay, any question to the presentation? I'm curious what you do with the Z values in geometry when you transform them. Because some projections
19:43
use sea level, other projections use the relative surface of the spheroid. Here I'm in 2D. So there are no projections here. So the data are either 2D, so Cartesian so you
20:04
already have the projection, or it's longitude latitudes. I guess in projections we do what Prodsword is doing, right? We ignore the Z. And Prodsword is also ignoring? It depends.
20:34
Okay, but there is limited 3D support even in Cartesian, so not a lot of things. I suppose all the projection
20:42
supports 2D. The third D is from the mean, the elevation is from the mean sea level, which is not a plan at all. Okay, any other question? So on a bit of a tangent here, I noticed that boost geometry has support for reading shape
21:00
files. Are there any other formats supported besides shape files and WKT and how complete is? No. Is it? I think no. You don't have it. Yes, yes, this is quite
21:27
new. I don't know. Can you write shape files? No. It's only read. WKB. Yes, you can write also by now. Reading
21:43
of shape files. Okay, more questions? I have one question. What is the relation or differences between these Boost and Gauss, which is used by PostGIS? It's a
22:03
C++ library behind. Do you know what are the relations between these two developments? Yes, it's the Java topology
22:22
tool implemented. I know, but there are two parallel developments, so there is no collaboration. So as far as feature, development wise, the functionality is similar. So as far as I know, Geos does not do a lot of
22:45
geographic computation. Yes, let's say that as far as I understand, boost geometry is like a blend of functionality of Geos with geographic lib, and also
23:02
Mixer. So you can use the algorithms of Geos, that's as far as I know it's only for Cartesian, but with geographic lib functionality, which is for geography. So
23:22
you can blend both. Thank you. More questions? I'll try to be on topic this time. In the distance
23:40
calculation, maybe I missed it, but is there also something like linear referencing that you can really use the m values because you showed points along line, but this was a relative distance, I think. Or is it also with m values? What is your distance
24:11
parameter here that you use? All right, yeah, yeah,
24:23
okay, thanks. Okay, any more questions? The answer was captured by the livestream. So the distance
24:41
here is in meters, so you start from a point and you create points along the line after every 500 kilometers. And if you reach the end, you stop. No.
25:08
What do you mean the real distance? No, no, it creates points every, so if you have a line string or if you have a segment that it's 200, 2.4 kilometers,
25:29
then it will create one in 500, one in 1,000, 1,500, two, and it will stop. So you'll have three points plus the end points. No, no, no. But
25:51
I don't see the point, how you interpolate linearly in one dimension, actually. Yes, yes, yes,
26:03
it's only one dimension. Okay, thank you.