[Graphic]How to minimize a head movement when we just have a list of points
Hi Thank you for reading my post , and I'm sorry if this place is not suitable place for this question I have a long list of all pixels in a bitmap for example , i have all X,Y of all pixels and now i want to draw the bitmap using those X,Y s Problem is that i send all this points to a Robotic like machine , and machine will use this points to draw the bitmap (by using sequential hits) on a metal surface. as you know in such machine we should minimize head (mechanical tool that hit the surface to make the bitmap) movement to achieve better overall performance . Now i should find an algorithm or method to sort those X,Y points in a way that head movement become minimum. is there such algorithm around ? Please if i post in wrong forum , let me know right place for this kind of questions Thank you.
Legolas Woodland schreef:
Hi Thank you for reading my post , and I'm sorry if this place is not suitable place for this question I have a long list of all pixels in a bitmap for example , i have all X,Y of all pixels and now i want to draw the bitmap using those X,Y s Problem is that i send all this points to a Robotic like machine , and machine will use this points to draw the bitmap (by using sequential hits) on a metal surface. as you know in such machine we should minimize head (mechanical tool that hit the surface to make the bitmap) movement to achieve better overall performance . Now i should find an algorithm or method to sort those X,Y points in a way that head movement become minimum. is there such algorithm around ?
That sounds like the Travelling Salesman Problem (http://en.wikipedia.org/wiki/Traveling_salesman_problem). I don't know an algorithm for that, but the wiki page lists some starting points.
Legolas Woodland wrote:
Hi Thank you for reading my post , and I'm sorry if this place is not suitable place for this question I have a long list of all pixels in a bitmap for example , i have all X,Y of all pixels and now i want to draw the bitmap using those X,Y s Problem is that i send all this points to a Robotic like machine , and machine will use this points to draw the bitmap (by using sequential hits) on a metal surface. as you know in such machine we should minimize head (mechanical tool that hit the surface to make the bitmap) movement to achieve better overall performance . Now i should find an algorithm or method to sort those X,Y points in a way that head movement become minimum. is there such algorithm around ? ...
Sounds like the travelling salesman problem (a quick search will find more than enough information, unfortunately an exact solution is quite costly). But is it necessary to go through a bitmap? Can't you use the SVG data more directly?
Jasper van de Gronde wrote:
Legolas Woodland wrote:
Hi Thank you for reading my post , and I'm sorry if this place is not suitable place for this question I have a long list of all pixels in a bitmap for example , i have all X,Y of all pixels and now i want to draw the bitmap using those X,Y s Problem is that i send all this points to a Robotic like machine , and machine will use this points to draw the bitmap (by using sequential hits) on a metal surface. as you know in such machine we should minimize head (mechanical tool that hit the surface to make the bitmap) movement to achieve better overall performance . Now i should find an algorithm or method to sort those X,Y points in a way that head movement become minimum. is there such algorithm around ? ...
Sounds like the travelling salesman problem (a quick search will find more than enough information, unfortunately an exact solution is quite costly). But is it necessary to go through a bitmap? Can't you use the SVG data more directly?
No , unfortunately i can not use SVG directly because i should use fonts (texts) and there is no way to draw some texts without having a vectorial representation of text .(for example each character is composed of many points ( some lesser lines) the is no way to find those lines so i must convert SVG to bitmap and then send the bitmap to Marking machine).
I do not understand this problem relation with TSP , indeed some days (in college) i implement TSP solution based on Genetic algorithms. but in this time we have two factor that we need to optimize at once.
Any help is really welcom
Legolas Woodland wrote:
No , unfortunately i can not use SVG directly because i should use fonts (texts) and there is no way to draw some texts without having a vectorial representation of text .(for example each character is composed of many points ( some lesser lines) the is no way to find those lines so i must convert SVG to bitmap and then send the bitmap to Marking machine).
I understand, but Inkscape can convert text to a path. You'll probably still have to convert bezier curves to a sequence of lines, but it could be a start.
I do not understand this problem relation with TSP , indeed some days (in college) i implement TSP solution based on Genetic algorithms. but in this time we have two factor that we need to optimize at once.
In that case I might have misunderstood, what do you need to optimize apart from the route the head makes?
Jasper van de Gronde wrote:
Legolas Woodland wrote:
No , unfortunately i can not use SVG directly because i should use fonts (texts) and there is no way to draw some texts without having a vectorial representation of text .(for example each character is composed of many points ( some lesser lines) the is no way to find those lines so i must convert SVG to bitmap and then send the bitmap to Marking machine).
I understand, but Inkscape can convert text to a path. You'll probably still have to convert bezier curves to a sequence of lines, but it could be a start.
It is very good news that It can convert each character of a text into a path (am i right ?) , but the stopper for me is about converting a path into smaller lines . by the way is that a feature of your SVG editor or other editor has the same future ?
I do not understand this problem relation with TSP , indeed some days (in college) i implement TSP solution based on Genetic algorithms. but in this time we have two factor that we need to optimize at once.
In that case I might have misunderstood, what do you need to optimize apart from the route the head makes?
we just need to optimize that , i was mistaken when posting that answer.
Legolas Woodland wrote:
Jasper van de Gronde wrote:
I understand, but Inkscape can convert text to a path. You'll probably still have to convert bezier curves to a sequence of lines, but it could be a start.
It is very good news that It can convert each character of a text into a path (am i right ?) , but the stopper for me is about converting a path into smaller lines . by the way is that a feature of your SVG editor or other editor has the same future ?
Pretty much every vector editor can do it as far as I know. In Inkscape you simply select the text object you want to convert to a path and select the convert to path action from the path menu.
I do not understand this problem relation with TSP , indeed some days (in college) i implement TSP solution based on Genetic algorithms. but in this time we have two factor that we need to optimize at once.
In that case I might have misunderstood, what do you need to optimize apart from the route the head makes?
we just need to optimize that , i was mistaken when posting that answer.
In that case it seems to me you could simply see each (black) pixel as a node, connected to its neighbours and use some TSP solution. You may want to do some preprocessing, and there might be a simpler solution, but I think it should work.
Jasper van de Gronde wrote:
Legolas Woodland wrote:
Jasper van de Gronde wrote:
I understand, but Inkscape can convert text to a path. You'll probably still have to convert bezier curves to a sequence of lines, but it could be a start.
It is very good news that It can convert each character of a text into a path (am i right ?) , but the stopper for me is about converting a path into smaller lines . by the way is that a feature of your SVG editor or other editor has the same future ?
Pretty much every vector editor can do it as far as I know. In Inkscape you simply select the text object you want to convert to a path and select the convert to path action from the path menu.
I can think about this feature , if i could find a way to convert a path into some small parts of lines
I do not understand this problem relation with TSP , indeed some days (in college) i implement TSP solution based on Genetic algorithms. but in this time we have two factor that we need to optimize at once.
In that case I might have misunderstood, what do you need to optimize apart from the route the head makes?
we just need to optimize that , i was mistaken when posting that answer.
In that case it seems to me you could simply see each (black) pixel as a node, connected to its neighbours and use some TSP solution. You may want to do some preprocessing, and there might be a simpler solution, but I think it should work.
It could take very long time as you know , using TSP for a bitmap with even a 20*20 pixel would take too long to calculate the best fitted path :(
Legolas Woodland wrote:
Jasper van de Gronde wrote:
Legolas Woodland wrote:
Jasper van de Gronde wrote:
I understand, but Inkscape can convert text to a path. You'll probably still have to convert bezier curves to a sequence of lines, but it could be a start.
It is very good news that It can convert each character of a text into a path (am i right ?) , but the stopper for me is about converting a path into smaller lines . by the way is that a feature of your SVG editor or other editor has the same future ?
Pretty much every vector editor can do it as far as I know. In Inkscape you simply select the text object you want to convert to a path and select the convert to path action from the path menu.
I can think about this feature , if i could find a way to convert a path into some small parts of lines
You might be able to do this yourself if the document isn't too complex (and with a bit more effort if it is) by using one of various techniques for evaluating a bezier curve (it's not extremely difficult and there are quite a number of reasonably well-documented methods). One very well-known method is De Casteljau's algorithm: http://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm The article has some pseudocode showing how to implement it.
In that case it seems to me you could simply see each (black) pixel as a node, connected to its neighbours and use some TSP solution. You may want to do some preprocessing, and there might be a simpler solution, but I think it should work.
It could take very long time as you know , using TSP for a bitmap with even a 20*20 pixel would take too long to calculate the best fitted path :(
I know, but there are quite a few heuristic methods you could use to get a decent approximation (like the genetic algorithms you mentioned).
participants (3)
-
Jasper van de Gronde -
Legolas Woodland -
Roel Schroeven