You are viewing a plain text version of this content. The canonical link for it is here.
Posted to batik-dev@xmlgraphics.apache.org by Legolas Woodland <le...@gmail.com> on 2006/02/11 22:40:04 UTC
[Graphic]How to minimize a head movement when we just have a list
of points and need to draw the bitmap again
Hi
Thank you for reading my post , and Im 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.
---------------------------------------------------------------------
To unsubscribe, e-mail: batik-dev-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: batik-dev-help@xmlgraphics.apache.org
Re: [Graphic]How to minimize a head movement when we just have a list of points and need to draw the bitmap again
Posted by Cameron McCormack <ca...@aka.mcc.id.au>.
Hi Legolas.
Legolas Woodland:
> Thank you for reading my post , and Im sorry if this place is not
> suitable place for this question
Probably not the right place, but no matter...
> 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 ?
This general problem is the Travelling Saleseman Problem[1,2], which
unfortunately is NP hard. You may have luck with some heuristic
algorithms that result in a "good" solution, but still not minimal.
Cameron
[1] http://en.wikipedia.org/wiki/Traveling_salesman_problem
[2] http://mathworld.wolfram.com/TravelingSalesmanProblem.html
--
Cameron McCormack ICQ: 26955922
cam (at) mcc.id.au MSN: cam (at) mcc.id.au
http://mcc.id.au/ JBR: heycam (at) jabber.org
---------------------------------------------------------------------
To unsubscribe, e-mail: batik-dev-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: batik-dev-help@xmlgraphics.apache.org
Re: [Graphic]How to minimize a head movement when we just have a list of points and need to draw the bitmap again
Posted by Ronan Oger <ro...@roasp.com>.
...this looks a lot like a student question.
And this is probably not the right place for this question.
You say you need to hit every pixel in your bitmap.
You need to do an S track, scan line by scan line, starting at the extreme of
one scan line. This will give you the lowest amount of travel.
pseudo code:
1) sort by x.
2) for each x, sort by y.
3) flip the order of the y points for odd values X.
Ronan
On Saturday 11 February 2006 21:40, Legolas Woodland wrote:
> Hi
> Thank you for reading my post , and Im 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.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: batik-dev-unsubscribe@xmlgraphics.apache.org
> For additional commands, e-mail: batik-dev-help@xmlgraphics.apache.org
--
Ronan Oger
Director
RO IT Systems GmbH
...Building Web2.0 with SVG since 2001
http://www.roitsystems.com
---------------------------------------------------------------------
To unsubscribe, e-mail: batik-dev-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: batik-dev-help@xmlgraphics.apache.org