speeding up calculation of huge sets of points or lines

hi all

hope somebody has an ides to that topic.... maybe david when he is back from his urgent needed holidays or Rajaa ??

we want to optimize calculations of pointssets or sets of lines for line line intersection for example.
we know the possibility to tile up data-sets in smaller pieces but we don't know the approach to set up the datat tiling script
i think david used it @ his pointsetreconstruction tool
so we started to cull the points with bbox and sorted than the points again but the script didn't get faster and it was a little bit buggy
hope somebody has an idea to that topic
or have some links that point in that direction

waiting for some good hints or a great discussion with our scripting guys out there

all the best

[uto]
www.utos.blogspot.com

Replies to This Discussion

Permalink Reply by Giulio Piacentino on June 8, 2009 at 6:39am

Please, could you give a couple more details? I know it might be for some undisclosed project, but like this it is difficult to understand what you are trying to do. Maybe then some people would know already a solution?

Permalink Reply by °[u on June 8, 2009 at 7:13am

hi Giulio!
...for example a problem like "next neighbour", or "closest point" (also with lines or objects ), or the voronoi calculation... when you have to compare every component with all others... we know it must be possible to split the data into sectors like david did in his "pointsetreconstruction" tool.... to speed up the calculation... but we don't know how.

Permalink Reply by Giulio Piacentino on June 8, 2009 at 7:41am

Hi °[u! Sometimes it is enough to order points with a sweeping plane (from small x-coordinate to big x-coordinate, for example). Then a simple binary search would be possible. Otherwise, I know octrees are used in collision detection. Also see Kd-trees in wikipedia. With quite some coding it could be possible to do these things in GH.

Permalink Reply by Damien Alomar on June 8, 2009 at 9:46am

I've never dealt with them, but I think that you're essentially looking for some sort of space partitioning algorthim that would prevent you from having to take all points into account for every single operation. The two best ones for 3d space are either OctTrees or Binary Space Partitioning (BSP Trees). Personally I like OctTrees myself, and would seam to be a little bit easier to setup than BSP trees. With BSP trees you definitely have to know what you're doing to navigate those trees and be able to work with them effectively.

HTH

http://en.wikipedia.org/wiki/Octtree
http://en.wikipedia.org/wiki/BSP_trees

Permalink Reply by to] on June 9, 2009 at 9:59am

thanks to giulio and damien
that is exactly what we are searching for but i didn't know the name of that algorithms
thanks a lot for the links
we will have to look closer but we think we now know what to do
again thanks a lot
and keep on your great work

all the best [uto]
we will place a link at our blog to your pages ;)
damien i am looking forward to see your hairtool

Permalink Reply by Giulio Piacentino on June 9, 2009 at 10:48am

Damien, me too!

Permalink Reply by Damien Alomar on June 9, 2009 at 9:06pm

Thanks guys...an alpha will be out tomorrow

to]...just added your blog to the list on mine...thanks for spreading the word :)

Best,
Damien

RSS