Clever way to do this?

breadmonkey

I have a cloud of points in 3D space. Pairs of these points are connected to form a cloud of lines. There are some cases where the end point of one line lies directly on another line segment and I want to identify all of these cases.

I've written a function which can check if a point lies on a line segment. I then take each line in term and loop through all of the points, checking if any are on that line. Then I move to the next line and so on. Something like the following pseudo code:

For each line in lines
     For each point in points
          Check if point is on line

This is fine for a limited set of points/lines but it takes a very long time to run on the entire point cloud because I'm checking every single point against every single line. Can anyone think of a clever way to implement this for faster speed of execution?

Thanks

Colonel Panic

The key here is spacial partitioning, for 3D points, you could look at an octree.

breadmonkey

Thanks for that. It looks interesting but will take me a while to get my head around it. Might be back with some questions!

Colonel Panic

breadmonkey wrote: »

Thanks for that. It looks interesting but will take me a while to get my head around it. Might be back with some questions!

Get you head around how to insert date into a binary tree first before you add another 6 children per node to the mix!