- Join over
**1.5M+ people** - Join over
**100K+ communities** - Free
**without limits** - Create
**your own community**

Discuss Boost.Geometry (Generic Geometry Library) - https://github.com/boostorg/geometry

- 19:48benjaminor commented #626
- 15:11benjaminor commented #626
- Nov 10 19:36
awulkiew on develop

[test][arithmetic] Replace std:… (compare)

- Nov 08 18:30yhenon commented #557
- Nov 08 12:41deni64k starred boostorg/geometry
- Nov 08 04:06Guuuuuum starred boostorg/geometry
- Nov 07 22:58barendgehrels commented #638
- Nov 07 22:55
awulkiew on master

[sectionalize] Enable #include,… Merge branch 'develop' into bg-… Merge branch 'bg-prepare' (compare)

- Nov 07 22:55
awulkiew on bg-prepare

[sectionalize] Enable #include,… Merge branch 'develop' into bg-… (compare)

- Nov 07 22:54awulkiew closed #638
- Nov 07 22:53awulkiew commented #638
- Nov 07 22:53
awulkiew on develop

[sectionalize] Enable #include,… (compare)

- Nov 07 20:32barendgehrels commented #638
- Nov 07 20:09awulkiew milestoned #638
- Nov 07 20:09awulkiew unlabeled #638
- Nov 07 20:08awulkiew commented #638
- Nov 07 20:05awulkiew commented #638
- Nov 07 19:56awulkiew commented #638
- Nov 07 18:44barendgehrels edited #638
- Nov 07 18:43barendgehrels labeled #638

Hi, quick question, this is unrelated to GSoC, but since the 1.71 deadline is approaching, I'd be very thankful if anybody could take a look at #584 (Pull Request). We use it in our codebase it is a slight implementation change for the matrix_transformer strategy that allows it to work for arbitrary dimensions (rather than just 3 to 3, 3 to 2, 2 to 2) and allows composing of transformers across dimensions. A test case is included.

@awulkiew can you suggest how I would add support for these types and bg::intersection? (e.g. 1. implement circularstring, compoundcurve and curvepolygon concepts 2. implement bg::models for them 3...n ??? -> what else to implement to be able to use bg::intersection for them? Also, I guess calculation operations with circularstring etc. requires a parameter for how many points to approximate the arc?)

to be clear: As a first step, I would appreciate the minimum work required to make bg::intersection work for these types/concepts.

(e.g. I have already implemented a circularstring concept locally, but, as it consists of three points, it does (only) work for converting to WKB, where these three points are the only thing required.)

@meastp Separate models for them are the most straightforward solution indeed. Besides of that:

You have to implement all strategies that are used in intersection, strategies calculating:

- intersection of 2 segments
- whether a point is inside polygon
- on which side of a segment a point lies
- area
- envelope and expand for circular segments
- checking if box disjoints circular segment
- possibly some other ones...

Many strategies would stay the same, e.g. regarding point/point and box/box operations.

The problem I see is that internally we're considering segments as defined by 2 points, but in this case a segment is defined by 3 points. So I'd expect it to be an issue. You'd probably need some kind of thin wrapper around 3 points defining a segment between 2 first points. And this

`circular_referring_segment`

should be passed into the utilities/strategies in algorithms instead of e.g. 2 points or linear segment or`referring_segment`

. So you'd also need some utility returning regular/linear`referring_segment`

or`circular_referring_segment`

based on the tag of a geometry. Unless I'm missing something and it is possible to define a circular segment based on 2 points?If the above fails and parts of circular segments cannot be represented as described above you'd have to write new versions of algorithms for these geometries as well as strategies.

But I think it should be possible to do it with 1 and 2. You could start with something simpler than intersection of 2 polygons. E.g. `relate(point, polygon)`

which needs less strategies. Or even `area(polygon)`

which needs only 1 strategy and you could straight away test if you need a separate algorithm or would `circular_referring_segment`

be enough.

If you define a separate tag for your geometry, e.g. circular_polygon_tag and call an algorithm the compiler should complain that the dispatch::algorithm is not implemented for this tag. Then you have to make a decision whether reimplement an algorithm or simply write dispatch for your tag and derive from the old implementation.

Then the compiler will start to complain about default strategies not implemented (or maybe first it will complain about that). At that point you have to implement them as described above.

@awulkiew thank you for the thorough description :) I agree with you that only 2 points isn't sufficient to represent an arc - three points or two points + radius is needed (and I think three points is the better option because tiny rounding of floats makes 2 points + radius fluctuate)

I see @meastp follows SQL MM/OGC terminology what is good as it helps t o have such common reference when discussing or reviewing BG against existing implementations like PostGIS or SQL Server.

Regarding the number of points in circular :point_up: July 15, 2019 7:37 AM

AFAIK, only requirement is that `CircularString`

has odd number of points, so it is composed from connected 3-point arc segments

- 3-points means it is single arc
- 5-points it is two arc segments
- 5-points with 2nd in middle of 1st arc and 4th in middle of 2nd arc compose a circle

etc.

Sorry if I wasn't clear enough. I wasn't talking about representing circular segments in a geometry like circular string. I was specifically talking about representing a segment internally in algorithms. E.g. when you pass them into the intersection strategy deeply in set operation. Now we assume that a segment is defined by 2 points, we take them directly from geometry, passing pointers/references into referring_segment and passing the 2-point segment into the intersection strategy. We then assume/expect that the result of the intersection of 2 segments is either 0 or 1 point unless they are collinear when the number is 2. But with circular segments both of these assumptions/expectations are not correct. It's because the shape of a segment between any two points is defined by a third point (and in general case like bezier curves probably more points around) either before or after a pair of points and because of the non-linear shape the number of intersection points of circular segments may be 0, 1 or 2 even if they are not collinear. And this means that at least some parts of the algorithms should be modified as well.

@meastp Hi, you may count me among those who are interested in CurvePolygon. The codebase at my job has demand for that kind of geometry and maybe I can contribute to that during work hours in the future. More specifically, we would have demand for that in 2D, cartesian coordinates and we would probably use the algorithms area, envelope, within (point in CurvePolygon) and intersects (CurvePolygon and CurvePolygon).

Btw, what's the state of WKB? Do you think we should release it?

@tinko92 I think you are much more familiar with the code base than I, but I have started with tiny baby steps to try to get familiar, create tags, concepts and models for circular_segment and circularstring. What is a good algorithm to start implementing, to get familiar with the strategies architecture? I'm currently trying intersects, but there are a lot of algorithms behind it....?

Those are often used as steps of more complex algorithms

Starting with such simple self-contained algorithms will confirm the new circular types are recognised as geometries, make it easier to review,

before jumping to complex behemots ;)

before jumping to complex behemots ;)

@meastp I also think starting from

In general let mw know if I can help too

`envelope`

or `length`

should be the entry point. `area`

could also be not that difficult (maybe replacing the determinants in shoelace formula with the area under the circular arc), for `centroid`

I am not sure, but those are a good start. The side predicates are implemented by @tinko92 here: boostorg/geometry#617In general let mw know if I can help too

The

`convex hull`

should be as (or simpler than, because the arcs are sorted) the one for the union of circles, see for example https://hal.inria.fr/inria-00074391/document
So computing the intersection is algorithmically much simpler but the code in boost geometry is maybe too much to start with

@meastp I will look into this too, after finishing work on some branches I try to get merged. Will you work on this on your fork of Boost.Geometry? Then I'll know where to look for that. Also thanks for thinking I'm familiar with the code base ;) Incidentally, just after I read that, I noticed that I unknowingly reimplemented an existing algorithm. I will familiarize myself with the implementations of algorithms for polygons and I'll try to think about, how some of that can be done for CurvePolygon.

Speaking of which, @vissarion my implementation of uniform point distribution for LineStrings caches intermediate lengths and segments so that a single point can be interpolated in logarithmic, rather than linear time using binary search over the accumulated lengths. I now use line_interpolate for generating the point on a single segment now.

Do you think it would be sensible to make that caching in some way an option for line_interpolate for the benefit of users who repeatedly interpolate single points with varying max_distance over the same LineString? I am asking because I do not know what this algorithm is generally used for.

@tinko92 regarding caching I do not know of any particular use case for `line_interpolate`

I just implemented since it seems useful in GIS and there are many implementations of it in various libraries (`PostGIS`

included). But since you have already implemented I think it doesn't harm to add this functionality to `line_interpolate`

as long as it does not overcomplicate the user interface.

Regarding uniform points generated on a linestring, thanks for sharing your approach. I haven't reviewed your PR yet ;) An alternative would be to generate random numbers in [0,len] (where len := the length of the input linestring) sort them and then simply parse/navigate on the linestring by creating points in distances from the sorted list. That should be more efficient, as far as I can see.

Hi @vissarion , thanks for your thoughts. I look forward to discussing this during the review. Regarding ordering random numbers: This can probably be faster in some use cases, I think the asymptotic time complexity should be in O( n * log(n) + m ) with O(n) auxiliary space where n is the number of samples and m is the length of the LineString.

I think my approach is in O(m + n * log(m)) with O(m) auxiliary space, so it depends on whether n is larger than m.

The issue, though, as far as I can see, is that this is incompatible with the current interface, which is modeled after the random distribution classes in Boost.Random, where samples are always generated one at a time (at least as far as the distribution interface is concerned).

I think my approach is in O(m + n * log(m)) with O(m) auxiliary space, so it depends on whether n is larger than m.

The issue, though, as far as I can see, is that this is incompatible with the current interface, which is modeled after the random distribution classes in Boost.Random, where samples are always generated one at a time (at least as far as the distribution interface is concerned).

Hi, after listening to some CppCon 2019 talks, I had a look at the new C++20 Concepts feature. In some far future (I'm sure C++20 will become available to RHEL users around 2026), this may be interesting for Boost.Geometry, and maybe other Boost libraries. Since Boost.Geometry is a library that already defined concepts long before they were a C++20 feature, I tried it out with the point concept. If that is interesting to you, you can find the gist (~2 pages including explanation) here: https://gist.github.com/tinko92/163d55200d1a704ba4bfca557de3575a . I cannot guarantee that this is correct but with the things I tried, it behaved as I hoped.

@awulkiew Is there a general position on the use such of new language features, maybe hidden behind Macros like in the examples at https://www.boost.org/doc/libs/1_71_0/libs/geometry/doc/html/geometry/reference/models/model_ring.html with BOOST_NO_CXX11_HDR_INITIALIZER_LIST? I'd generally be interested in checking out, how static concept checks could be improved with C++20-features, but I wonder if you think this could potentially be merged if done properly or whether that's unlikely.

Another potential useful feature from C++20 (or, perhaps, a range-library) is Ranges. I have adapted a geometry model which is both pointer-based and uses shared geometry (i.e. polygon exterior is not a ring of points, but a ring of linestrings that might be used in other polygons as well). The adaption today uses iterators, and I think it might be simpler to write it using range-views and range-for_each to flatten the hierarchy into a range of points which boost.geometry expects.

@tinko92 & @meastp AFAIK, there is no plan to jump as far as C++20, not even C++17. The furthest stride that is being contemplated is C++14 but C++11 is currently a more likely option.

I'd suggest you to review and join the discussion here #590 and/or discuss details on the Boost.Geometry mailing list.

Gitter is not the best place to discuss important plans about the library future, as it is not monitored as well as the mailing list or GitHub and, most important, it is not properly publicly archived.

@mloskot thanks for the pointer, I responded to that issue. Just for clarification, I am not seeking to contribute something that makes the library depend on C++20, I was thinking about something that improves error messages if C++20 is available but doesn't break things if it isn't. And I'd understand if there were problems with that as well, like CI not covering that code. But I look forward to a possible response in #590.