All this talk of windy rural postmen, the guy next door and the cat on the roof is very confusing to people who dont do programming
Jim
All this talk of windy rural postmen, the guy next door and the cat on the roof is very confusing to people who dont do programming
Jim
Yadda, sounds like you have been giving this some thought.
I just read up on the subject and see the point of framing it as a rural postman problem rather than a chinese postman problem because the distiction between arcs that need to be traveled and rural rouds that don't applies to the distiction between non blanked and blanked lines respectively. I'm not so clear on why windy, do you have any specific reason for that?
A windy graph is an undirected graph in which the cost of traversing an edge in a given direction can be different from the cost of traversing it in the opposite direction.
In our case the problem is windy because imported laser frames have a direction which is "preferred" and reversing the direction can undo any manual "point pulling" optimizations.
[added to explain more for the casual browser]
A directed graph is like a map of a city with one way roads.
An undirected graph lets you traverse the edge either way.
Most people are familiar with "shortest path through all points"... basically given a number of points and a distance between each of the points, find the shortest path which hits each point once. People do a phenomenally good job of this when planning road trips, and it is interesting that computers are classically terrible at it.
There is a modification to the shortest path requirements classically known as the "traveling salesman problem" where you are now looking for the shortest path through all points that drop you back where you started after you are done traversing.
The problem with solutions to the two algorithms is that for laser frames is that you will have to force it into a mixed sequence of directed graphs and it doesn't require that the beam traverse a given edge so you have to do a lot of weights to "trick" it into behaving.
Back many moons ago, a chinese guy did some research on a shortest path for postmen where they have to traverse every street along their route and then go home. The discovery was that if the route did not create a Eulerian circuit, you could algorithmically determine a road to backtrack on (thus creating a Eulerian circuit) and solve it using Markov chains rather elegantly... the problem was thereinafter known as the "chinese postman problem"... There is a variant called the New York Garbage Truck problem which assigns additional "cost" to certain routes (nobody wants a huge garbage dump truck through their neighborhood)...
The shortest path algorithms currently used by all of the commercial laser software packages are very far from optimal because they use traditional "fast" heuristics to minimize the calculation time. This optimization is no longer required IMHO because of how insanely fast modern systems are. For the number of points which a scanhead can display, we can tackle the optimal or very close to optimal solutions in a reasonable amount of time.
The rural postman problem creates further rules by allowing one to determine which edges must be traversed and which are optional. Hence the rural postman problem is one of the most apt fits to the problem of organizing a frame. It is quite optimal for new frames generated from software which can compute the anchor points. However, as stated above, frames which are imported have a certain preference for direction which we can weight appropriately on a per object basis by using a windy rural postman solution.
Last edited by yaddatrance; 03-23-2007 at 16:43.
Very cool. I'm lousy at maths, so this is inspiring. I heard of the travelling salesman, but that's about as far as I got in this direction.
There is another thing that computers are bad at in some ways, that's sorting stuff. I wanted to code a sort that was stable and fast. Once I got in deep, I learned of various methods that were either fast OR stable, but not both. I needed both. I GOT both. I tricked it. What I did was label the items in their current order by prefixing them with number strings, then I sorted by two keyed columns, first the main one with the stuff I wanted, then the numbers I'd added as second priority. I used the fastest algorithm I knew (in this case the one supplied by Lua, the language I was using), then stripped the numbers off each string. A stable bubble sort in Lua would have taken DAYS to sort the 60K lines I was working on, but this trick did it in about 7 seconds.
I bring this up because I'm wondering if similar trickery might work. A computer could never have invented such a trick, but a human brain can, and did, so by looking at the intractable problem of routing, maybe in terms of various apparent unrelated forms of geometry, might it be possible to trick a machine into making the kind of 'intuitive' leaps that we can make? I'm wondering what might have been tried on the routing problem, as if I ever write more attempts at laser scan generation, it would be nice to try to automate routing instead of relying on human ability to do it.
One possibility that might offer a way is ray tracing. Not sure how, but I heard recently that this long and intensive task was recently reworked so it can be efficient and fast, done in video hardware for better games rendering and such, so maybe they've found something that can be applied. Ray tracing doesn't seem that far removed from routing problems...
Edit: For those not familiar, 'stable sort' means that, if equal, two items must remain in the same order they started in, when the sort is done.
Last edited by The_Doctor; 03-24-2007 at 05:14.
Thanks Yadda, that makes perfect sense.
Will be looking into it further but for now I want to focus on on the svg to laserpoints algorithm.
For those intersted I found two applets showing the differences in algorithms for the TSP.
compare nearest neighbour, 2opt and genetic algoritms note how fast the 2opt and better than nearest neighbour. GA gives an additional 10% improvement.
another GA approach
@ TL, haven't had time yet to look at your stuff but sounds really promising! Looking forward to trying it.
[QUOTE=TL;20679]Yes, I'm interested, too...
I'm currently working on a plugin (using python) for Blender3D (http://www.blender3d.org) to render 3D scenes & animations to ILDA files...
That sounds cool, do you have a working version?
hmm, partial working...
in fact it actually uses either the painter or newell algorithm as hidden line algorithm, so only convex objects (like cubes, but no cubes with holes) are rendered correctly. Also if objects are overlapping they are not intersected...
These issues are gone, when the weiler atherthon algorithm is implemented, but this will take some time...
Animation rendering is working...
Another thing is sorting the points, which is actually done quick & dirty. Here's also some more work needed, but I think it's more important to implement the right hidden line algorithm first. Other options like line interpolating, corner repeat points, etc. are working...
Here you can see a screenshot from blender with the plugin: Click me
And here's a screenshot of the scene in Anarchy: Click me
Both images are linked because of the size...
Thomas
KVANT Australian projector sales
https://www.facebook.com/kvantaus/
Lasershowparts- Laser Parts at great prices
https://www.facebook.com/lasershowparts/
I don't want to go too far off topic - but since the board is only single-sided you could make it at home using something like Press-n-peel Blue
(http://www.allelectronics.com/cgi-bin/item/TEK-5/445/TECHNIKS_"#34;PRESS_"#38;_PEEL"#34;_PC_BOARD_KIT_. html)
I've used this before and it works real nice... To buy the etchant, board, and press-n-peel you might spend $40 but you'd have enough for this board and probably lots more.
-Andy
hint: for etching use hydrochloric acid and hydrogen peroxide.
now back on topic :P
KVANT Australian projector sales
https://www.facebook.com/kvantaus/
Lasershowparts- Laser Parts at great prices
https://www.facebook.com/lasershowparts/