In my spare time, I write extensions for a 3D modeling program. I have one extension that is in serious need of a rewrite. It is way, way too slow and not at all optimized. (It's not C, but Ruby, but I would consider rewriting it in C)
The task my extension performs is to analyze a 3D or 2D (usually just a 2D in situ) model (consider a topography or a poorly drawn house foundation plan) and find all the line segments that do not touch other line segments at their ends (either or both). See attached examples. topo1 is a view of a lot with elevation lines. topo2 is the same screen shot, with the open line segments (an open line segment == a vertex with only one line coming off of it) labeled and numbered. In this view, for example, I need to determine that point 22 needs to be connected to point 25 because it is "closer" than all the other points in the set of points I am analyzing. And, for another example, points 20 and 21 need to connect, and 23 and 24 need to connect.
Along the same lines, I would also like to detect that since point 25 is also a "perimeter" point, 25 needs to also be connected to 28. (but this would be icing on the cake)
My current algorithm (if it could be called that... yuk) is to make an array of all the vertices with only one line connected to them.
Then, I start with the first vertex in my array, and calculate the distance to all the other vertices in my array, and when the closet vertex is found is found, I draw a line to connect these two vertices, if and only if that new line will not cross another existing line, or a line I have just drawn due to connecting previous vertices) in the process. It has to be a straight shot without crossing any other lines. I do a raytest to determine this - works' fine, but this too adds to the long elapsed times. If an obstruction is found, I get the second-closest vertex and see if that will work, etc.
After the first vertex is processed and a new line has been drawn, I take the second vertex in the array, and run the array again (from array element #3) to find the distance to its closest vertex, then test for no obstruction, then draw a line, and I keep repeating this until I am done. With a few vertices (think in the dozens), performance is fine. However, when the number of vertices grows the to the hundreds or even thousands, my routine runs FOR EVAR, as I am sure you can imagine.
Vertices get added to my initial array in willy-nilly fashion, just as you see the pseudo-random labeling added in topo2.
What is the nature of the algorithm I need in this application to speed it up? I just had a user have to cancel his 3D modeling program after my algorithm ran for 48 hours and did not finish.