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

[Brad Larson]

This is almost exactly what I had in mind, although I hadn't proceeded  
past the sketching-it-out phase.  I was concerned about doing an  
O(N^2) sort on the elements, but the performance on this is nearly  
instant for even the most massive files (~2000 features) that I could  
find.

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.

Also, looking at this, I don't think it would be hard to do a second  
version of the nearest-neighbor that took two points for each feature:  
a starting and ending point.  The ending point would be used as the  
point that you would search for the next feature from, and the  
starting points would be what you'd determine distance from.  This  
way, lines that touch and continue from one to the next would be  
connected.  Once the point-based sorting works well, I'll give that a  
try.

On Aug 2, 2008, at 10:28 AM, Graham Cox wrote:

> 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.
>
>
> <DKRouteFinder.m><DKRouteFinder.h>
>
>
> 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
>
> _______________________________________________
> 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.m
Type: application/octet-stream
Size: 23420 bytes
Desc: not available
URL: <http://lists.apptree.net/pipermail/drawkit-apptree.net/attachments/20080804/b0c8c57b/attachment-0001.obj>