I'm too lazy right now to make the code neatly arranged so attached is the quick'n'dirty code. It's a C# console application that reads an image, figures out the required points, and outputs an image showing them. It also outputs intermediate images showing the steps taken to get to that point. I've also attached one of these sample output images.
EDIT: Apparently it doesn't let me attach source code files. Well here is the entire file:
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
namespace Vector
{
struct Point
{
public static readonly Point Zero = new Point(0,0);
public double X;
public double Y;
public Point (double x, double y)
{
X = x;
Y = y;
}
public override string ToString ()
{
return "{" + X + "," + Y + "}";
}
}
class Polygon
{
public List<Point> Points;
public Polygon ()
{
Points = new List<Point>();
}
}
class Path
{
public List<Point> Points;
public bool[,] EdgeMap;
public Path (bool[,] edgeMap, IEnumerable<Point> points)
{
EdgeMap = (bool[,])edgeMap.Clone();
Points = new List<Point>();
Points.AddRange(points);
}
}
class Program
{
static readonly double EDGE_OFFSET_THRESHOLD = 1;
static readonly string INPUT_PATH = @"A:\Data\shape.png";
static void Main (string[] args)
{
Bitmap bmp = (Bitmap) Image.FromFile(INPUT_PATH);
bool[,] edgeMap;
int edgeCount;
FindEdges(bmp, out edgeMap, out edgeCount);
Bitmap output = new Bitmap(bmp.Width, bmp.Height);
for (int y = 0; y < bmp.Height; y++)
for (int x = 0; x < bmp.Width; x++)
{
if (edgeMap[x,y])
output.SetPixel(x, y, Color.White);
else
output.SetPixel(x, y, Color.Black);
}
output.Save(INPUT_PATH + ".edges.png", ImageFormat.Png);
// Now find the polygons:
List<Polygon> polygons = new List<Polygon>();
while (edgeCount > 0)
{
// Remove any point to start a new polygon
Point point = FindRandomEdge(edgeMap);
edgeMap[(int) point.X, (int) point.Y] = false;
// Create the first path
Path path = new Path(edgeMap, new Point[0]);
path.Points.Add(point);
List<Path> paths = new List<Path>();
paths.Add(path);
EvaluatePath(path, paths);
// Now look through the list of paths to find the one(s) with the
// most points. There may be two with the same number of points;
// just choose the first one arbitrarily in that case.
Path bestPath = null;
int bestCount = 0;
foreach (Path option in paths)
{
Point first = option.Points[0];
Point last = option.Points[option.Points.Count-1];
// Look for the path that has all the points and that
// correctly forms a closed polygon.
if (first.X >= last.X-1 &&
first.X <= last.X+1 &&
first.Y >= last.Y-1 &&
first.Y <= last.Y+1 &&
option.Points.Count > bestCount)
{
bestCount = option.Points.Count;
bestPath = option;
}
}
edgeCount -= bestCount;
// Create the new polygon
Polygon polygon = new Polygon();
polygon.Points.AddRange(bestPath.Points);
polygons.Add(polygon);
edgeMap = bestPath.EdgeMap;
}
output = new Bitmap(bmp.Width, bmp.Height);
for (int y = 0; y < bmp.Height; y++)
for (int x = 0; x < bmp.Width; x++)
output.SetPixel(x, y, Color.Black);
for (int n = 0; n < polygons.Count; n++)
{
for (int p = 0; p < polygons[n].Points.Count; p++)
output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, GetPolygonColor(n));
}
output.Save(INPUT_PATH + ".polygons.png", ImageFormat.Png);
// Now we need to remove useless edge pixels until we only have the corners remaining.
foreach (Polygon polygon in polygons)
{
int p = 0;
while (p < polygon.Points.Count)
{
Point start = polygon.Points[p];
int removeCount = 0;
for (int n = 2; n < polygon.Points.Count; n++)
{
int endIndex = (p+n) % polygon.Points.Count;
Point end = polygon.Points[endIndex];
bool removeToEnd = true;
// Now see if all pixels between start and end are within the allowed distance
// from the line from start to end. If so then keep going. Otherwise we are done
// and can eliminate any pixels between start and end.
for (int m = 1; m < n; m++)
{
int middleIndex = (p+m) % polygon.Points.Count;
Point middle = polygon.Points[middleIndex];
double distance = GetPointSegmentDistance(middle, start, end);
if (distance > EDGE_OFFSET_THRESHOLD)
{
// We've found a pixel that must not be removed so stop here.
removeToEnd = false;
break;
}
}
if (removeToEnd)
removeCount = n-1;
else
break;
}
if (removeCount > 0)
{
int firstRemoval = (p+1) % polygon.Points.Count;
int lastRemoval = (p+removeCount) % polygon.Points.Count;
// We've found at least one pixel to remove.
if (firstRemoval <= lastRemoval)
{
polygon.Points.RemoveRange(firstRemoval, 1+lastRemoval-firstRemoval);
p++;
}
else
{
polygon.Points.RemoveRange(firstRemoval, polygon.Points.Count - firstRemoval);
polygon.Points.RemoveRange(0, 1+lastRemoval);
break;
}
}
else
p++;
}
}
for (int n = 0; n < polygons.Count; n++)
{
for (int p = 0; p < polygons[n].Points.Count; p++)
output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, Color.White);
}
output.Save(INPUT_PATH + ".corners.png", ImageFormat.Png);
}
static void FindEdges (Bitmap bmp, out bool[,] edgeMap, out int edgeCount)
{
edgeMap = new bool[bmp.Width, bmp.Height];
edgeCount = 0;
// Important: do not count diagonals.
for (int y = 1; y < bmp.Height-1; y++)
{
for (int x = 1; x < bmp.Width-1; x++)
{
if (bmp.GetPixel(x, y).R > 0)
{
// This is a foreground pixel (part of the polygon).
// Count how many surrounded pixels are the background.
int count = (bmp.GetPixel(x-1, y).R == 0 ? 1 : 0) +
(bmp.GetPixel(x+1, y).R == 0 ? 1 : 0) +
(bmp.GetPixel(x, y-1).R == 0 ? 1 : 0) +
(bmp.GetPixel(x, y+1).R == 0 ? 1 : 0);
if (count > 0 && count < 4)
{
// It counts as an edge
edgeMap[x, y] = true;
edgeCount++;
}
}
}
}
// Now we have to eliminate any edge pixels that are adjacent (including diagonally)
// to only one other edge pixel; they are dead-ends.
bool outliersFound = true;
while (outliersFound)
{
outliersFound = false;
for (int y = 1; y < bmp.Height-1; y++)
{
for (int x = 1; x < bmp.Width-1; x++)
{
if (edgeMap[x, y])
{
int count = (edgeMap[x-1, y-1] ? 1 : 0) +
(edgeMap[x-1, y] ? 1 : 0) +
(edgeMap[x-1, y+1] ? 1 : 0) +
(edgeMap[x, y-1] ? 1 : 0) +
(edgeMap[x, y+1] ? 1 : 0) +
(edgeMap[x+1, y-1] ? 1 : 0) +
(edgeMap[x+1, y] ? 1 : 0) +
(edgeMap[x+1, y+1] ? 1 : 0);
if (count == 1)
{
edgeMap[x, y] = false;
edgeCount--;
outliersFound = true;
}
}
}
}
}
}
static double GetPointLineDistance (Point p, Point lineA, Point lineB)
{
double length = GetLength(lineA, lineB);
double xAP = lineA.X - p.X;
double yAP = lineA.Y - p.Y;
double xBA = (lineB.X - lineA.X) / length;
double yBA = (lineB.Y - lineA.Y) / length;
return (xAP * yBA) - (yAP * xBA);
}
static double GetNearestPointOffsetOnLine (Point p, Point lineA, Point lineB)
{
double xAP = p.X - lineA.X;
double yAP = p.Y - lineA.Y;
double xAB = lineB.X - lineA.X;
double yAB = lineB.Y - lineA.Y;
double ABdotAB = (xAB*xAB) + (yAB*yAB);
double APdotAB = (xAP*xAB) + (yAP*yAB);
if (ABdotAB != 0)
return APdotAB / ABdotAB;
else
return double.NaN;
}
static Point GetPointOnLine (Point lineA, Point lineB, double offset)
{
double x = lineA.X + (offset * (lineB.X - lineA.X));
double y = lineA.Y + (offset * (lineB.Y - lineA.Y));
return new Point(x, y);
}
static double GetPointSegmentDistance (Point p, Point segmentA, Point segmentB)
{
double offset = GetNearestPointOffsetOnLine(p, segmentA, segmentB);
if (offset <= 0)
return GetLength(p, segmentA);
else if (offset >= 1)
return GetLength(p, segmentB);
else
return GetLength(p, GetPointOnLine(segmentA, segmentB, offset));
}
static double GetLength (Point p1, Point p2)
{
double dx = p1.X - p2.X;
double dy = p1.Y - p2.Y;
return Math.Sqrt((dx*dx) + (dy*dy));
}
static Color GetPolygonColor (int index)
{
switch (index)
{
case 0:
return Color.FromArgb(64, 0, 0);
case 1:
return Color.FromArgb(64, 64, 0);
case 2:
return Color.FromArgb(0, 64, 0);
case 3:
return Color.FromArgb(0, 64, 64);
case 4:
return Color.FromArgb(0, 0, 64);
case 5:
return Color.FromArgb(64, 0, 64);
default:
return Color.FromArgb(64, 64, 64);
}
}
static void EvaluatePath (Path path, IList<Path> allPaths)
{
while (true)
{
List<Point> adjacent = FindAdjacentEdges(path.EdgeMap, path.Points[path.Points.Count-1]);
if (adjacent.Count >= 2)
{
// Multiple options so create new paths for each option.
for (int a = 0; a < adjacent.Count; a++)
{
Path branch = new Path(path.EdgeMap, path.Points);
branch.Points.Add(adjacent[a]);
branch.EdgeMap[(int) adjacent[a].X, (int) adjacent[a].Y] = false;
allPaths.Add(branch);
EvaluatePath(branch, allPaths);
}
// This path must be abandoned now.
break;
}
else if (adjacent.Count == 1)
{
// Only one direction to go.
path.Points.Add(adjacent[0]);
path.EdgeMap[(int) adjacent[0].X, (int) adjacent[0].Y] = false;
}
else
{
// No more adjacent pixels; we're done with this path
break;
}
}
}
static Point FindRandomEdge (bool[,] edgeMap)
{
for (int y = 1; y < edgeMap.GetLength(1)-1; y++)
for (int x = 1; x < edgeMap.GetLength(0)-1; x++)
{
if (edgeMap[x, y])
return new Point(x, y);
}
return Point.Zero;
}
static List<Point> FindAdjacentEdges (bool[,] edgeMap, Point point)
{
List<Point> list = new List<Point>();
for (int y = (int) point.Y-1; y <= (int) point.Y+1; y++)
for (int x = (int) point.X-1; x <= (int) point.X+1; x++)
{
if (x == point.X && y == point.Y)
continue;
if (edgeMap[x, y])
list.Add(new Point(x, y));
}
return list;
}
}
}