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

[Brad Larson]

You're right, that starts things off at the right point.  I added a  
quick search routine at the beginning of the nearest neighbor method  
to find the point closest to 0,0.

I was still having problems with the result not starting at the right  
point until I saw that in the sortedArrayFromArray: method you were  
assuming an index of 0 for the first point in the list (based on the  
previous symmetric search).  If any other point is the upper-left  
point, this causes weird results.  I added an instance variable to act  
as a holder for the correct index of the starting point.  With this in  
place, it is now perfectly optimizing the grids.

I was also seeing some bizarre behavior with patterns containing lines  
where some were dropped and others duplicated.  That came about  
because the line

mOrder[++k] = [points indexOfObject:[mVisited lastObject]] + 1;

in the sortArrayUsingNearestNeighbour: method would run into a problem  
if two lines had the same starting point.  The index for the first  
line would be used when the second line came up.  To fix this, I  
created a parallel array of indices that can be used to track the  
unique items as they pass through the sort.

This is close to complete, but it still does not recognize lines,  
arcs, and other features that are touching and that we'd want to draw  
in one motion, so I'm going ahead with a version that uses two points  
for each object and finds nearest neighbors based on those two points.

On Aug 5, 2008, at 8:03 AM, Graham Cox wrote:

> Not sure exactly what the problem is, but it would be better to  
> start at the top, left point of a notional bounding box of the  
> objects. Then you know that searching east should find something  
> sensible in your object set. Starting at 0,0 might put the ideal  
> first object outside the visibility of the NN search for a given  
> direction.
>
> cheers, Graham
>
>
> On 5 Aug 2008, at 9:16 am, Brad Larson wrote:
>
>> Testing it out, it's very close, but I'm having a problem with the  
>> fact that the pathfinding starts at the first element drawn, rather  
>> than the zero point.  This means that if you have a grid, and the  
>> first point you drew was in the middle of the grid, you'll get a  
>> nonoptimal path.  Our dispenser always starts from the 0,0 point  
>> when drawing, so this also reflects the actual behavior of the  
>> device.  I tried modifying the nearest-neighbor to do this by  
>> inserting a 0,0 point as the first point to test against, then  
>> removing that 0,0 point at the end, but I'm getting weird behavior  
>> from it (dropped lines, jumpiness at the start) so I must not be  
>> doing it the right way.
>
> _______________________________________________
> 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: DKRouteFinder.h
Type: application/octet-stream
Size: 3090 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080805/f3e07387/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DKRouteFinder.m
Type: application/octet-stream
Size: 24645 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080805/f3e07387/attachment-0003.obj>