list of coordinates of the pixels of a line between 2 pixels

Questions and postings pertaining to the development of ImageMagick, feature enhancements, and ImageMagick internals. ImageMagick source code and algorithms are discussed here. Usage questions which are too arcane for the normal user list should also be posted here.
Post Reply
gubach
Posts: 45
Joined: 2013-12-13T11:13:29-07:00
Authentication code: 6789

list of coordinates of the pixels of a line between 2 pixels

Post by gubach »

Is there an internal way in IM to get the sorted list of coordinates of the pixels of a line (pointsize = 1) between two given pixels?
I have tried some analytical ways with the linear equation but if the absolute value of the slope is not 1 I get too many or too little pixels if I draw the resulting x- and y-list.

Or to put it in an other way: How is Draw computing the pixels when it draws a line?

Thank you very much for your help!
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: list of coordinates of the pixels of a line between 2 pixels

Post by fmw42 »

What is your IM version and platform? Please always provide that information.

If you have, say white line on a black background and want to list all the white (or non-black points), then you can do the following:

Code: Select all

convert image txt:- | grep "white"
or
convert image txt:- | grep -v "black"

Code: Select all

convert image txt:
will display every pixel coordinate and its color.

see http://www.imagemagick.org/Usage/files/#txt
snibgo
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: list of coordinates of the pixels of a line between 2 pixels

Post by snibgo »

gubach wrote:How is Draw computing the pixels when it draws a line?
Assuming you mean straight lines, it seems to use Wu's algorithm. See https://en.wikipedia.org/wiki/Xiaolin_W ... _algorithm

If you don't want anti-aliasing, Bresenham's algorithm is faster and simpler. See https://en.wikipedia.org/wiki/Bresenham ... _algorithm

Bresenham's algorithm is widely explained in Graphics primers, textbooks, etc.

I don't think IM has a mechanism for listing the points it draws, in the order it draws them. As Fred says, you can list them afterwards but they may not be in the same order.

EDIT: Of course, for straight aliased lines width=1, txt: or sparse-color: will list the points from one end to the other. If you care which end comes first, your script could invert the order afterwards, or "-flip" or "-flop" the image before listing the points.
snibgo's IM pages: im.snibgo.com
gubach
Posts: 45
Joined: 2013-12-13T11:13:29-07:00
Authentication code: 6789

Re: list of coordinates of the pixels of a line between 2 pixels

Post by gubach »

thank you for answering!

@fmw42
"txt:- | grep "white"" was helpful; it works but I have to write each time an intermediate image because I can't again port the syntax to PerlMagick (@list=$img->Get(?)). I have also improved the linear equation approach which takes some distinction of cases. The Black&White image https://www.flickr.com/photos/gbachelie ... ed-public/ shows left the IM draw, in the middle the linear equation approach and right the difference with src; sufficient for me.

@snibgo
straight line in black&white (= no anti-aliasing) is the case.
I will look in the Bresenham's algorithm; it seems it is also using the linear equation. Moore neighbourhod tracing would be a more general solution which covers not only straight lines but I could not find an implementation with Perl/PM.
yes, reverse the lists of x- and y-coordinates must be made in some of the cases in both the txt-grep and the linear equation method.
Post Reply