Takes a 2d array of bools (representing squares on a grid) and gives you the polygon that wraps those squares

SquaresToPolygonGenerator.cs

    /// <summary>
    /// C# port of http://raksy.dyndns.org/cycle_collection.py via http://stackoverflow.com/questions/8946563/add-square-to-polygon-composed-of-squares
    /// </summary>
    static class SquaresToPolygonGenerator
    {
        static readonly Coordinate[] directions = new[]
                                                      {
                                                          Coordinate.West, 
                                                          Coordinate.South, 
                                                          Coordinate.East, 
                                                          Coordinate.North, 
                                                      };

        public static Geometry GetPolygon(bool[][] b)
        {
            var edges = new HashSet<Edge>();
            var edgeMap = new Dictionary<Coordinate, List<Edge>>();
            var cols = b[0].Length;
            var rows = b.Length;

            for (int c = 0; c <= cols; c++)
            {
                for (int r = 0; r <= rows; r++)
                {
                    var cell = GetCell(c, r, b);
                    var westCell = GetCell(c - 1, r, b);
                    var northCell = GetCell(c, r - 1, b);
                    if (northCell != cell)
                    {
                        AddEdge(new Edge(c, r, c + 1, r), edges, edgeMap);
                    }

                    if (westCell != cell)
                    {
                        AddEdge(new Edge(c, r, c, r + 1), edges, edgeMap);
                    }
                }
            }

            var cycles = new List<List<Coordinate>>();

            while (edges.Count > 0)
            {
                var edge = edges.First();
                RemoveEdge(edge, edges, edgeMap);

                if (IsEdgeLeftHand(b, edge))
                {
                    edge = edge.Reversed();
                }

                var currentCycle = new List<Coordinate> { edge.From, edge.To };
                while (edge.To != currentCycle[0])
                {
                    var moves = from direction in Turns(edge.From - edge.To)
                                let nextCoordinate = direction + edge.To
                                from e in EdgesFrom(edge.To, edgeMap)
                                where e.To == nextCoordinate || e.From == nextCoordinate
                                select e;

                    var nextEdge = moves.First();
                    RemoveEdge(nextEdge, edges, edgeMap);
                    edge = nextEdge.To != edge.To ? nextEdge : nextEdge.Reversed();
                    currentCycle.Add(edge.To);
                }
                cycles.Add(currentCycle);
            }

            var scale = 32;
            return new PathGeometry(cycles.Select(x => new PathFigure(x.First().ToPoint(scale), x.Skip(1).Select(y => new LineSegment(y.ToPoint(scale), true)), true)));
        }

        private static bool IsEdgeLeftHand(bool[][] b, Edge edge)
        {
            var cell = GetCell(edge.From.Col, edge.From.Row, b);
            return (edge.From.Row < edge.To.Row && cell) || (!(edge.From.Col < edge.To.Col && cell));
        }

        static IEnumerable<Edge> EdgesFrom(Coordinate c, Dictionary<Coordinate, List<Edge>> edgeMap)
        {
            return edgeMap.ContainsKey(c) ? edgeMap[c] : Enumerable.Empty<Edge>();
        }

        static IEnumerable<Coordinate> Turns(Coordinate currentDirection)
        {
            int index = Array.IndexOf(directions, currentDirection);
            return directions.Skip(index + 1).Concat(directions.Take(index));
        }

        private static bool GetCell(int c, int r, bool[][] b)
        {
            if (r < 0 || r >= b.Length)
            {
                return false;
            }
            var row = b[r];
            if (c < 0 || c >= row.Length)
            {
                return false;
            }
            return row[c];
        }

        private static void RemoveEdge(Edge e, HashSet<Edge> edges, Dictionary<Coordinate, List<Edge>> edgeMap)
        {
            edges.Remove(e);
            edgeMap[e.From].Remove(e);
            edgeMap[e.To].Remove(e);
        }

        private static void AddEdge(Edge e, HashSet<Edge> edges, Dictionary<Coordinate, List<Edge>> edgeMap)
        {
            edges.Add(e);
            AddCoordinate(e.From, e, edgeMap);
            AddCoordinate(e.To, e, edgeMap);
        }

        private static void AddCoordinate(Coordinate c, Edge e, Dictionary<Coordinate, List<Edge>> edgeMap)
        {
            List<Edge> list;
            if (!edgeMap.TryGetValue(c, out list))
            {
                edgeMap[c] = list = new List<Edge>();
            }
            list.Add(e);
        }


        struct Coordinate
        {
            public readonly int Row, Col;

            public Coordinate(int col, int row)
            {
                Col = col;
                Row = row;
            }

            public bool Equals(Coordinate other)
            {
                return other.Row == Row && other.Col == Col;
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(null, obj)) return false;
                if (obj.GetType() != typeof(Coordinate)) return false;
                return Equals((Coordinate)obj);
            }

            public override int GetHashCode()
            {
                unchecked
                {
                    return (Row * 397) ^ Col;
                }
            }

            public override string ToString()
            {
                var s = "";
                if (this == North) s = " n";
                if (this == West) s = " w";
                if (this == South) s = " s";
                if (this == East) s = " e";
                return string.Format("({0}, {1}{2})", Col, Row, s);
            }

            public static bool operator ==(Coordinate left, Coordinate right)
            {
                return left.Equals(right);
            }

            public static bool operator !=(Coordinate left, Coordinate right)
            {
                return !left.Equals(right);
            }

            public static Coordinate operator +(Coordinate c1, Coordinate c2)
            {
                return new Coordinate(c1.Col + c2.Col, c1.Row + c2.Row);
            }

            public static Coordinate operator -(Coordinate c1, Coordinate c2)
            {
                return new Coordinate(c1.Col - c2.Col, c1.Row - c2.Row);
            }

            public Point ToPoint(double scale)
            {
                return new Point(Col * scale, Row * scale);
            }

            public static readonly Coordinate West = new Coordinate(-1, 0);
            public static readonly Coordinate South = new Coordinate(0, 1);
            public static readonly Coordinate East = new Coordinate(1, 0);
            public static readonly Coordinate North = new Coordinate(0, -1);
        }

        struct Edge
        {
            public readonly Coordinate From, To;

            public Edge(Coordinate from, Coordinate to)
            {
                From = from;
                To = to;
            }

            public Edge(int fromCol, int fromRow, int toCol, int toRow)
                : this(new Coordinate(fromCol, fromRow), new Coordinate(toCol, toRow))
            {

            }


            public bool Equals(Edge other)
            {
                return other.From.Equals(From) && other.To.Equals(To);
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(null, obj)) return false;
                if (obj.GetType() != typeof(Edge)) return false;
                return Equals((Edge)obj);
            }

            public override int GetHashCode()
            {
                unchecked
                {
                    return (From.GetHashCode() * 397) ^ To.GetHashCode();
                }
            }

            public override string ToString()
            {
                char angle = ' ';
                if (From.Col == To.Col)
                {
                    angle = '|';
                }
                if (From.Row == To.Row)
                {
                    angle = '-';
                }


                return string.Format("[{0} {2} {1}]", From, To, angle);
            }

            public static bool operator ==(Edge left, Edge right)
            {
                return left.Equals(right);
            }

            public static bool operator !=(Edge left, Edge right)
            {
                return !left.Equals(right);
            }

            public Edge Reversed()
            {
                return new Edge(To, From);
            }
        }
    }