June 27th, 2012

Whovian robo-spider

Algorithm

Okay, I started this more than a week ago and got stalled-out partway through and haven't posted about all kinds of other interesting things since then, so I am just going to finish it off to get it out of my brain.

I was working on a problem for a couple days because I had an interesting idea for a solution and was compelled to try it out. Like, even though it wasn't all that important, I just HAD TO KNOW whether it would work.

So here's the problem: you've got a region that's defined with a grid. You want to draw a line around the edge of the region. How do you find the points that define the boundary of your region?

Which is to say, you've got a (square) grid of locations, and the grid cells that are a part of the region have a value of 1, and all the other grid cells have a value of 0. You know the coordinates for the center of each grid cell. You can assume the region is all in one piece and has no holes in it. You need the coordinates of points all along the edge of the region, and they need to be sorted in order, such that if you draw line segments from one to the next, you've outlined the region. Even better if you can find the minimal set of points to define the region. Best of all is if you can also figure out a way to get rid of stair-steps along diagonals -- but if you do that, it has to be in such a way that two adjacent regions won't overlap.

(And for anybody doing a tech hire, I think this might make a good interview question.)

Collapse )

I was gonna post my resulting code, but I don't have access to it at the moment and I want to be done with this, so that'll have to do.