Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • 18:35

    awulkiew on develop

    [distance] Add support for DG/G… [algorithms] Fix too long line … Merge pull request #922 from aw… (compare)

  • 18:35
    awulkiew closed #922
  • 17:45
    awulkiew synchronize #922
  • 14:26

    awulkiew on develop

    [self_turns] Pass AssignPolicy … Merge pull request #914 from aw… (compare)

  • 14:26
    awulkiew closed #870
  • 14:26
    awulkiew closed #914
  • Oct 15 15:22
    vissarion synchronize #923
  • Oct 14 20:00
    vissarion synchronize #923
  • Oct 14 15:00
    vissarion synchronize #923
  • Oct 14 09:00
    vissarion synchronize #923
  • Oct 13 13:12
    barendgehrels commented #918
  • Oct 13 13:10
    barendgehrels review_requested #924
  • Oct 13 13:10
    barendgehrels review_requested #924
  • Oct 13 13:10
    barendgehrels opened #924
  • Oct 13 07:08
    barendgehrels assigned #918
  • Oct 13 07:08
    barendgehrels commented #918
  • Oct 12 20:09
    awulkiew labeled #919
  • Oct 12 19:05

    awulkiew on develop

    [strategies] Fix area strategy … Merge pull request #915 from aw… (compare)

  • Oct 12 19:05
    awulkiew closed #915
  • Oct 12 19:03

    awulkiew on develop

    Fix c++20 compilation errors re… [convex_hull] Fix compilation e… Merge pull request #921 from aw… (compare)

Ayush Gupta
@ayushgupta138
Hello everyone, I am Ayush Gupta, a sophomore at Indian Institute of Technology, Roorkee. I have a good understanding of C++ and metaprogramming principles. I have gone through the boost geometry repository in some detail, but for some better understanding and for contributing to this community, some projects would be better. So could some of the mentors suggest some assignments or mini projects?
Ayush Gupta
@ayushgupta138
@vissarion @awulkiew @mloskot ?
Mateusz Łoskot
@mloskot
@ayushgupta138 https://github.com/boostorg/geometry/issues?q=is%3Aopen+is%3Aissue+label%3Agood-first-issue
or just find a project yourself, what interests you, what fits your skills and knowledge, ... if you can not motivate yourself, nobody can
tinko92
@tinko92

Hi, I have some follow-up questions/comments regarding rtree queries, and I'd be interested in comments.

For a recent application of the rtree at my work (the same that could use the infinite frustum query), there would be utility in having a version of index::satisifies that takes part in the traversal. As @awulkiew mentioned, this is currently not the case and I understand it can't be done generally, but I think it can be done and have utility for some categories of custom queries.

E.g., consider a large space of geometries, some percentage of which (which also tend to be cluster close to each other), are red. Querying a box in that space for red objects would require linear search over all elements in the query box, even if none of them is red. If internal tree nodes had, aside from the bounding box of their children, some representation of whether some or none of the children are red, that query could skip entire subtrees.

More generally, I think this could be provided for user-defined index data that can be aggregated with, e.g., operator|= and compared in leaves with operator==. I understand that there are ways to achieve some of this with the current implementation. I could use an extra rtree for the red geometries, but I am not sure how well that scales for more complicated custom queries. Or I could add an extra spatial dimension and set it to 1 for red geometries, but I think that would change the results of k-nearest queries in an unintended way. I do not know how treating this field would affect the structure of the tree, maybe it would be beneficial if it makes the tree consider the value in the extra dimension in the decision for grouping nodes into subtrees.

I do not know what other applications that use the rtree look like, so I would be thankful for comments on whether custom index data like that could be useful as a general interface, from people that have more insight into it.

Adam Wulkiewicz
@awulkiew

@tinko92 In such case the additional information would have to be stored in the internal nodes aside from the bounding box and this information would have to be calculated during the creation of the R-tree (so balancing and packing). There was a user in the past asking about it. He wanted to store planets or stars in the R-tree and to speed up the query hold the information about the total mass or some other quantity related to the objects represented by a region defined by an internal node. So yes, custom nodes + their creation and custom query using this info would be something that could be useful for sure.

Something like this could be done even now but it would be complex (and the internals of the r-tree are not documented). Internally r-tree is implemented more or less like a GIST. It is possible to define your node type, the ways how this node is created/destroyed, various balancing algorithms, etc. and all of these things are then chosen by the compiler based on tags when certain parameters are passed (e.g. these are the options for index::linear<>: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp#L65-L75). AFAIR besides packing algorithm because this is always the same right now.

Are you asking because you'd like to use it at your work or because you consider this as a potential project for GSOC?

tinko92
@tinko92
@awulkiew I am asking mainly because I would have utility for this at work, although it is not something that I would have time to implement immediately (I have some Pull Requests to attend to before that). I am not eligible for GSoC but I am aware that it is coming up, so I also have it in mind when thinking about potential library extensions.
tinko92
@tinko92
But my knowledge of the rtree (I haven't looked too deeply into the code) is insufficient to judge whether it would be a good project idea and because this year's GSoC is only half as long as in the years in which I participated (AFAIK) it would be even harder for me to judge. It doesn't sound like it would require implementations of algorithms that are overly complicated but I imagine that designing a future-proof interface could take a lot of thought.
Adam Wulkiewicz
@awulkiew

You are correct that all of the algorithms are implemented and that the interface would be the most complex part.

But to give you some idea I think that this should be implemented as a more generalized version of the rtree, let's say bounding_tree or similar. So a tree created bottom-up allowing to define any bounding geometry (spheres, oriented bounding boxes, variants. etc.) and additional data stored in the internal nodes. Maybe even allowing to define the exact type of an element stored in the internal node. Then the r-tree would be implemented on top of that.

Aside from user-defined spatial queries it would also be possible to implement user-defined knn queries. E.g. AFAIR there is an experimental version of "path query", i.e. a knn query returning the k nearest values intersecting a linear geometry which could be interpreted as first object hit by a ray or first object found on a driving path or a river, etc. So knn queries could be generalized too.

I'm also not sure if this is a good idea for a GSoC project. I'm only asking because you mentioned GSoC before.

tinko92
@tinko92
Thanks for the ideas. It sounds interesting and useful (I think, a hit-by-ray-first query could also have utility in my usage of the rtree) but also like a bigger undertaking than I had originally in mind. I'll think about it (later).
Ayush Gupta
@ayushgupta138
are project ideas for gsoc 2021 published for boost geometry? I was only able to see project ideas for previous years.
Mateusz Łoskot
@mloskot
None at https://github.com/boostorg/wiki/wiki/Google-Summer-of-Code%3A-2021
Students are free to suggest projects of their own interest though
Mateusz Łoskot
@mloskot
By the way, the project has mailing list
Siddharth Kumar
@Siddharth-coder13
Hello mentors, I have proposed a new project for GSOC 2021, https://lists.boost.org/Archives/boost/2021/03/251051.php
@mloskot @vissarion I would like to discuss about the project, if this one sounds good.
Mateusz Łoskot
@mloskot
Three words: search web first
Ayush Gupta
@ayushgupta138
is there any slack channel for boost geometry?
Mateusz Łoskot
@mloskot
No, but there are #boost and #boost-user and #boost-gsoc
Siddharth Kumar
@Siddharth-coder13
Hey @vissarion, here is my proposal draft as suggested by you https://docs.google.com/document/d/1NJ6MYRphIHJNizQqQoKYxCOijkFh6STIIAUgP98jafs/edit?usp=sharing it would be great if you provide some feedback.
Vissarion Fisikopoulos
@vissarion
thanks for sharing @Siddharth-coder13
shadymohamedamin
@shadymohamedamin
Hello all, I am Shady, Faculty of Engineering, Department of Computer Engineering, and I want to participate in the Google Summer of Code Boost Organization, so I need some suggestions about how I begin and what is the issue and buggs that i will begin with it to solve it?
Thanks
I am very interested in participating in google summer of code
shadymohamedamin
@shadymohamedamin
I have working and practical experience working in C,C++, Python, dart,matlab,prolog, etc. with knowledge of mathematical concepts like Linear Algebra, discrete math , . etc. I am interested in contributing to Boost and apply for GSoC. Will be highly grateful for guidance on beginning processes in contributing to Boost.
@vissarion @awulkiew @mloskot
Mateusz Łoskot
@mloskot
@shadymohamedamin Search the web, read archives of this channel, mailing lists. Surely, you can't be the only one who asked such questions lately
Ayush Gupta
@ayushgupta138
Hello everyone,
I wanted to know about the implementation of Polyhedral surface in Boost.Geometry. Since my GSoC 2021 project proposal is based on Polyhedral surfaces, I wanted the know the interface and implementation of the same. Since there are not much details in https://portal.ogc.org/files/?artifact_id=18241, should I assume the implementation to be more or less as in https://doc.cgal.org/latest/Polyhedron/index.html ? It would be really helpful if someone could provide some material on Polyhedral Surface interface.
Ayush Gupta
@ayushgupta138
@mloskot @vissarion @awulkiew?
Mateusz Łoskot
@mloskot
Mateusz Łoskot
@mloskot
The OGC spec and SQL MM spec and PostGIS implementation is also a good place to look at
Ayush Gupta
@ayushgupta138
As per the https://postgis.net/docs/manual-2.0/ST_GeometryN.html , a polyhedron is defined as a set of 3d planar polygons. But unlike polygon, a polyhedron cannot be represented only as set of 3d planar polygons. For example, their incidence relation also has to be specified, which could be inferred in the case of polygons from the point order.
Ayush Gupta
@ayushgupta138
@mloskot @vissarion please correct me if I am wrong.
Mateusz Łoskot
@mloskot

A PolyhedralSurface is a simple surface, consisting of some number of Polygon patches or facets. If a PolyhedralSurface is closed, then it bounds a solid.

If you read the OGC spec you should find more answers

From The PostGIS in Action book at https://livebook.manning.com/book/postgis-in-action-third-edition/chapter-2/v-15/36

Float a bunch of polygons in three-coordinate space and glue them together at their edges, and you’ll form a patchwork referred to as a polyhedral surface. Although polygons make up both multipolygons and polyhedral surfaces, there is one fundamental difference: polygons in multipolygons can’t share edges; polygons in a polyhedral surface almost always do. There are two other notable restrictions in the construction of polyhedral surfaces: polygons can’t overlap, and each edge can be mated with at most one other edge.

Vissarion Fisikopoulos
@vissarion

But unlike polygon, a polyhedron cannot be represented only as set of 3d planar polygons.

Does that mean that if the user gives a set of polygons in 3d space then this could correspond to more than one polyhedral surface?

Mateusz Łoskot
@mloskot
It's worth to note, Polyhedral Surface is not necessarily a Polyhedron
Vissarion Fisikopoulos
@vissarion
Thanks @mloskot let me add this page https://jeffe.cs.illinois.edu/compgeom/ it is quite old but packed with useful information
Mateusz Łoskot
@mloskot
:thumbsup:
Siddharth Kumar
@Siddharth-coder13

It's worth to note, Polyhedral Surface is not necessarily a Polyhedron

Polyhedron is a special case of polyhedral surfaces when it is closed.

Mateusz Łoskot
@mloskot
@Siddharth-coder13 Yes, it's important to agree on definition of the Polyhedral Surface first, then dive into special cases.

However, my point was that @ayushgupta138 comment here :point_up: March 22, 2021 4:59 PM suggested he is misunderstanding the difference and using Polyhedral Surface and Polyhedron interchangeably, what is wrong.

Why I think @ayushgupta138 mismatches these two?
Because the page he referred https://postgis.net/docs/manual-2.0/ST_GeometryN.html does not even use word 'Polyhedron', but he is asking his question about Polyhedron referring to that page.

IOW, communication needs to be precise to avoid side discussion on what is what.

Siddharth Kumar
@Siddharth-coder13
👍
Ayush Gupta
@ayushgupta138

However, my point was that @ayushgupta138 comment here :point_up: March 22, 2021 4:59 PM suggested he is misunderstanding the difference and using Polyhedral Surface and Polyhedron interchangeably, what is wrong.

Yes, I used polyhedron and polyhedral surface interchangeably and it was my fault for doing so. Thanks to @mloskot and @vissarion the difference is clear to me now.

shadymohamedamin
@shadymohamedamin
I want to contact with the mentors (david bellot and cem bassoy)
Boost.ublas
And i want the irc channel to discuss the project with them
Very thanks ♥️
@mloskot
Mateusz Łoskot
@mloskot
@shadymohamedamin First, you want to learn how to search the web. There are materials and instructions that address your questions, on Boost site, wiki, mailing list archives.
Brett McDonald
@bfmsoft
OK, been 35 years since took geometry ;) here is my problem. cx,cy is starting point and dx,dy is destination point. Circle is centered on cx,cy with radias r. What is the equation to file the point the line from cx,cy to dx,dy that intercepts the circle? I want the x,y of the intersection point.
Adam Wulkiewicz
@awulkiew
@bfmsoft If your line starts at the center then what you really want is to get point at distance r into the direction of D. So with vectors this will be: C+(D-C)/|D-C|*r, where C is point (cx, cy), D is point (dx, dy), (D-C) is vector from point C to point D, |D-C| is the length of this vector and (D-C)/|D-C| is this vector normalized (it has length 1). So if you multiply this vector by r then you get a vector of length r having the same direction as your line.