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

[Graham Cox]

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.   
> For a square grid of this type, the optimal path would be to go left  
> to right across the row, then down one, then right to left across  
> the second row, then down one again, and left to right across the  
> last row.  That should yield a travel distance of 1400 microns (with  
> a 100 micron center-to-center spacing of the spots).

One quick way to make the algorithm look a bit further for an optimal  
solution is to remove this line from the anneal() function:

     if( nsucc >= nlimit)
         break;		// Finish early if we have enough successful changes.


I found that with completely regular grids it would find a solution  
that was as short as theoretically possible, (i.e. it eliminated any  
diagonals) though the actual path taken through the grid is still  
somewhat arbitrary. Of course it takes it slightly longer to run, but  
this wasn't significant for my test grid (48 objects).

Given that this works by trying path segments at random until it  
discovers a shorter one, I don't think you'll be able to force it to  
always find the most regular as well as the shortest path. If it's  
important that your objects are visited in a specific order, I suspect  
that you might need to leave it to the user to specify the order in  
some way (in other words, it requires real intelligence). A different  
algorithm could be used to find the nearest neighbour in a certain  
direction, say "east" then if not found, switch to "south", "west",  
"north" in order. Starting at the top left that would find the path  
you described for a regular grid. If the placement is irregular the  
problem you would need to deal with is making sure it detected every  
object at least once so that none got forgotten, and marking each one  
already found so that none were visited twice. I expect that the path  
found by this approach would be non-optimal for most irregular cases,  
but could well be acceptable.

> Also, is the sorting order of the array such that the first item in  
> the array is the last to be drawn?  It seems that way from the  
> sorting I'm seeing.

The algorithm actually doesn't preserve the starting point at all, but  
my wrapper code does. The first item in the original array ends up as  
the first item in the sorted array, to allow you to specify a known  
starting point. That works because the sort is actually performed as a  
"round trip" - it doesn't matter where you start the circuit is the  
same. When you pass [layer objects] as the objects to be sorted, the  
first item is the first to be drawn (bottom-most object) so that's  
where the path starts (or finishes, depending on how you look at it).


To help you explore this, you might find the attached helpful. It's a  
slightly modified route finder that makes some additional progress  
callbacks from within the inner loop whenever the path length has  
actually changed. Then, in my document category, I use that to  
recreate and redraw the path so far. It's very hackish, so don't use  
it for app code, but it does allow you to see what's going on as the  
algorithm runs.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: GCDrawDemoDocument+ShortestRoute.h
Type: application/octet-stream
Size: 447 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080801/cef03fe2/attachment-0004.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: GCDrawDemoDocument+ShortestRoute.m
Type: application/octet-stream
Size: 4149 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080801/cef03fe2/attachment-0005.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKRouteFinder.m
Type: application/octet-stream
Size: 16902 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080801/cef03fe2/attachment-0006.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKRouteFinder.h
Type: application/octet-stream
Size: 2138 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080801/cef03fe2/attachment-0007.obj>