My algorithm
My algorithm has five different algorithms within it to try to come up with a good enough solution.
- Group locations that are close together
- Try swapping neighbours to see if the route becomes shorter
- Find the points that are quite far from their neighbours and see if there's any closer points to it
- If a point lies roughly in the path of two others, see if visiting this point makes the paths shorter
- If any paths cross, try swapping them around so they don't cross to see if the route is shorter
Grouping locations
The idea behind this sequence (which is only used once) is to come up with a very rough pattern which will be used as a basis.
This algorithm tries to make groups of points that have between 1 and 10 points in them by extending a radius around each point and seeing if they touch.
The simplest way to describe it is in pictures. Here, it has taken the 130 points, and created groups of them based on a radius around each point:
Using this particular radius, it has created 9 groups of points - some of which only have 1 point in them. It then looks at any grouping which has more than 10 points in it, and reduces the radius down until it has between 5 and 10 new groups. This is the magenta group in the bottom middle of the board:
It has created 7 groups from this - and it will divide down further. This is the dark yellow at the bottom:
This is good enough; it does not need to subdivide further. However, the green section in the second picture needs more division:
It will now move back to the cyan block to the left of the first picture. This is subdivded:
The red bit needs subdividing:
And finally, the pink section on the subdivision of the original cyan bit:
That's the subdivision done. It will use these groups and points within the groups based on a "nearest first" approach. It starts off with the first subdivision, and visit each group based on which one is nearest. Inside that group, it does the same thing until all points in that group have been added. And this occurs for all groups.
The route that is chosen isn't particularly optimal - although (as I commented to a friend of mine) it would still be quicker for the CNC machine to drill them than I would by hand. But I like optimising things!
Swapping neighbours
This is a fairly simple algorithm that swaps one point with the one next to it. If the new path is shorter, then use it; otherwise keep the old one. This is repeated until no more optimisations can be done.
Find far points
This algorithm I call "Outliers", and it basically looks for any points that are quite a distance from their "neighbours" (being the ones it is connected to). If it finds any, it'll try to find the points that are actually closer to it than the ones they're connected to and insert it in between those two points. If the new route is shorter, then it'll keep it - otherwise look for the next point.
This algorithm looks at the worst offenders first of all, and recalculates each time up to a maximum of 30 points (otherwise it could get bogged down when there'll be very little gain).
At the end of this stage, the Swapping neighbours algorithm is performed repeatedly to tidy things up.
Points along a path
This has a fairly simple premise in that if you're travelling from A to B, and C is pretty close to being on the way, you may as well go via C anyway.
This looks at all points, and sees if there are any lines that happen to be near it. If there are, it will rearrange the route to go via the point and if it's shorter, it'll use the new route. Otherwise, it'll use the old one.
As the previous outlier algorithm, the swap neighbours is called to tidy it up.
Removing crossed paths
This was based on an observation I had with the 130 points that some paths were crossed. To me, it looked like if they weren't crossed, then it would be quicker.
So I wrote the algorithm that looks at all the line segments and if there were any crossed points, it would swap the order around so they wouldn't end up being crossed.
This did actually show the new route was quicker.
As before, the swap neighbours is called after this
Putting it together
The first algorithm is performed once (although there are two variants of it which produce different results). After then, the four algorithms are repeated until no more optimisations can be made.
The grouping variations
When I initially wrote the grouping algorithm, I hadn't realised that the "ordering by nearest" was always from the same point (either the current drill position, or from the centre of the group). I had actually meant the current drill position to follow the group or point it had selected. However, when I recoded it to be correct, the new algorithm was worse for the 130 points, but was actually better for a subset of them. So it tries one, and then the other - and keeps the best one.