## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
##### Activity
• 07:54
LumiereDeLOmbre commented #1111
• 07:15
LumiereDeLOmbre edited #1111
• 06:59
LumiereDeLOmbre opened #1111
• Jan 30 04:10
Mitsuhiko-Matsukawa commented #1108
• Jan 25 14:52
barendgehrels commented #1108
• Jan 25 14:48
barendgehrels commented #1109
• Jan 25 09:55
barendgehrels labeled #1108
• Jan 25 09:55
barendgehrels assigned #1108
• Jan 25 09:55
barendgehrels commented #1108
• Jan 25 09:44
barendgehrels commented #1109
• Jan 25 09:41
barendgehrels labeled #1109
• Jan 25 09:41
barendgehrels assigned #1109
• Jan 24 16:07
Mitsuhiko-Matsukawa opened #1109
• Jan 23 04:27
Mitsuhiko-Matsukawa opened #1108
• Jan 22 07:39
harm-smits starred boostorg/geometry
• Jan 21 17:48
rconde01 commented #1075
• Jan 18 14:10
barendgehrels commented #1057
• Jan 18 14:09
barendgehrels commented #1057
• Jan 18 14:09
barendgehrels commented #1057
• Jan 18 13:17
barendgehrels commented #1057
Baidyanath Kundu
@sudo-panda
Can I know the time complexity of nearest neighbor search for rtree
Also shouldn't the time complexities of the implementations be listed in the documentation?
Digvijay Janartha
@digu-007
The performance of Rtree depends on factors like balancing algorithm, number of nodes etc. Although in every case KNN using RTree is faster than the naive brute force method, but using right algorithm in the right place yields better results. I used nearest neighbour once, and queries works in approx. k * log(n) complexity, where k is the number of nearest nodes and n is the total nodes in the Rtree. https://www.boost.org/doc/libs/1_72_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html Refer to this for more information. There are figures and graphs for complexity analysis.
Baidyanath Kundu
@sudo-panda
Oops my bad thanks for the help
Digvijay Janartha
@digu-007
No problem :)
RTree is frequently used in my project, for intersection and KNN queries. I must say it is a very powerful tool.
Baidyanath Kundu
@sudo-panda
@digu-007 Is packing algorithm available in boost geometry
Digvijay Janartha
@digu-007
I haven't used packing algorithm yet, and I remember that it was written somewhere that they only have first 3.
Baidyanath Kundu
@sudo-panda
yeah I couldn't find it anywhere
rconde01
@rconde01
is there any good place to find references to the underlying algorithms used by boost geometry - e.g. for boolean polygon operations?
@awulkiew
@awulkiew
@rconde01 the code itself and the related comments. For set and boolean/relational operations of polygons AFAIR we use our own algorithms. If you want to know more about history of the implementation you should probably ask @barendgehrels at the mailing list because AFAIK he is the author of the initial version which was first added into Boost. Both set and relational operations first calculate the intersection points with additional data about the parts of geometries in the vicinity and then analyze this information either by creating and traversing a graph of intersection points and segments connecting them (this is done in set operations) or doing a simplified analysis like sorting the intersection points by the position on geometries and analyzing this sequence (this is done in boolean/relational operations).
@awulkiew

@mloskot

I guess you are not on the C++ Slack

I tried to get invite at cpplang.now.sh using my public/Boost-related email but the site responded with no_perms, so I gave up. ;)

Great, thanks!

Mateusz Łoskot
@mloskot
@awulkiew I issued new invite, let's see if you get it.
@awulkiew
@mloskot I'm in, thanks!
rconde01
@rconde01
@awulkiew thx for the background...trying to look at the code on github has been a bit challenging...every call seems to be a light wrapper to some other template...so maybe i need to actually compile and step through it instead
Baidyanath Kundu
@sudo-panda
@mloskot Just a reminder. It's been a week since I uploaded the new benchmarks for #670 can you please check it? Also i am working on the plotly extension. Will add support for more geometries soon.
Mateusz Łoskot
@mloskot
@sudo-panda Sorry, I did not have time yet. I have seen your new PR, but not details of it
Baidyanath Kundu
@sudo-panda
It's cool :)
Mateusz Łoskot
@mloskot
@sudo-panda tentative promise: I will check the WKT thing at least by end of the week
tinko92
@tinko92

Hi, I've looked into #585 , which you said is an annoying bug. I have no complete understanding of how to solve it, unfortunately, so I cannot create a PR or post a solution to the issue, but I hope that giving you this partial analysis of the issue here, may help you to solve it:

I noticed that https://www.boost.org/doc/generate.php?page=libs/libraries.htm&version=1.73 shows geometry extensions and https://www.boost.org/doc/generate.php?page=libs/libraries.htm&version=develop does not. After running generate.php locally, I think that it is based on a db of libraries that is generated by update-doc-list.php and represented in this xml file: https://www.boost.org/doc/libraries.xml. It has multiple entries for "geometry/extensions", the entry for develop has hidden status, the entry for "1.70" does not. Notably, "geometry index" has an entry for 1.70 without status hidden and one for 1.72 with status hidden.

What I think, may happen here, is that the generate.php-script just uses the latest numbered entry if version=1.73 is passed. Manipulating the data structure like this in generate.php
$libs->db['geometry/extensions']['1.73.0'] =$libs->db['geometry/extensions']['1.70.0'];
\$libs->db['geometry/extensions']['1.73.0']->details['status'] = 'hidden';
makes the "geometry extensions" entry go away, if I run it locally.

So, if the metadata would be added again for the next version with the status being properly set to "hidden", I believe that could make the "geometry extension"-entry go away.
So TL;DR: I think the list of libraries for releases may use the latest meta data for a numbered version and because of that having a non-hidden "geometry extensions"-entry for 1.70 and no entry (deleted) afterwards may cause the entry to reappear in all versions since then.

Mateusz Łoskot
@mloskot
@tinko92 This is awesome finding, thank you so much. I will look into that tonight.
@sudo-panda I'm sorry, still haven't looked at your PR. The Boost .173 pre-release tasks are taking over.
tinko92
@tinko92
@mloskot the more i think abou this, the more it seems to be a website issue rather than a boostorg/geometry issue to me. I opened an issue with this question at boostorg/website: boostorg/website#497 . I hope this is not considered inappropriate, if it is, I will delete the issue.
tinko92
@tinko92
Manipulating the history would not be satisfactory, including metadata to mask metadata from a previous version that should just be gone completely in master seems not satisfactory either, so that's my reasoning for inquiring whether it should be considered a website bug. But adding the metadata like in my linked branch in the issue may still be reasonable if it solves the issue, to have the entry gone in version 1.73 because I doubt that he website will change to quickly, even if the website is determined to be at fault.
tinko92
@tinko92
I guess glenfe resolved it.
Mateusz Łoskot
@mloskot
Yes, I'm thankful Glen was able to help.
I had to take kids for two days in woods,
Let them spend energy accumulated during lock out due to covid
Without you and Glen, the I could do anything for the issue.
Thanks a lot
Baidyanath Kundu
@sudo-panda
It's fine @mloskot . It's a global pandemic I understand your situation, it's fine. I am in bit of a problem regarding #693 tho. There is no fill for 2d plots in plotly and the 3d mesh plots can only be made by mentioning explicitly which vertices form a triangle. But the polygon type doesn't check if the rings form proper faces. Should I check for faces in the polygon or should I let the user decide if his data can be a mesh plot and if he wants it to be a mesh plot.
Baidyanath Kundu
@sudo-panda
Why do append m_ to class variables, like m_geometry? What does it stand for?
tinko92
@tinko92
Generally, in C++ development, the "m_" prefix is often used to designate class/struct members.
Baidyanath Kundu
@sudo-panda
Does it have a full form?
member I guess?
tinko92
@tinko92
Yes, I think the "m" is short for "member"
Baidyanath Kundu
@sudo-panda
Congrats
@tinko92
tinko92
@tinko92
Thanks. Also thanks for the renewed trust @vissarion
tinko92
@tinko92
And, of course, thanks to everybody else at Boost.Geometry who was involved in the project selection.
Digvijay Janartha
@digu-007
Congrats @tinko92 !!
Vissarion Fisikopoulos
@vissarion
We had very good proposals this year and the selection was very difficult.
Congrats @tinko92 !
Thank you all for your proposals, discussions and contributions.
Congrats @tinko92
Great working with you guys! :)
tinko92
@tinko92
Thanks, everyone!
Mateusz Łoskot
@mloskot
Congratulations!
@tinko92 Boost.Geometry is an intimidating piece of software (it is to me!) and it does not stop you to keep ploughing. I want to say, you're an exceptional contributor.
Baidyanath Kundu
@sudo-panda
Is strategy necessary when differentiating between CSs because in the plotly extension I don't see a reason to keep strategies and not make the decision internally everytime. Is there some other reason why strategy is used other than letting user make the choice?
Frédéric Simonis
@fsimonis
Hi there, I am developer of the project preCICE.
We are currently writing our next major reference paper and would like to cite our dependencies to give them the credit they deserve. This paper will be the goto citation for quite some time.
We use boost.geometry especially for the spacial index trees.
How should we cite your project?