Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • 09:55
    vissarion commented #934
  • 09:52
    vissarion commented #933
  • 03:51

    mclow on boost-1.78.0

    (compare)

  • Dec 06 17:18
  • Dec 02 23:44
    n4z4m3 starred boostorg/geometry
  • Dec 02 20:29
    mgatc starred boostorg/geometry
  • Dec 02 14:59
    vissarion synchronize #939
  • Dec 02 14:56
    vissarion commented #939
  • Dec 02 14:53
    vissarion synchronize #939
  • Dec 02 14:46
    audrew commented #657
  • Dec 01 16:34
    Zorkimer starred boostorg/geometry
  • Dec 01 15:10

    vissarion on develop

    [closest_points] Add missing in… (compare)

  • Dec 01 14:57
    vissarion synchronize #933
  • Dec 01 14:50

    vissarion on develop

    Closest points for cartesian wi… Add closest_points pl-pl tests … Merge branch 'develop' of https… and 18 more (compare)

  • Dec 01 14:50
    vissarion closed #923
  • Dec 01 09:09

    barendgehrels on develop

    [test] cleanup svg generation (compare)

  • Dec 01 09:09
    barendgehrels closed #945
  • Nov 29 17:33

    awulkiew on master

    [linear linear]: remove asserti… [test] take car alternate tests… test: add and use test settings and 3 more (compare)

  • Nov 29 17:32

    awulkiew on bg-prepare

    [linear linear]: remove asserti… [test] take car alternate tests… test: add and use test settings and 2 more (compare)

  • Nov 29 15:35

    awulkiew on develop

    Add 1.78 release notes. (compare)

Gaurav Sarkar
@GauravSarkar
okay @mloskot
Rohit Konge
@rohit_konge_twitter
Hello Everyone! I'm a 2nd Year B.Tech CSE Student. I would like to start contributing to Boost C++ libraries for GSOC 2021
KoushikAD1234
@KoushikAD1234
Hii Everyone! I'm a first year B.Tech Electronics and communication engineering student. I would like to start contributing to Boost C++ libraries as I highly intereseted in Coding as well as development and also want to participate in GSoC 2021 under this Organisation. Will somebody help me?
Mateusz Łoskot
@mloskot
@KoushikAD1234 Search the web, read, ask questions. There's no babysitting to offer.
Shubham Korde
@shubhamkorde
Hii! I am Shubham Korde, second year undergraduate from Indian Institute of Technology Kanpur (Electrical). I would like to contribute to this organisation. Can anyone help me get started?
Sanjiban Sengupta
@sanjibansg
Hello everyone!
This is Sanjiban Sengupta, a Junior undergrad from IIIT Bhubaneswar, pursuing Computer Engineering. I have working and practical experience working in C,C++, Python, etc. with knowledge of mathematical concepts like Calculus, Linear Algebra, Stats, Prob. 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.
Siddharth Kumar
@Siddharth-coder13
Hey everyone, just made to this channel. Already done some contribution in geometry repo, (though still in the review phase) . Glad to connect to this platform with all.
Saurav Dhar
@imshuv
hello everyone, I am Saurav Dhar
A junior undergrad from Chandigarh University pursuing B.E in computer science , I am currently a 3* coder in codechef. And now I want to get in open source . I will be really thankful if someone can suggest me on how to get started with it?
Mateusz Łoskot
@mloskot
Scroll up
pankaj-2407
@pankaj-2407
Hello everyone,
This is Pankaj Goyal,2nd year undergraduate from NIT Warangal.I am currently 4*coder in codechef and 1450+ in codeforces and a good rating in other platforms too. I have good skills of competitive programming in
c++,and I am beginner in python and java and I have a good knowledge of web development . but now i want to get in open source and I want to start contribute . Can anyone help me to get started .
Mateusz Łoskot
@mloskot

Can anyone help me to get started

No. There is plenty of material online, general and Boost specific, that should get you started in no time
https://gitter.im/boostorg/geometry?at=6001a0c499549911fc23a72e

tinko92
@tinko92

Hi everyone, before I have time to write a proper issue on this for github, I hoped that I might get some preliminary feedback here. At work I was recently confronted by a problem of determining geometries that are "visible" in some obstructed space. In this case this means that I want to query objects that are located between two straight, oriented lines in 2D or planes in 3D (the cones of vision). If I understand the structure of the rtree correctly, it would be in principle possible to use it to make such query efficient. I assume this would require a new predicate.

I also mention this, because I understand that GSoC is coming up and it's only 175h this year. I am not eligible this year, but I wondered whether it could be something for the list of project ideas.

Vissarion Fisikopoulos
@vissarion
@tinko92 as far as I understand, if the user provide a predicate of whether those oriented lines (btw a definitions is missing here) intersect a box then the r-tree could be used. However, @awulkiew who is the author of r-tree is the one that is possible to give the most precise answer.
@tinko92 also if this is the case, maybe is too simple for a gsoc project ?
tinko92
@tinko92

@vissarion thanks for the quick feedback. I will provide a sketch that illustrates what I mean: https://ibb.co/ynVG2RZ . By oriented lines I mean the lines passing through point_1, point_2 and point_3, point_1 (oriented in the sense the order of those points matters). I am looking for the objects to which the view from point_1 is obstructed by the obstacle point_2, point_3. These are the objects that are to the right of [point_1, point_2] and [point_3, point_1] and [point_3, point_2].

I think this would be a new spatial predicate and is not yet efficiently decided by the existing bg rtree predicates (EDIT: I suppose currently in 2D a ring could be used that extends to the boundary of the space, I don't know the implementation of that, but I think this would involve at least some redundant tests. But I think for 3D, there is no efficient predicate yet), i.e. the bounding box of the shadow that is cased by the segment wrt to point_1 would hit many more boxes than the combination of the orientation tests above. The way I understand the structure of the rtree is that a predicate can be efficiently implemented if it can be efficiently decided for internal tree nodes and rule out their entire subtree, and I think that is the case here (we can check for the red rectangles sketch and if they don't fit the query, we don't need to search through their children).

I understand that it may be too simple for a project. There is also a 3D version of that problem, in which I would want an rtree predicate that looks for objects that lie in some half-space above a given plane. Or more generally, I think the rtree could use an interface for custom spatial queries, that requires an apply-method for internal rtree tree nodes and for rtree leaves. If I didn't miss something in the documentation, currently there is only an interface for custom unary predicates that need to be applied to each leaf in the query result (index::satisfies).

I will try to write this in a proper issue on github this week.
Adam Wulkiewicz
@awulkiew

@tinko92 So AFAIU you want to get all of the points intersecting an infinite frustum. Since you want to get all of the objects intersecting it this would be a spatial query.

There is a method to do this right now but it's undocumented: https://stackoverflow.com/questions/19490435/boost-geometry-spatial-query-shapes
So indeed I think the best course would be to implement user-defined spatial predicate allowing the user to pass two functors/predicates defining the tree traversal for node bounding boxes and values stored in the rtree.

I understand that it may be too simple for a project.

Yes this would be too simple. I'm planning to do this for some time now but I still find something more important. The most tricky part of this is the interface which will be unchangeable when it's made public.

index::satisfies

Yes, this predicate does not take a part in tree traversal at all. It's only for filtering of the resulting values. Basically working like if std::copy_if was called after rtree.query().

tinko92
@tinko92
I see. Thank you very much for the pointer. And thanks for mentioning that this interface is basically already on the agenda, I guess in that case the question is solved and there is no gh issue for further discussion necessary.
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