The 80/20 rule kicked in and it took me a bit longer to write than estimated.
My ARX entry is attached. ConnectDots2004.arx is for Autocad 2004-2006, and ConnectDots2007 is for 2007-2008(9?). Just load the appropriate version and at the command line type
connectdots
You will them be prompted for the maximum segment length to connect, and to select the points to operate on.
Here the processing times (counted in my head) -
10,000 points, uh' its done.
100,000 points, little less then 2 seconds.
500,000 points, about 15 seconds.
The heart of the program is the KD-Tree data structure which holds point data selected by the user. Given any point, we can ask the structure to return a set of points within a radius of the source point. Line segments can then be created from each point in the set to the source point. Doing this for all the points in the collection, results in at best 2 line segments for each qualified set of points. There are a number of methods to find duplicate line segments, but they all have some performance cost associated with them. Instead I set a flag for the source point, marking it as already processed and don't have to worry about duplicate segments.
Points of interest in the code (since there is a lot of code)-
Create an instance of CKdTree and initialize it to the number of dimensions. kdTree is set to 3 dimensions, though for the purposes of this program 2 would have been fine since the Z is ignored in all the calculates.
CKdTree kdTree;
kdTree.Create(3);
Add a node to the tree. The forth parameter is of type void *, and is for user defined data. In this case I'm using it as a flag to determine if the node has been processed. Initial value is NULL or false.
kdTree.Insert(pt3d.x, pt3d.y, pt3d.z, NULL);
Query for all the gathered points (need to add another public function to CKdTree to get the head position).
Get a pointer to the X, Y, Z data
Query for another result set around the X, Y, Z, and radius.
RESULT_SET * pResAllPoints = kdTree.NearestRange(0.0, 0.0, 0.0, HUGE_VAL);
...
double * pPos = pResAllPoints->riter->item->pos;
RESULT_SET * pRes = kdTree.NearestRange(pPos[0], pPos[1], 0.0, dRadius);
The KD-Tree code I got off the internet about 5 years ago, though I've not been able to find it again and it had no copyright notice or name associated with it. Any changes I did to the code was so it would compile in C++, IIRC work with doubles instead of floats, and a couple helper functions. I've used the code in about 7 projects, and it's always fun when another opportunity arises to use it again.
The rest of the code should be straight forward, if not a bit messy.