Weekly Programming Challenge #4

Drawing Lines

I’m running a bit behind this week! Vacationing on beautiful Vashon Island has me struggling to keep up with my usual schedule. Plenty to do around here — the farmer’s market, the beach, hiking…lots of activities!

Some of my favorite programming activities are those that involve producing graphical output. There’s just something really satisfying about having the results of my experiments displayed visually, whether it be drawing mazes, curves, knots, or graphs. To that end, this week’s programming challenge will be drawing lines!

But first, let’s recap last week’s challenge…

Recap: Challenge #3

Last week’s challenge was to write a program that would solve mazes. Hard
mode was to find the shortest solution to a maze with multiple possible
solutions. And here’s the coolest thing: everyone that submitted a solution,
did hard mode!

Two in particular qualify for “surprise me”, I think:

1. Jens Nömtak’s solution was in Javascript and Node.js (https://github.com/flixo/mazes), and it also displays the path through the maze visually!
2. Martin Moberg did his submission in Cloure (https://github.com/indifferen7/casual-m), and displays the paths visually, too.

The other hard mode submissions:

1. Lasse Ebert went with Elixir: https://github.com/lasseebert/jamis_challenge/tree/master/003_maze
2. Steve Desmond wrote his in C#: https://github.com/stevedesmond-ca/WeeklyChallenges/tree/master/03-Maze
3. Alejandro Perea implemented his in Javascript: https://github.com/aeperea/programming-challenges/tree/master/03-mazes

I gave it a try in Elixir, for the first time, and was pleasantly surprised that I was able to wrap my mind around it enough to succeed at hard mode! You can see my submission here: https://github.com/jamis/weekly-challenges/tree/master/003-maze-solver

Now, on to challenge #4!

Programming Challenge #4

For this challenge, you’re not allowed to use any graphics or image library. None! In short, you will represent an image as a raw matrix of RGB pixel values, which you’ll draw to using a minimal API of your own invention. When you’re done drawing to it, you’ll write it out to a file in PPM format.

Let’s break this down.

First, the raw image data. You must represent the image as an array of (at least) RGB values, where each color is (at least) 8 bits in size. That is to say, each pixel will be three numbers: red (0–255), green (0–255), and blue (0–255). If you wish to support an alpha channel, that’s fine as well. Your image API only needs to support a single method, “draw pixel”, to write a pixel of a given color, to a given (x,y) coordinate. (More methods are fine, if you want to go nuts — but you only need to support the one method.)

Second, drawing! This is the fun part. You’ll get to implement Bresenham’s line algorithm (which should be really, really easy, because there is pseudocode for it all over the Internet). You should allow arbitrary lines, with arbitrary start and end points, in arbitrary colors.

Third, write it as a PPM file. You may use either the ASCII (P3) format, or the binary (P6) format. (If you have trouble finding an app that can view PPM files, you may use a tool like ImageMagick to convert your output to PNG or whatever pleases you.)

That’s it! Doing just that will score you a “normal mode” submission. For hard mode, then… Let’s try something a bit different this time.

Grading

Normal mode is, as stated before, these three things:

• Simple image API, drawing an RGB color to a given coordinate
• Bresenham’s line algorithm
• Save image as PPM file (either P3 or P6 format)

We’ll call that the basis, and give you one point for those three things together. For each of the following options, you’ll earn another point:

• Thick lines. Allow your line drawing routing to accept a “line width” parameter.
• Line styles (at least dashed and dotted, but feel free to experiment!)
• Anti-aliased lines! Implement Xiaolin Wu’s line algorithm, instead of Bresenham’s.
• In addition to lines, also implement the midpoint circle algorithm.
• If the midpoint circle algorithm isn’t challenge enough, adapt it to draw arcs (segments of a circle)! You should specify either (a) a start point, end point, and a radius, or (b) an origin, a start angle, and an end angle.
• Each additional file format that you support for saving the image, earns you another point. Note that you must write the routines for formatting the image yourself!

And if you really want to get creative, shoot for “surprise me” mode! This doesn’t need to be viciously difficult, but it ought to be something more than the basics, applied in a way that is unexpected or thoughtful. See what you can come up with!

This challenge will run until Saturday, August 27th, at 12:00 MDT (18:00 UTC).

Submissions are now closed for this challenge, but feel free to try your hand at it anyway! If you’re following along, the next week’s challenge is “Priority Queues and Binary Heaps”. See you there!