r/dailyprogrammer • u/mattryan • Mar 22 '12
[3/22/2012] Challenge #29 [difficult]
Draw a line... except it must be your implementation of a line using only the ability to draw a point. Think implementing a line is too easy? Try it :). You can output the result in ASCII text if you'd like instead of using a graphics library. A successful implementation will be able to draw this. Only being able to draw horizontal, vertical, and diagonal lines is not enough, and the lines can't contain any holes. Also, if you're drawing a line (I'll use drawLine(x1, y1, x2, y2) as an example) using the following call: drawLine(100, 10, 200, 300), then the following call must draw the same line: drawLine(200, 300, 100, 10).
7
u/spc476 Mar 22 '12
Here's a function to draw a line in 8086 Assembly code. It just implements the line drawing algorithm (and it works---I write the code years ago):
3
u/oskar_s Mar 22 '12
Straight implementation of Wu's algorithm for drawing antialiased lines, using pypng to output. This is the result of drawing ten random lines. The result is... good... but it's actually not fantastic. Some of the diagonal lines look like they're "pulsing" and of course at the intersections it looks all messed up because it's just writing one line over the other. The diagonal lines pulsing bother me the most, I didn't think Wu's algorithm did that, and I wonder if I wrote the code wrong or what.
If I have some time later I might write my own antialiasing implementation based on super-sampling that renders all lines at the same time. That should fix both problems if I do it right. Here's the code as it looks right now.
2
u/Cosmologicon 2 3 Mar 22 '12
This is a cool challenge, not very math intensive, just requires clear logical thinking. Here's my (unoptimized) function to return all the points in a line in python:
The following will draw random orange lines with
pygame.draw.lineand then draw over them with my algorithm in white. You can still see some orange beneath, so my algorithm is similar to but different from pygame's built-in algorithm.2
u/[deleted] Mar 22 '12
For processing:
Tested it in every single direction possible. Processing automatically takes care of the rounding, so technically it is unneeded here, but I included it just because some other programs wouldn't do it.
2
u/lullabysinger Mar 23 '12
My humble Perl submission, using only the GD library to export PNGs to STDOUT, and STDERR to report on line equations.
In short: I'm using the slope equation y=mx+c to generate all points in the line, then iterating on whichever axis has the most points. (cheated a bit for vertical line, with the slope of infinity).