Where communities thrive

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

Explore more communities

boostorg/geometry

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

People

Repo info

Activity

10:09

tobiass-sdl commented #1112
Feb 03 15:57

tobiass-sdl commented #1112
Feb 03 15:48

tobiass-sdl opened #1112
Feb 01 15:38

barendgehrels commented #1108
Feb 01 15:36

barendgehrels commented #1108
Feb 01 10:55

barendgehrels commented #1108
Feb 01 07:54

LumiereDeLOmbre commented #1111
Feb 01 07:15

LumiereDeLOmbre edited #1111
Feb 01 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

Baidyanath Kundu

@sudo-panda

@mloskot It's cool.

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?

Adam Wulkiewicz

@awulkiew

@sudo-panda packing algorithm is used if you pass the elements into the constructor of the R-tree: https://www.boost.org/doc/libs/1_72_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree/rtree_iterator__iterator_.html

Adam Wulkiewicz

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

Adam Wulkiewicz

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

I'm asking ther eabout the #585 issues.

Great, thanks!

Mateusz Łoskot

@mloskot

@awulkiew I issued new invite, let's see if you get it.

Adam Wulkiewicz

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

Aditya Mohan

@adityamohan29

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?

Chat via Matrix