- 3D printing
- Audio IO on RISC OS
- Desktop Tracker
- Dune II
- Matrix Orbital
- PCB Drill
- Talking Canvas Jnr
- Active project
- Source code
I've just realised that there's 134 points (+1 for the start position), not 130. However, I'm not going to do the maths again - you just need to multiply the previous time by 308,178,024...
The "correct" grouping algorithm produces this route (the drill starts at the centre of the board):
Currently, it's at 785.408mm. The left hand side is particularly bad. If you look closely, you can see numbers next to each point. This is its position in the route, and occasionally I'll mention them. The algorithim will perform the "swap neighbours", "outliers" and "swap neighbours" first of all:
That's a bit better - now at 692.045mm. However, if you look just above the middle of the board, there's a long line that points 4 to 8 are nearby. This is where the "find points along a path" algorithm kicks in - which it'll also do for the left hand side (although that is difficult to see because the lines overlap). After this:
Now it's 654.102mm - but still some optimisations to do, such as a couple of loops between points 20 and 49. The "Remove crossed paths" algorithm will try to fix that...
With that, pretty much all the cross-overs have been removed, and our length is 628.307mm. There's still some on the bottom left hand side, but that's because the points are actually on the lines (line is betwen points 45 and 46, and the points are 52 and 54). The crossed paths algorithm doesn't consider points on a line as crossing - and the earlier "find points near a route" didn't spot it because it was such a mess beforehand.
It'll now look at the outliers again:
Here, it only moves one point - what was point 110 is now point 102, and the route is 618.454mm. It then runs "find points near a line" again:
And we now see that the two points on the bottom left hand side that I'd mentioned earlier that were on the line are now put in the same line. Our length is 618.380mm - we only saved 0.074mm! But we have some crossed points...
The second execution of the remove crossed paths algorithm has now eliminated them, and the length is 613.374mm
This is the best it can come up with; re-running the algorithms has no benefit, so it stops there.
So it starts again, this time with the "incorrect" grouping algorithm:
Oh dear - its initial length is 926.089mm, which is a considerable way from the "correct" algorithm. Never mind, let's do the first step (outliers):
That's actually quite good - 675.855mm. The path is looking quite well defined, so let's move the points near lines:
Now at 614.507mm - which is shorted than the "correct" algorithm!. We have some crossed paths which can be worked on:
This has brought it down to 596.108mm - and the path looks quite good! But let's re-run the outlier algorithm again...
And it's 591.981mm - the biggest difference is point 63 (was 81), which on the "correct" algorithm was the one it had troubles with until the end. And another attempt to move points to a line:
It's now 587.708mm - the only difference is points 74 onwards where it's done a slight rejigging of the order.
The repeat of the remove cross paths didn't yield any differences, so no image was captured - but another outlier attempt has swapped some points in the same area as before:
We've now got to 578.102mm - with some crossed paths, which we'll sort out:
And that's the final answer - 575.009mm. It can't optimise any more than it already has.
How long does it take?
As I said, to exhaustively search for every answer at 1µs per search would take a long time - running these two algorithms took a total of 0.144683 seconds. This means you barely notice it when it starts to drill the pattern for your selected drill bit.
If you want an animated GIF of these steps, then you can download them here: