[Drawkit] Now with added testing. (was Re: For the brave ; -)

[Graham Cox]

More Route-finding madness ;-)

I have made an attempt at implementing a "nearest neighbour" (NN)  
approach. In the simplest case, this just searches the remaining  
unvisited points and chooses the nearest. In the event of a tie, the  
first one found in the current list is used (which in turn means that  
a presort into x,y order might be beneficial but I haven't really  
explored that so far). The neighbour becomes the current point for the  
next iteration. It proceeds until all points have been visited. This  
approach is really dumb and doesn't turn up a good path for regular or  
irregular grids in most cases (unless you get lucky).

So I then modified NN to use the directional approach which I  
attempted to outline earlier though reading it again it's a bit  
unclear. So what happens now is this: the algorithm tracks in a  
certain direction, say, east. It searches for the nearest neighbour  
that lies in this direction ahead of the current point. It determines  
whether a point lies in this direction by testing whether its angle  
from the current point is within the area 45 degrees either side of  
the cardinal direction. If so, it is used as the next point. If no  
neighbours can be found in the given direction, the direction is  
changed and potential neighbours searched again. This behaviour  
results in the NN algorithm keep going in the same direction until  
there's no more that way, turning, then going in the new direction,  
and so on. A simple switching scheme as first tried was just to cycle  
through E, S, W, N. The predictable result is an ever-decreasing  
spiral path over a regular grid. That might be OK, but I was after a  
scan pattern, so a modified switching scheme tracks east and west  
alternately until no more can be found, then allows one neighbour  
south or north before going back to east/west. The result is the  
expected scan pattern over a regular grid provided the starting point  
is at a corner*. For irregularly arranged objects, you get a fair-ish  
path, though non-optimal compared to the SA approach, with frequent  
crossings (crossings in themselves are not necessarily a problem, but  
they do indicate a better path is possible).

At that point you could compare path lengths as per Uli's suggestion  
and go with whichever is less. I may modify the route finder to do  
that as a matter of routine, but right now you manually select whether  
to use SA or NN (code attached).

I also found a bug in the code (off by 1) that may have been the cause  
of your impression that the SA path always started at the last object.

*the corner criterion is not essential in that all points will be  
visited regardless, but starting somewhere that isn't a corner will  
spoil the regular pattern. However, it would be easy enough to find  
the corner point of any given set prior to the NN sort to avoid the  
problem. Again, the route finder could do this automatically.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKRouteFinder.m
Type: application/octet-stream
Size: 23380 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080803/d97614a5/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKRouteFinder.h
Type: application/octet-stream
Size: 2964 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080803/d97614a5/attachment-0003.obj>
-------------- next part --------------



On 1 Aug 2008, at 9:04 pm, Graham Cox wrote:

> Just looking at your grids. Given that there are an odd number of  
> points, and that the algorithm makes a "round trip", I think there  
> is no way to make a path that doesn't have at least one diagonal. I  
> can't prove it, but just trying to do it "by eye" I can't do it. If  
> you relax the "round trip" requirement then there's no problem, so  
> maybe that's something to focus on. A "round trip" is required as  
> part of the original TSP problem, but for our needs isn't all that  
> important.
>
> cheers, Graham
>
>
>
> On 1 Aug 2008, at 9:01 am, Brad Larson wrote:
>
>> It gets close, but I did a trial on a few grids of 5 wide, 3 down  
>> spots and found that it always stopped short of an optimal path
>
> _______________________________________________
> Drawkit mailing list
> Drawkit at lists.apptree.net
> http://lists.apptree.net/listinfo.cgi/drawkit-apptree.net