QuadTree (QT) component output (point indices)

Hello

I am using quad tree to group a collection of 3d points to a 2d grid of rectangles.

since the points are in 3d space, the output is projected points of the initial 3d points.

I would like to ask how could i match the data structure of the points per leaf to the initial 3d points collection. (perhaps having the indexes of the initial points as outputs in quad tree component)

What i am trying to is to compute the average distance of the initial points, per leaf plane.

thank you in advance for your time.

best

alex

Attachments:

points.gh, 11 KB

Replies to This Discussion

Permalink Reply by peter fotiadis on October 15, 2015 at 12:42pm

Try this

Attachments:

quad_tree_points.gh, 126 KB

Permalink Reply by Joseph Oster on October 15, 2015 at 12:49pm

No way! I've begun to wonder if all that C code you distribute here might have a nefarious purpose? I'm only half kidding...

Permalink Reply by ng5 Alex on October 15, 2015 at 1:17pm

is this checking normal plane vectors of the leaf points to all the other points in 3d collection? does not work with 350000 points. rhino freezes forever.

if that's the case Joseph has already provided a solution.

the calculations for lets say 4 leaves containing in total 350000 points are huge.

thank you for your input.

best

alex

Permalink Reply by peter fotiadis on October 16, 2015 at 1:02am

Well this is "reverse engineering" meaning that ... yes ... it works via the projection criterion (the isParallel thingy). This gives us a O[N^2] complexity. Using divide and conquer techniques may yield faster times (or // with a proper scheduler).

But if you do this frequently with "some" rand pts ... obviously the ideal solution is to ask David to include a non projected tree option.

Q: is the quad Tree a K-means clustering thingy? If yes I have some fast algos that do that.

Note: David does "even" rand pts (with a pretty fast algo I recon). Use the C# attached if you are not interested on the "even" part (spot the Elapsed time).

Attachments:

quad_tree_points_V2.gh, 130 KB

Permalink Reply by peter fotiadis on October 16, 2015 at 2:32am

On the other hand ... Plan B yields ~Loops/10.

Q for David: see 2nd function: why all the "help" methods used and the inclusion test (in order to narrow the search) doesn't appear to have a significant participation on the Elapsed time? (vs pts to pts) ...

... or, in fact, the Vector3d.isParallel is computational heavy?

Attachments:

quad_tree_points_V3.gh, 135 KB

Permalink Reply by peter fotiadis on October 16, 2015 at 3:05am

or better (for Plan A)

Attachments:

quad_tree_points_V4.gh, 139 KB

Permalink Reply by peter fotiadis on October 16, 2015 at 3:39am

and finally PlanA ~= PlanB

Attachments:

quad_tree_points_V5.gh, 138 KB

Permalink Reply by peter fotiadis on October 16, 2015 at 1:59pm

Never say never: Initial Plan A beats B by ~50++% (and loops are O[N]: say 700 instead of 490000). Maybe a 30% further decrease in Elapsed time could been achieved by using Hashsets (and replacing the LINQ used).

Attachments:

quad_tree_points_V5A.gh, 137 KB

Permalink Reply by Joseph Oster on October 15, 2015 at 3:01pm

Look at this Profiler output - For ~105K points, 99% of the time (28+ minutes) was spent creating the points ('Pop3D') and only ~10 seconds was spent on 'OcT', 'PtCloudCntr' and 'Line':