Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • 19:48
    benjaminor commented #626
  • 15:11
    benjaminor commented #626
  • Nov 10 19:36

    awulkiew on develop

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

  • Nov 08 18:30
    yhenon commented #557
  • Nov 08 12:41
    deni64k starred boostorg/geometry
  • Nov 08 04:06
    Guuuuuum starred boostorg/geometry
  • Nov 07 22:58
    barendgehrels 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:54
    awulkiew closed #638
  • Nov 07 22:53
    awulkiew commented #638
  • Nov 07 22:53

    awulkiew on develop

    [sectionalize] Enable #include,… (compare)

  • Nov 07 20:32
    barendgehrels commented #638
  • Nov 07 20:09
    awulkiew milestoned #638
  • Nov 07 20:09
    awulkiew unlabeled #638
  • Nov 07 20:08
    awulkiew commented #638
  • Nov 07 20:05
    awulkiew commented #638
  • Nov 07 19:56
    awulkiew commented #638
  • Nov 07 18:44
    barendgehrels edited #638
  • Nov 07 18:43
    barendgehrels labeled #638
tinko92
@tinko92
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.
Adam Wulkiewicz
@awulkiew
@tinko92 Thanks for a reminder. I'll handle it.
Mats Taraldsvik
@meastp
Hi there - is there any support for the curved paths/areas in the SQL/MM-3 ISO Standard (CircularString, CompoundCurve, CurvePolygon) in Boost.Geometry? Current use case is intersection with CurvePolygons
Adam Wulkiewicz
@awulkiew
@meastp hello, no, currently there isn't.
Mats Taraldsvik
@meastp
@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.)
Adam Wulkiewicz
@awulkiew

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

  1. 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.
  2. 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_segmentbased on the tag of a geometry. Unless I'm missing something and it is possible to define a circular segment based on 2 points?

  3. 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.

Adam Wulkiewicz
@awulkiew
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.
Mats Taraldsvik
@meastp
@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)
Adam Wulkiewicz
@awulkiew
@meastp to be clear, what I meant was that in the circular geometry 3 points are used to define an arc so you should probably contain pointers/references to exactly these original points in the circular geometry.
Mateusz Łoskot
@mloskot
I'm also interested in the circular geometries in BG, but I have no time to allocate for that and offer any help in implementing it.
I will only be able to help in reviewing and testing.
So, big up for @meastp 's initiative :)
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.
Mateusz Łoskot
@mloskot

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.

Adam Wulkiewicz
@awulkiew
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.
Mateusz Łoskot
@mloskot
Thanks Adam
Mats Taraldsvik
@meastp
I see that this is pretty complicated, but I'll give it a go when I have time :)
Mateusz Łoskot
@mloskot
Yes, it is. I'd have expected to be able to hide the 3-vertex detail inside a dedicated strategies that are plugged in to provide algorithms with all the low level answers :)
tinko92
@tinko92
@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).
Mats Taraldsvik
@meastp
@tinko92 That's great. @awulkiew @mloskot What's the minimum functionality that you would accept into boost.geometry? I am trying to support a new circular_segment type, and trying to implement support for intersects.
Adam Wulkiewicz
@awulkiew
@meastp I'm not sure about the minimum functionality but if you're willing to add it to extensions first it won't be a problem.
Btw, what's the state of WKB? Do you think we should release it?
Mats Taraldsvik
@meastp
@awulkiew I'm not aware of any problems with WKB.
@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....?
Mateusz Łoskot
@mloskot
I'd start with basics like length, distance, perimeter, perhaps convex hull
Those are often used as steps of more complex algorithms
Mats Taraldsvik
@meastp
@mloskot Ah, got it - perhaps if I start with those, then create a PR, @tinko92 , I and others can cooperate on implementing (and perhaps I can get help when I'm stuck ? :)
Mateusz Łoskot
@mloskot
I will do my best to help
Mats Taraldsvik
@meastp
great, thanks :)
Mateusz Łoskot
@mloskot
... there are also envelope, centroid, area that I'd consider not too complex
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 ;)
Vissarion Fisikopoulos
@vissarion
@meastp I also think starting from envelope or length should be the entry point. areacould 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#617
In general let mw know if I can help too
Mats Taraldsvik
@meastp
@vissarion great, I'll try to implement those instead of intersects first :) (also, don't expect fast progress as I only have about an hour a week, but I hope to make steady progress :))
Vissarion Fisikopoulos
@vissarion
@meastp sure, I am just brainstorming here.
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
tinko92
@tinko92
@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.
tinko92
@tinko92

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.

Mats Taraldsvik
@meastp
@tinko92 sure, I'll fork Boost.Geometry and commit the changes in a branch there (currently, I only have the changes locally). :)
Vissarion Fisikopoulos
@vissarion

@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.

tinko92
@tinko92
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).
tinko92
@tinko92
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.
tinko92
@tinko92
@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.
Mats Taraldsvik
@meastp
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.
Mateusz Łoskot
@mloskot

@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.

tinko92
@tinko92
@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.
Mateusz Łoskot
@mloskot
@tinko92 I'm taken the liberty to reply in comment to the issue :)
tinko92
@tinko92
Hi, I don't want to spam Github with this, but I also want to state this to not look rude: I have not abandoned my random point PR, I've just been sick for a couple of days. I'll get back to it, once I'm well again. @awulkiew @vissarion
Vissarion Fisikopoulos
@vissarion
no problem, @tinko92, get well soon!