Steve on Image Processing and MATLAB

Concepts, algorithms & MATLAB

Cody problem solvers: simplify a polygon

A couple of weeks ago I posted about how one might want to simplify the output of bwboundaries in order to remove unneeded vertices in the output boundaries. That is, turn this polygon:

into this one:

At the same time, I created a new problem on Cody called "Eliminate unnecessary polygon vertices" and invited everyone to try it.

Well, in the last sixteen days or so, almost 300 solutions have been submitted for this problem!

I've been putting off writing a follow-up blog post because there's so much interesting to look at in the various solution attempts. But I decided today that I need to at least go ahead and recognize the efforts of everyone who participated in this effort.

(As an aside, the MATLAB Community team released updates to Cody just this week that make it a lot easier to see who has solved a problem and to search for all solutions by a particular player. That helped me a lot; thanks, team!)

By clicking on the "Solvers" button I can see the eight players who (as of this writing) have submitted correct solutions to this problem:

I especially appreciate the input from Sven, Richard, and Cris, who all helped "debug" my initial test suite in the first few hours.

Sven and Richard engaged in a very impressive tag team effort over the course of several days to find the smallest solution.

And I want to recognize Sagiv for making this his first solved Cody problem! (But keep going, Sagiv, try some more!)

When I was looking at various solutions, I found it helpful to create a function to help visualize them. You can download my visCody820Solution.m file from here. (You'll also need arrow.m by Erik Johnson.)

For example, here is the visualization of one of the test cases.

Next time I'll write about some of the interesting concepts and MATLAB techniques raised by this problem and its many solutions, including:

  • Making sure the problem is well defined
  • Floating-point round-off error and the use of tolerances (or not)
  • diff
  • circshift
  • modulo (or periodic) indexing
  • bsxfun
  • Subtle behaviors of function input and output arguments
  • The "automatic" output variable ans
  • Philosophical meanderings about the merits of the Cody solution scoring method




Published with MATLAB® 7.14

|

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.