Grasshopper

algorithmic modeling for Rhino

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

Views: 2341

Attachments:

Replies to This Discussion

Try this

Attachments:

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

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

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:

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:

or better (for Plan A)

Attachments:

and finally PlanA ~= PlanB

Attachments:

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:

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':

This is confirmed by a relatively rapid response to changing the 'Group' slider value:

RSS

About

Translate

Search

Photos

  • Add Photos
  • View All

Videos

  • Add Videos
  • View All

© 2024   Created by Scott Davidson.   Powered by

Badges  |  Report an Issue  |  Terms of Service