ITC2009: Line Segment Intersection

The problem of this contest’s round was to find the intersections within a set of 3d line segments. I found tons of information in google about algorithms solving this problem in 2d. It seems that finding the intersections in a set of 2d line segments is a well known problem of computational geometry. Unfortunately, I didn’t find any algorithm in 3d and I wasn’t sure that converting the 2d algorithms to 3d could give better results than a brute force approach. Taking this into account, I decided to implement a brute force algorithm using a simple line segment intersection test. This approach gave ~800secs in a set of 100.000 line segments. I realized that the tests that were already tested could be skipped, after the modification the algorithm gave ~300secs. At this moment, I removed every instruction of the if intersection test statement (don’t ask why) resulting in a running time of ~6secs. This time was wrong. I was compiling with the optimizations active, so the compiler just removed the call to the intersection test function, giving a double nested loop doing pointer dereferencing. Well, after this little mistake I was ready to think in how to parallelize the algorithm.

As with the previous problem I used Threading Building Blocks as the tool to parallelize the algorithm. I chose to use the parallel_reduce algorithm, after trying to make it with parallel_for. The problem is gathering the results across all the tasks. Parallel_reduce is an easy way of collect results after the tasks completion. The algorithm includes a synchronization method: join. After a task ends the join method is called to merge the results. The parallel approach gave me a time of ~60secs.

I think the speed I got wasn’t that fast to win this round but that’s not my objective. I’m having a lot of fun, I’m learning from other people and I’m learning how to use TBB. Those are my objectives.

Comments are closed.