Boost.Geometry, Introduction And Examples
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 | 95 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/15513 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Production Place | Nottingham |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSS4G Nottingham 201313 / 95
17
25
29
31
32
34
48
50
56
58
68
69
70
82
89
91
00:00
AreaAlgorithmBuildingComputer programBriefträgerproblemGeometryPoint (geometry)Template (C++)Data modelData typeInformationLibrary (computing)Level (video gaming)EmailJava appletTopologySuite (music)SQL ServerWeightPolygonState diagramElectronic mailing listPhysical systemGroup actionRevision controlGeneric programmingTime domainPartial derivativeCovering spaceSet (mathematics)FrequencyExplosionCondition numberLimit (category theory)CombinatoricsMultiplicationRing (mathematics)CuboidStatement (computer science)Genetic programmingCASE <Informatik>Game controllerIncidence algebraComplex (psychology)Network topologySimilarity (geometry)Closed setStaff (military)GeometryLibrary (computing)Extension (kinesiology)Different (Kate Ryan album)AlgorithmEndliche ModelltheorieTerm (mathematics)Video gamePoint (geometry)Digital electronicsPresentation of a groupView (database)Multiplication signComputer programmingBit rateNumber theoryMultiplicationSoftware testingSemiconductor memoryRevision controlCondition numberMathematicsFrequencyMonster groupBitComputational geometryPay televisionRange (statistics)Boom (sailing)Slide ruleKey (cryptography)Type theoryUniqueness quantificationPairwise comparisonOpen setChaos (cosmogony)Buffer overflowSoftwareElectronic mailing listEmailMereologyScheduling (computing)Generic programmingProgrammer (hardware)WeightCodeSuite (music)Java appletLevel (video gaming)PolygonOpen sourceFreewareProcess (computing)Line (geometry)Stack (abstract data type)Template (C++)Physical systemInterface (computing)Server (computing)String (computer science)Ring (mathematics)Flow separationAttribute grammarComputer animation
08:16
Algebraic closureRing (mathematics)Orientation (vector space)GeometryInterior (topology)StrutGlass floatTrigonometric functionsLengthDistanceLine (geometry)Sample (statistics)Data modelPolygonGreen's functionFunction (mathematics)State diagramMotion blurComputer programPoint (geometry)Data typeVariable (mathematics)Cartesian productMultiplicationRevision controlString (computer science)CalculationSphereSineSystem callMaxima and minimaTopologySet (mathematics)Element (mathematics)Exclusive orOverlay-NetzLine (geometry)Game theoryDistanceAutomationPoint (geometry)Programmer (hardware)QuicksortRevision controlEndliche ModelltheorieComputational geometryLevel (video gaming)Multiplication signArithmetic progressionOperator (mathematics)BitFrequencyExtension (kinesiology)AuthorizationMedical imagingGreat circleReading (process)Dimensional analysisView (database)Electronic visual displayOcean currentSpectrum (functional analysis)CASE <Informatik>Compilation albumComputer programmingCentralizer and normalizerGeometryLibrary (computing)WritingOrientation (vector space)Internet service providerScripting languageVideo gameSphereFunctional (mathematics)Maxima and minimaLengthStrategy gamePolygonEmailFile formatCalculationMultilaterationGraph coloringCoordinate systemGeneric programmingArray data structureFunction (mathematics)Vector spaceOpen setData structureComputer animation
16:32
GeometryOverlay-NetzImplementationPartition (number theory)Point (geometry)Envelope (mathematics)Maxima and minimaCirclePrice indexNetwork topologyExecution unitSoftware testingVideo gameOrder (biology)WhiteboardSurfaceDistanceGroup actionPhysical systemCircleDecision theoryPoint (geometry)WordSimulationIndependence (probability theory)Control flowPlanningMenu (computing)Service (economics)Multiplication signLevel (video gaming)Graphics libraryQuicksortHost Identity ProtocolProcess (computing)Envelope (mathematics)MultiplicationSheaf (mathematics)Shape (magazine)Object (grammar)Subject indexingGame theoryPolygon meshCovering spaceBinary codeImplementationInternet forumGeometryBeat (acoustics)Library (computing)Semiconductor memorySynchronizationFitness functionPentagonBitExtension (kinesiology)Incidence algebraOperator (mathematics)State of matterProgrammer (hardware)Line (geometry)FrequencyComputer configurationPolygonCalculationAlgorithmMereologyType theoryBlock (periodic table)Roundness (object)Term (mathematics)Three-dimensional spaceSoftwareProjektive GeometrieTriangulation (psychology)Goodness of fitConvex setVotingBuffer solutionStrategy gameSerial portCuboidXML
24:48
Numerical digit3 (number)Interior (topology)GeometryGeneric programmingRule of inferenceSlide rulePlastikkarteTableComputer animation
Transcript: English(auto-generated)
00:00
to my presentation about Booge geometry. In the schedule it says that it is also presented by Mateusz Lozkot, but alas he could not make it because his girlfriend is pregnant and it is due in a few weeks. So he didn't want to leave his girlfriend alone for a whole week and that is totally understandable. So I will do it now on my own. This is
00:32
the first library, so this is C++ code. If you don't use C++ it is not really a problem because I will not really go into all the details. First some introduction, then I will
00:51
have a slide or two about the usage that is in C++, then a large number of slides about algorithms and some testing and community. Booge geometry contains algorithms for geometries.
01:13
In the next slide I have some comparable libraries. Many people know such a library and then you can place it better. It is based on generic programming.
01:24
It is not assuming things about your own program types. What are the key selling points, unique selling points? It requires no point model. It is also in comparison with other
01:40
libraries. You don't have to convert your point, you can just use your point or polygon. It is a lower level library and you can customize it and you have more control in certain aspects. We will also see that. And it is header only, so you don't have to link it or have complex linking things. It is all compiled and runs.
02:07
Comparable libraries, probably everyone knows the Java topology suite. It has already existed for a long time. That is in Java, in chaos. They have a similar, not exactly similar of course, but a similar interface and also the .net library which is also in SQL Server.
02:26
Or Seagull is also a comparable library, GPC, Clipper, there are more. We follow the standard library that is in C++. The library most programmers are using
02:43
containing a lot of useful stuff. And we are part of the Boost community, so we also follow Boost conventions of course. And OGC, our interface is based on OGC. That is open geodata spatial consortium. This is our team. I indeed took the initiative several years ago.
03:11
Bruno Lalande is from France. He now lives in the UK, but he could not be here too. Mateo Zoltschotz and Adam Bukovitz just this year joined too. And there are some
03:25
contributions from other people too. The community, we have an own Boost geometry mailing list. It is about 150 subscriptions, mail traffic nearly every day. There are also sometimes questions
03:41
on the general Boost mailing list. Actually, I didn't introduce Boost. Boost is for C++ collection of libraries that everyone can use. It's totally free. There's free SMBR. It's now GPL. They have an own software license. And they have a review
04:05
process. So it's not like SourceForge, where you can put everything in and know first you have to be accepted and then it's incorporated in the library. So many things about Boost. Boost has also a ticket system where you can file bugs. There's an IRC hangout.
04:27
There are also sometimes questions on Stack Overflow. So it's used more and more. In 1995, the history goes back already to 1995. I worked at Jordan at that time,
04:42
like some of the people here. And we had a library that was not based on templates. In 2008, we updated the library, modernized it and thought, well, that's suitable for open source. So we
05:00
did a preview for Boost and they seem to like it, but it still needs many changes. So we have four previews. And in November 2009, it was reviewed and accepted by the Boost community. After that, there were still some things to be done. So in 2011, it was for the first time
05:26
incorporated in Boost. And now it's there already. Each quarter or four months, there's a new version of Boost. And usually there are also updates of Boost geometry. The review period was, yeah, you can say heavy period with many mail traffic about
05:46
all opinions, etc, etc. In the end, there were 14 reviewers and most of them voted yes. So it was accepted in the several conditions. And they also especially liked the design, which we made. Bruno Lalande has also a special contribution to the design because
06:08
we arranged many things different as was in the first preview. The changes is to build it generic. We will see that there are many, many possibilities. We see that in the next slide,
06:24
to manage all those possibilities. It should be fast. It should also be robust, no floating point issues. And also limit the scope because geometry is a huge subject and you can build probably for all your life about in such a library. So you have to decide what's important
06:44
and at the same time also satisfy many users. So the basic concepts, these are OTC things, so open GIS, open geospatial. It's all about point,
07:02
a line string and a polygon. Or the multi versions, multi point, a multi line string, for example, a broken highway or a multi polygon. So these things belong together. For example, one attribute. Those are more or less prescribed by OTC. So we follow that.
07:23
So you miss here, for example, a circle, a ellipse, an arc. That's in some extensions, we have it, but it's not, at least not yet supported in the published library. So we follow the OTC conventions here. We have also some helper
07:42
geometries because a line string is built up segment. Yeah, we of course then also need to segment and a polygon is built based on ring. So we need a ring and we need the bounding box, et cetera. And OTC also has a multi geometry. That's a collection of different things.
08:02
There we call it different because we use boost variant, which can also be the same thing. It still type checked. So we call it a variant or a multi variant, or we don't call it, we use it.
08:21
In one of the first slides, we said we are agnostic with respect to many things. So we are, for example, agnostic with respect to orientation. A polygon can be clockwise or counterclockwise, and it can also be closed or open. For example, in the first version, it was not the case, but people said, well, we cannot use it because we have just the other
08:44
orientation. So we had to be agnostic about that. So we support both. Well, let's look at the basic structure. Who can program C++ so that such data can get an impression? Okay,
09:01
most of them can, or can a bit. So this is actually one of the key points of the library. You have your own struct. You don't have to define it for it. This is just an example. You have it already, probably, because most of the people who use GIS have their own
09:23
struct. So for example, the struct looks like this. Then you adapt that struct. That is explained, or not really in details, but it's explained later. And then you can just use it. So you can just use a standard vector, C++ vector, of those points, and use some
09:42
Busciamti stuff, and use the length of the line. So that is one of the unique select points of the library. You can use your own struct. And you can also use really old-styled C arrays for example, and calculate the distance of a vector to this struct. So these are two completely
10:06
different structs, but still they can be compared to the library. This is the whole program. This also illustrates that Busciamti, you can use this header only, so it's really lightweight.
10:20
You can use only a little bit of it if you want. So if you only need the distance, you can only use the distance, and you don't have a large library to link this. So you can only use only one or two things. Or you can do everything, of course, whatever you want. This is another example. It's somewhat more complicated. We have also our own models,
10:47
of course, because people can use their own point model, but to test only we have also our own point model, which we can use. So we have a polygon of our point model,
11:00
this is in two dimensions, with having X and I. We read the WKT, probably everyone knows that, and we support it, so that's handy for users, but also for ourselves to test with. This is broken here because it was too long for the slides. We declare a standard library
11:22
variable to get the output, and we compute the spatial intersection. And then we display it, but we usually do other things with it. So this is also a complete program. So this is what we saw. Well, most things I've already explained. Geometries can
11:42
be of any type, distance, any pair. The make thing returns a sort of constructor, but we don't accept. We can already output DSV, and that can be formatted more or less
12:00
in JSON format. I don't know if we have an example of that. We cannot yet parse it. It's a good question and a good idea to support that too. We have some ASCII formats, indeed WKT. We can write SVG, we can read and write WKB, but JSON is useful too.
12:27
So we provide our own geometries, a generic one. I showed XY, but we also have coordinate systems. This is Cartesian. We will come back to that later. Or already having xi or boost
12:45
tuples, which are also heavily used. They are now also in the standard library, in the new version of C++. Or while using xi, you can also have color points. So in red, green, blue, in a color cube, and can calculate color distances from it. This is also possible.
13:06
So let's start with distance again, because most programmers have at least once in their life programmed a function to calculate the distance between two points. So that's obviously
13:23
heavily used. But the generic distance function we have can also calculate the distance between a point and a polygon, and that's the shorter distance then. Check the time. And besides the Cartesian distance, we can also calculate the distance
13:43
over a sphere. As you probably know, the distance of the sphere is not really the shortest. It is the shortest, but not really a straight line. It's a great circle, so it's a curved line. And we can calculate the distance over that, or over the globe,
14:05
because the globe is not really a sphere, but a sphere-read. And we have different calculations. Five minutes, that's always already. I just took the time. It was
14:21
somewhat more, probably. The distance from Nottingham to Ballmer and Ballmer and Aurora. In different strategies, you get different distances. Now, what is the actual distance? Probably this one is most accurate, but it's also slower. So you can select whatever you wish.
14:40
Do you want a fast calculation, but less precise? Or a precise calculation, but less fast? I have to go. Well, I skipped this one. Well, for distance always programs usually leave out square roots, because this is very slow. And usually if you compare distances, this is not
15:03
necessary. So we can do that for Pythagoras, of course. But we can also do it for Herpersheim. And then it's also somewhat faster. So you have a fast distance over the earth. Well, the same here within. Pointing polygon, famous algorithm, but also you should determine
15:26
if a line is in a polygon or a segment, or a polygon in a polygon, or a polygon in a multi-polygon, or a point on a sphere inside a polygon. Because if it's really somewhere here or so, then you cannot use the straight lines. You really have to use the sphere.
15:46
Simplify. This is not an OGC algorithm, but we support it using Dupless-Poyker. It makes a complex form simpler. So you specify a maximum distance, for example this distance,
16:05
and the line which had originally, for example, 500 points, after that has about 10 points or so. And we can also specify strategies. You can have, for example, not the distance, but a maximum of points. So it's a bit lower level, if you want.
16:29
We have also the overlays, booleans, as they are sometimes called. So if you have two polygons or a polygon, multi-polygon, then you can calculate the intersection. It also works
16:41
for polygon and a line string, or both together, or one but not in the other, or in one of them but not in both. We can also calculate those. The implementation is probably...
17:01
Say something else... About performance. Internally, we have a spatial index now, in short. But internally we use partitioning. So if you have two multi-polygons, one green, one blue,
17:21
we first divide, and you can calculate the intersection points between the two, we first divide it in two, and then we have three groups, one left, one right, and a group of all crossing polygons, and they should be matched with two. So you make it now simpler
17:41
and faster, and we continue that in the horizontal level, for the second level. It's a bit like quadtree, but not exactly like that. We continue dividing the parts until we have a reasonable amount, for example four, it's specifiable, or six, or twelve,
18:04
and then we compare all together. And the group following in both boxes is always compared to both of them, of course. And then the intersection points, for example, can be calculated much more easily. It doesn't work only for intersection points,
18:24
but it's also a generic algorithm, so you can also use it to assign things, or to do other things with that. Besides partitioning, we have also internally sectionalizing, and that breaks the polygon up in monotonic sections.
18:44
So this is one section, so if you are here, you've only to think about that part, and forget the rest of the polygon, because that's outside your scope at that moment.
19:00
It's now exactly 20 minutes, no? It can be used together with the spatial index, but it's not part of it, so it's more or less independent.
19:23
Well, we have some algorithms, this is one of the last slides, we have point properties, so the centroid, or generate any point on the border, that can be sometimes interesting, or generate any point on the surface, but it should be inside the polygon, the centroid is not always inside the polygon, as you probably know,
19:41
or generate the convex hull, so that is a convex polygon exactly fitting among the polygon, or the envelope, or the minimum bounding circle, and this is not yet implemented, therefore it's cursive, and the votes were now to call that also envelope,
20:03
because, well, the return type only defines, makes the distinction already, so it can also be a circle. Circle is now an extension, so this is not already there. And this is also in progress, but it's showing how the buffer will look like,
20:24
because we can specify a distance strategy for left and right, so such that we support asymmetric distance, and also the end strategy, so such that we have straight borders, or I don't know how they're called, block borders, or round borders, and also specify the joint strategy,
20:44
so such that we have round corners, or sharp corners, or you can specify your own strategy, for example doing things like this, if you want. So that's the lower level part of the library, I said this already,
21:02
and special index is now there, so that well fits the library, because we have the same, we use the same words, and of course it uses the library, and so we have a special index library, which can be built up with many polygons, or lines, or multiple lines, or points, and asks for intersection with the box,
21:25
so if it's intersect, or if it's disjoint, or covered by, these are all OGC terms within. And one about lower level, so this is the distance,
21:42
but we have also distance info, which will be released, which doesn't only give the distance back from a point to a line string, but also the point of, the projection point, which is often asked for, and also on which segment it lands, and the distance between that segment,
22:01
and for a polygon it does the same, but also says, well this one is inside, but still gets the distance back. Are there already questions? Yeah, a few minutes. A few minutes, short questions, short answers. I understand that this geometry is a generic library,
22:22
so there are lots of types for geometry, but sometimes you just want one type, to form some generic calculation. So you serialize it, do some calculations, serialize it back, you don't want these different types. Is there something you can do with BoostGeometry?
22:42
We don't convert, we support many point types, but we don't convert, we adapt. So you just have your own point type, and you can use, you have to write on a sort of traits adapter, and you can use BoostGeometry. So there's no need for serialization or deserialization.
23:02
I don't care if it's a polygon or a line string, can I work with it just as one type? That's the variant then. So it's type-erased? It's not type-erased, that's the Boost variant. I don't think it's type-erased, you have options for it.
23:23
Two questions, one is what's license of that, another is a more technical one, do you plan to support more complex objects also, like 3D meshes and this kind of triangulation? Yeah, good questions. Boost has its own license, it's a Boost software license.
23:41
It's very open, so you basically can use it everywhere, commercial or not commercial, binary forms, even without mentioning the Boost license. So the license is quite open. And yes, we are planning to support more features, for example those circular features or ball and three-dimensional.
24:04
The design of the library supports three-dimensional, and we have also some algorithms, for example distance, but many algorithms are not yet implemented in 3D. And triangulations and meshes are mentioned.
24:20
There are no immediate plans, but I think it's often asked, so I think it will be planned too. Sorry, but I'm going to have to do a short question or a short question. Last question, are you running away after this? Can we ask more questions after this? I'm running away, sorry? Are you going to be asking more questions after this?
24:40
Yeah, you can be asking more questions, sure, yeah. Oh, and the last slide, I have my own, I had many more slides. Okay, I will give you my card.
Recommendations
Series of 8 media