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

[Brad Larson]

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).

Instead, I'm seeing the behavior shown below.  I'm always getting a  
path length of 1441 microns, because it always goes diagonally for at  
least one step.  This might be a result of the algorithm always  
starting with the first point, no matter if it is the best starting  
point.  I haven't checked to see if this is what's actually going on,  
though.

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.

For the lines, I might create a version of the sorting routine that  
operates on two points per object, where there is a forced path length  
for the segment defined by those points, and the sorting operates with  
pairs of points.  That might not be too hard to do within the existing  
methods and functions (double up the array sizes, return the distance  
between two pairs of points as the smallest of the distances between  
starting and ending points, but try to keep the rest the same).

On Jul 30, 2008, at 11:20 PM, Graham Cox wrote:

> Just FYI: I just did a quick comparison of the route finder versus a  
> simple sort of x and y versus manual placement. The grid is regular  
> but diagonally offset so that the visitation order for the simple  
> sort is clear (this does increase the path lengths slightly but the  
> same arrangement was used in all tests). I think it shows that a  
> naive sort is pretty useless for this.
>
> If you know in advance that your objects are in a grid arrangement,  
> then you'd think you'd be able to come up with a visitation order  
> that is better than the route finder - but given a set of  
> arbitrarily placed objects, the problem becomes how to detect they  
> are in a grid in the first place. However, by manually placing the  
> objects in a specific order and doing no sorting at all, (bottom  
> image) the path length is *worse* than the route finder! So  
> intuition isn't always correct.
>
> Straight sort of Y, then X: (path length 9896.748047)
>
> <Picture 4.png>
>
>
> DKRouteFinder: (path length 4810.483887)
>
> <Picture 5.png>
>
>
> Manually placed and unsorted: (path length 5210.396973)
>
> <Picture 6.png>
> _______________________________________________
> Drawkit mailing list
> Drawkit at lists.apptree.net
> http://lists.apptree.net/listinfo.cgi/drawkit-apptree.net

______________________
Brad Larson
SonoPlot, Inc.
3030 Laura Lane, Suite 120
Middleton, WI 53562
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gridresult1.png
Type: image/png
Size: 5140 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080731/4e776e65/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gridresult2.png
Type: image/png
Size: 5087 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080731/4e776e65/attachment-0001.png>
-------------- next part --------------