[Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Legolas Woodland - 2006-02-11 21:39:47 ```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. ```
 [Inkscape-user] Re: [Graphic]How to minimize a head movement when we just have a list of points From: Roel Schroeven - 2006-02-11 21:52:03 ```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. -- If I have been able to see further, it was only because I stood on the shoulders of giants. -- Isaac Newton Roel Schroeven ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Jasper van de Gronde - 2006-02-11 21:54:39 ```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? ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Legolas Woodland - 2006-02-11 22:06:23 ```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 ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Jasper van de Gronde - 2006-02-11 22:11:30 ```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? ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Legolas Woodland - 2006-02-11 22:26:40 ```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. ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Jasper van de Gronde - 2006-02-11 22:33:18 ```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. ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Legolas Woodland - 2006-02-11 22:54:24 ```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 :( ```
 Re: [Inkscape-user] [Graphic]How to minimize a head movement when we just have a list of points From: Jasper van de Gronde - 2006-02-12 09:48:07 ```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). ```