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

[Graham Cox]

Hi Brad,

For the grid case, I'm also seeing a "snaking" effect rather than just  
marching along rows and columns. That is just an effect of the  
algorithm, though I must admit way back when I ported this originally,  
I recall that it did scan across a grid in the expected way, so maybe  
something changed. In terms of overall path length it shouldn't matter  
but there could be other considerations of course.

For handling the line order, you'll need to do more. The route finder  
will only find the shortest path from point to point, and disregards  
any ordering that must be maintained for short runs of points (like  
along a line). A modification of the algorithm could work on point  
pairs (or lines) representing the start and end points of each object  
to be visited. Then at least you'd know that the travel from the end  
of each shape to the next would be minimised. To do that you'll need  
to get into the workings of the routing algorithm, so it may not be  
trivial. You'll still end up with rather random motion from object to  
object, though it should minimise the overall distance travelled. You  
could also group the objects into sets according to which pen they are  
drawn with, and route each set separately. That will avoid pen changes  
- it will draw all objects with one pen in optimal order, change pen,  
then draw the next group, etc. This is what you'd do for a CNC drill  
for PCB manufacture for example - group all holes according to size  
and route each separately.

To avoid picking up the pen when two lines touch, I wonder if this  
could be better handled by physically merging touching objects into  
one so it can be treated as a unit. DKb4 has code that will find  
intersections between two paths (courtesy of Omni frameworks) so you  
could use that to detect those cases.

Anyway, I can see this isn't going to be solved overnight, but good  
luck!

cheers, Graham



On 31 Jul 2008, at 9:08 am, Brad Larson wrote:

> Holy crap.  I was just looking for a suggestion, not a full route- 
> finding class!  What's next, using a genetic algorithm to improve  
> sorting performance?
>
> I've attached the file handling category with the added sorting  
> functionality built in.  If you overwrite the files in the Beta 1  
> source with these and add the DKRouteFinder to the project, it  
> should add in the sorting before saving.  So far, I'm getting odd  
> results, but I can't tell if that's entirely on my end or what.   
> I've attached two simple examples, one a box made of lines and the  
> other a grid of spots.  These were saved using this code.  For the  
> grid of spots, rather than rastering across the rows and columns  
> like the optimal path should be, the spots are placed in a snaking  
> order.
>
> Lines are trickier.  Since our system operates like a pen plotter,  
> we'd like to have lines or arcs that touch one another be drawn in a  
> single stroke, rather than draw a line, pick up the pen, and draw  
> another line somewhere else.  First off, this means that the start  
> and end points of the line have to be in the right order.  As a  
> kludge, I created a method that goes through the objects in an  
> array, checks to see if a line's end point touches the end point of  
> a previously drawn line, and if so swaps the starting and ending  
> points of the line so that its starting point matches the other  
> object's ending point.  I run this before the sort, hoping that the  
> route finding through the starting points will sort in the proper  
> order.  As can be seen in the box example, that isn't the case right  
> now.  In fact, the elements look like they might in the opposite  
> order from what I expected.
>
> I'm just starting to test this, but I thought I'd let you know what  
> I'm seeing so far.  There's a lot more experimentation that I need  
> to do.