using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Azimuth;
using Annulus;
using Annulus.CSG;
using Annulus.CSG.StraightSkeletonUtilities;

namespace Annulus.UnitTests.CSG
{
    public class StraightSkeletonBuilderTests : UnitTestSharp.TestFixture
    {
        public class FindEdgeEventTests : UnitTestSharp.TestFixture
        {
            public void Basic()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(5, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 5), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void MatchVelocity()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, -1),
                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                CheckFalse(hit);
                CheckNull(edgeEvent);
            }

            public void ImpossibleDirection()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, 1),
                    },
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(10, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 10), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void UnequalDirection()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -2),
                    },
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(4, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 4), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void ZeroEdgeVelocity()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, 0),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, 0),
                    },
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(10, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 10), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void NegativeTOI()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, -1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                CheckFalse(hit);
                CheckNull(edgeEvent);
            }

            public void NonZeroInitialTOIs_Vertex()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 2,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(6, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 4), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void NonZeroInitialTOIs_Edge()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                        TOI = 2,
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                        TOI = 2,
                    },

                    TOI = 2,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(6, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(0, 6), edgeEvent.HitPoint);
                    CheckEqual(0.5, edgeEvent.Fraction);
                }
            }

            public void TooFarLeft()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(-4, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                CheckFalse(hit);
                CheckNull(edgeEvent);
            }

            public void TooFarRight()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(0, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(4, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                CheckFalse(hit);
                CheckNull(edgeEvent);
            }

            public void SweepingMiss()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(-1, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(-1, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(0, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                CheckFalse(hit);
                CheckNull(edgeEvent);
            }

            public void SweepingHit()
            {
                var edge = new Edge
                {
                    vertex1 = new Vertex
                    {
                        Position = new Vector(-1, 10),
                        BisectorDirection = new Vector(-1, -1),
                    },

                    vertex2 = new Vertex
                    {
                        Position = new Vector(1, 10),
                        BisectorDirection = new Vector(1, -1),
                    },

                    TOI = 0,
                };

                var vertex = new Vertex
                {
                    Position = new Vector(4, 0),
                    BisectorDirection = new Vector(0, 1),

                    TOI = 0,
                };

                EdgeEvent edgeEvent = EdgeEvent.FindEdgeEvent(edge, vertex);
                bool hit = edgeEvent != null;

                Check(hit);
                CheckNotNull(edgeEvent);
                if (edgeEvent != null)
                {
                    CheckEqual(5, edgeEvent.TOI);
                    CheckEqual(edge, edgeEvent.Edge);
                    CheckEqual(vertex, edgeEvent.Vertex);
                    CheckEqual(new Vector(4, 5), edgeEvent.HitPoint);
                    CheckEqual(10.0/12.0, edgeEvent.Fraction);
                }
            }
        }

        //public class FindCollapseEventTests : UnitTestSharp.TestFixture
        //{
        //    public void BasicHit()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(-1, 0),
        //            BisectorDirection = new Vector(1, 1),
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(1, 0),
        //            BisectorDirection = new Vector(-1, 1),
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //        bool hit = collapseEvent != null;

        //        Check(hit);
        //        CheckNotNull(collapseEvent);
        //        if (collapseEvent != null)
        //        {
        //            CheckEqual(1, collapseEvent.TOI);
        //            CheckEqual(vertex1, collapseEvent.v1);
        //            CheckEqual(vertex2, collapseEvent.v2);
        //        }
        //    }

        //    public void BasicMiss()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(-1, 0),
        //            BisectorDirection = new Vector(-1, 1),
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(1, 0),
        //            BisectorDirection = new Vector(-1, 1),
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //        bool hit = collapseEvent != null;

        //        CheckFalse(hit);
        //        CheckNull(collapseEvent);
        //    }

        //    public void NonZeroTOI()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(-1, 0),
        //            BisectorDirection = new Vector(1, 1),
        //            TOI = 2,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(1, 0),
        //            BisectorDirection = new Vector(-1, 1),
        //            TOI = 2,
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //        bool hit = collapseEvent != null;

        //        Check(hit);
        //        CheckNotNull(collapseEvent);
        //        if (collapseEvent != null)
        //        {
        //            CheckEqual(3, collapseEvent.TOI);
        //            CheckEqual(vertex1, collapseEvent.v1);
        //            CheckEqual(vertex2, collapseEvent.v2);
        //        }
        //    }

        //    public void UnevenTOI_CollisionPast()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(-1, 0),
        //            BisectorDirection = new Vector(1, 1),
        //            TOI = 0,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(-1, 2),
        //            BisectorDirection = new Vector(-1, 1),
        //            TOI = 2,
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);

        //        CheckNull(collapseEvent);
        //    }

        //    public void UnevenTOI_CollisionFuture()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(-2, -1),
        //            BisectorDirection = new Vector(1, 1),
        //            TOI = 0,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(1, 0),
        //            BisectorDirection = new Vector(-1, 1),
        //            TOI = 1,
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //        bool hit = collapseEvent != null;

        //        Check(hit);
        //        CheckNotNull(collapseEvent);
        //        if (collapseEvent != null)
        //        {
        //            CheckEqual(2, collapseEvent.TOI);
        //            CheckEqual(vertex1, collapseEvent.v1);
        //            CheckEqual(vertex2, collapseEvent.v2);
        //        }
        //    }

        //    public void DegenerateEdge()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(0, 0),
        //            BisectorDirection = new Vector(0, 1),
        //            TOI = 0,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(0, 1),
        //            BisectorDirection = new Vector(1, 1),
        //            TOI = 1,
        //        };

        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //        bool hit = collapseEvent != null;

        //        Check(hit);
        //        CheckNotNull(collapseEvent);
        //        if (collapseEvent != null)
        //        {
        //            CheckEqual(1, collapseEvent.TOI);
        //            CheckEqual(vertex1, collapseEvent.v1);
        //            CheckEqual(vertex2, collapseEvent.v2);
        //        }
        //    }

        //    public void DegenerateEdge_DegenerateRay()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(0, 0),
        //            BisectorDirection = new Vector(0, 1),
        //            TOI = 0,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(0, 1),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 1,
        //        };

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //            bool hit = collapseEvent != null;

        //            Check(hit);
        //            CheckNotNull(collapseEvent);
        //            if (collapseEvent != null)
        //            {
        //                CheckEqual(1, collapseEvent.TOI);
        //                CheckEqual(vertex1, collapseEvent.v1);
        //                CheckEqual(vertex2, collapseEvent.v2);
        //            }
        //        }

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex2, vertex1);
        //            bool hit = collapseEvent != null;

        //            Check(hit);
        //            CheckNotNull(collapseEvent);
        //            if (collapseEvent != null)
        //            {
        //                CheckEqual(1, collapseEvent.TOI);
        //                CheckEqual(vertex2, collapseEvent.v1);
        //                CheckEqual(vertex1, collapseEvent.v2);
        //            }
        //        }
        //    }

        //    public void DegenerateEdge_DegenerateRay_InThePast()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(0, 2),
        //            BisectorDirection = new Vector(0, 1),
        //            TOI = 2,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(0, 1),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 1,
        //        };

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //            bool hit = collapseEvent != null;

        //            CheckFalse(hit);
        //            CheckNull(collapseEvent);
        //        }

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex2, vertex1);
        //            bool hit = collapseEvent != null;

        //            CheckFalse(hit);
        //            CheckNull(collapseEvent);
        //        }
        //    }

        //    public void DoubleDegenerate_Coincident()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(0, 2),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 2,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(0, 2),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 1,
        //        };

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //            bool hit = collapseEvent != null;

        //            Check(hit);
        //            CheckNotNull(collapseEvent);
        //            if (collapseEvent != null)
        //            {
        //                CheckEqual(2, collapseEvent.TOI);
        //                CheckEqual(vertex1, collapseEvent.v1);
        //                CheckEqual(vertex2, collapseEvent.v2);
        //            }
        //        }

        //        {
        //            CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex2, vertex1);
        //            bool hit = collapseEvent != null;

        //            Check(hit);
        //            CheckNotNull(collapseEvent);
        //            if (collapseEvent != null)
        //            {
        //                CheckEqual(2, collapseEvent.TOI);
        //                CheckEqual(vertex2, collapseEvent.v1);
        //                CheckEqual(vertex1, collapseEvent.v2);
        //            }
        //        }
        //    }

        //    public void DoubleDegenerate_Separate()
        //    {
        //        var vertex1 = new Vertex
        //        {
        //            Position = new Vector(0, 1),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 2,
        //        };

        //        var vertex2 = new Vertex
        //        {
        //            Position = new Vector(0, 2),
        //            BisectorDirection = new Vector(0, 0),
        //            TOI = 1,
        //        };

        //        CheckThrow(typeof(Exception));
        //        CollapseEvent collapseEvent = StraightSkeletonBuilder.FindCollapseEvent(vertex1, vertex2);
        //    }
        //}

        public class FindInitialVerticesAndEdgesTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckSimilarity(
                IEnumerable<Vector> expectedVertices,
                IEnumerable<Vector> expectedReflexVertices,
                IEnumerable<Polygon.Edge> expectedEdges,
                IEnumerable<Vertex> vertices,
                IEnumerable<Vertex> reflexVertices,
                IEnumerable<Edge> edges)
            {
                CheckEqualCommutative(expectedVertices, vertices.Select(x => x.Position));
                CheckEqualCommutative(expectedReflexVertices, reflexVertices.Select(x => x.Position));
                CheckEqual(expectedEdges.Count(), edges.Count());
            }

            public void Triangle()
            {
                var poly = new PerforatedPolygon(new SimplePolygon(new Vector[]
                {
                    new Vector(0, 0),
                    new Vector(1, 0),
                    new Vector(0.5, Math.Sqrt(3)/2),
                }));

                List<Vertex> vertices, reflexVertices;
                List<Edge> edges;
                StraightSkeletonBuilder.FindInitalVerticesAndEdges(poly, out vertices, out reflexVertices, out edges);

                var expectedVertices = poly.Silhouette.VertexList;
                var expectedReflexVertices = new Vector[] { };
                var expectedEdges = poly.Edges.ToList();

                CheckSimilarity(expectedVertices, expectedReflexVertices, expectedEdges, vertices, reflexVertices, edges);
            }
        }

        public class FindBisector : UnitTestSharp.TestFixture
        {
            public class VectorDirectionTests : UnitTestSharp.TestFixture
            {
                public void PositiveWinding()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(1, 0),
                        new Vector(0, 1),
                        1);

                    CheckEqual(new Vector(1, 1), bisector);
                }

                public void NegativeWinding()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(1, 0),
                        new Vector(0, 1),
                        -1);

                    CheckEqual(new Vector(-1, -1), bisector);
                }

                public void Parallel()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(1, 0),
                        new Vector(1, 0),
                        1);

                    CheckEqual(new Vector(0, 0), bisector);
                }

                public void AntiParallel()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(1, 0),
                        new Vector(-1, 0),
                        1);

                    CheckEqual(new Vector(0, 0), bisector);
                }

                public void Quadrant2_Positive()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(0, 1),
                        new Vector(-1, 0),
                        -10);

                    CheckEqual(new Vector(1, -1), bisector);
                }

                public void Quadrant2_Negative()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(0, 1),
                        new Vector(-1, 0),
                        10);

                    CheckEqual(new Vector(-1, 1), bisector);
                }

                public void Quadrant3_Positive()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(-10, 0),
                        new Vector( 0,-10),
                        -10);

                    CheckEqual(new Vector(1, 1), bisector);
                }

                public void Quadrant3_Negative()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(-11, 0),
                        new Vector(0, -2),
                        10);

                    CheckEqual(new Vector(-1, -1), bisector);
                }

                public void Quadrant4_Positive()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(10, 0),
                        new Vector(0, -10),
                        -10);

                    CheckEqual(new Vector(1, -1), bisector);
                }

                public void Quadrant4_Negative()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(11, 0),
                        new Vector(0, -2),
                        10);

                    CheckEqual(new Vector(-1, 1), bisector);
                }

                public void OneZero()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(0, 0),
                        new Vector(0, -2),
                        10);

                    CheckEqual(new Vector(0, 0), bisector);
                }

                public void OtherZero()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(0, -2),
                        new Vector(0, 0),
                        10);

                    CheckEqual(new Vector(0, 0), bisector);
                }

                public void BothZero()
                {
                    var bisector = Vertex.FindBisector(
                        new Vector(0, 0),
                        new Vector(0, 0),
                        10);

                    CheckEqual(new Vector(0, 0), bisector);
                }
            }

            public class VertexTests : UnitTestSharp.TestFixture
            {
                public void Basic()
                {
                    var prevVertex = new Vertex
                    {
                        Position = new Vector(-1, 0),
                        TOI = 0,
                    };

                    var currVertex = new Vertex
                    {
                        Position = new Vector(0, 0),
                        TOI = 0,
                    };

                    var nextVertex = new Vertex
                    {
                        Position = new Vector(0, 1),
                        TOI = 0,
                    };

                    var bisector = Vertex.FindBisector(currVertex, prevVertex, nextVertex, 1);

                    CheckEqual(new Vector(-1, 1), bisector);
                }

                public void ReverseWinding()
                {
                    var prevVertex = new Vertex
                    {
                        Position = new Vector(-1, 0),
                        TOI = 0,
                    };

                    var currVertex = new Vertex
                    {
                        Position = new Vector(0, 0),
                        TOI = 0,
                    };

                    var nextVertex = new Vertex
                    {
                        Position = new Vector(0, 1),
                        TOI = 0,
                    };

                    var bisector = Vertex.FindBisector(currVertex, prevVertex, nextVertex, -1);

                    CheckEqual(new Vector(1, -1), bisector);
                }

                public void DifferentTOI_LeftRightTheSame()
                {
                    var prevVertex = new Vertex
                    {
                        Position = new Vector(-1, 1),
                        BisectorDirection = new Vector(0, -1),
                        TOI = 0,
                    };

                    var currVertex = new Vertex
                    {
                        Position = new Vector(0, 0),
                        TOI = 1,
                    };

                    var nextVertex = new Vertex
                    {
                        Position = new Vector(-1, 1),
                        BisectorDirection = new Vector(1, 0),
                        TOI = 0,
                    };

                    var bisector = Vertex.FindBisector(currVertex, prevVertex, nextVertex, -1);

                    CheckEqual(new Vector(1, -1), bisector);
                }

                public void DifferentTOI_LeftRightDifferent()
                {
                    var prevVertex = new Vertex
                    {
                        Position = new Vector(-1, 1),
                        BisectorDirection = new Vector(0, -1),
                        TOI = 2,
                    };

                    var currVertex = new Vertex
                    {
                        Position = new Vector(0, 0),
                        TOI = 3,
                    };

                    var nextVertex = new Vertex
                    {
                        Position = new Vector(-3, 1),
                        BisectorDirection = new Vector(1, 0),
                        TOI = 0,
                    };

                    var bisector = Vertex.FindBisector(currVertex, prevVertex, nextVertex, -1);

                    CheckEqual(new Vector(1, -1), bisector);
                }
            }
        }

        [UnitTestSharp.IgnoreTest]
        public void CheckSimilarity(StraightSkeleton actual,
            PerforatedPolygon poly,
            IList<Vector> additionalVerts,
            IList<int> additionalEdges)
        {
            StraightSkeleton expectedStraightSkeleton;
            var expectedEdges = new List<StraightSkeleton.ExportEdge>();
            {
                var vertexList = poly.Silhouette.VertexList
                    .Concat(poly.Holes.SelectMany(x => x.VertexList))
                    .Concat(additionalVerts);

                var expectedVertices = vertexList
                    .Select(x => new StraightSkeleton.ExportVertex 
                    {
                        Position = x,
                        Edges = new List<StraightSkeleton.ExportEdge>(),
                    })
                    .ToList();

                for(int i = 0; i < poly.Silhouette.VertexList.Count; ++i)
                {
                    expectedEdges.Add(new StraightSkeleton.ExportEdge
                    {
                        vertex1 = expectedVertices[i],
                        vertex2 = expectedVertices[Polygon.Utilities.CyclicIncrement(i, poly.Silhouette.VertexList.Count)],
                    });
                }

                int runningTotal = poly.Silhouette.Count;
                for (int i = 0; i < poly.Holes.Count; ++i)
                {
                    for (int j = 0; j < poly.Holes[i].Count; ++j)
                    {
                        expectedEdges.Add(new StraightSkeleton.ExportEdge
                        {
                            vertex1 = expectedVertices[runningTotal + j],
                            vertex2 = expectedVertices[runningTotal + Polygon.Utilities.CyclicIncrement(j, poly.Holes[i].Count)],
                        });
                    }

                    runningTotal += poly.Holes[i].Count;
                }

                for(int i = 0; i < additionalEdges.Count; i += 2)
                {
                    expectedEdges.Add(new StraightSkeleton.ExportEdge
                    {
                        vertex1 = expectedVertices[additionalEdges[i]],
                        vertex2 = expectedVertices[additionalEdges[i+1]],
                    });
                }

                expectedEdges.ForEach(edge =>
                {
                    edge.vertex1.Edges.Add(edge);
                    edge.vertex2.Edges.Add(edge);
                });

                // Need to glom together vertices that have the same position
                expectedVertices = expectedVertices.GroupBy(x => x.Position).Select(x => new StraightSkeleton.ExportVertex
                {
                    Position = x.First().Position,
                    Edges = x.Aggregate(new List<StraightSkeleton.ExportEdge>(),
                        (accum, next) => accum.Concat(next.Edges).ToList()),
                }).ToList();

                expectedVertices.ForEach(vert =>
                {
                    var repEdge1 = vert.Edges
                        .Where(edge => edge.vertex1.Equals(vert))
                        .Select(edge => new StraightSkeleton.ExportEdge
                        {
                            vertex1 = vert,
                            vertex2 = edge.vertex2,
                        });

                    var repEdge2 = vert.Edges
                        .Where(edge => edge.vertex2.Equals(vert))
                        .Select(edge => new StraightSkeleton.ExportEdge
                        {
                            vertex1 = edge.vertex1,
                            vertex2 = vert,
                        });

                    vert.Edges = repEdge1.Concat(repEdge2).ToList();
                });

                expectedStraightSkeleton = new StraightSkeleton
                {
                    Vertices = expectedVertices,
                    Edges = expectedEdges,
                };
            }

            var st = new System.Diagnostics.StackTrace();
            var pedigree = UnitTestSharp.Extensions.MethodBaseExtensions.ExtractPedigree(st.GetFrame(1).GetMethod());

            int oldFailedChecks = this.internals.FailedChecks;
            
            CheckEqualCommutative(expectedEdges, actual.Edges);
            CheckEqualCommutative(expectedStraightSkeleton.Vertices, actual.Vertices);

            if (oldFailedChecks != this.internals.FailedChecks) // Writing these svg files to disk takes FOR EVER, so don't do it if we don't need to
            {
                // Write out SVG of failed test

                string wrapper =
                    @"<?xml version=""1.0"" encoding=""utf-8""?>
                    <!DOCTYPE svg PUBLIC ""-//W3C//DTD SVG 1.1//EN"" ""http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"">
                    <svg xmlns=""http://www.w3.org/2000/svg"" xmlns:xlink=""http://www.w3.org/1999/xlink"" version=""1.2"" baseProfile = ""tiny"">
                    <g id=""viewport"" transform=""scale(150),translate(-.25,-0.5)"">
                        <g id=""toplabel"" transform=""translate(0.5,1)"">
                            <text font-size="".5"">Expected</text>
                            <text transform=""translate(0,3)"" font-size="".5"">Actual</text>
                        </g>
                        <g id=""expected"" transform=""translate(1.5,1.5)"">
                            <g transform=""{2}"">{0}</g>
                        </g>

                        <g id=""actual"" transform=""translate(1.5,4.5)"">
                            <g transform=""{3}"">{1}</g>
                        </g>
                    </g>
                    <script xlink:href=""SVGPan.js""></script>
                    <script xlink:href=""SVGPanUnscale.js""></script>
                    <script>
                        unscaleEach(""g.non-scaling > *"");
                    </script>
                    </svg>";

                string lineStyle = @"vector-effect=""non-scaling-stroke"" fill=""transparent"" stroke=""blue"" stroke-width=""1""";
                string vertexStyle = @"fill=""transparent"" stroke=""red"" stroke-width=""3""";
                string lineLabelStyle = @"fill=""blue""";
                string vertexLabelStyle = @"fill=""darkred""";
                string polygonLines = poly.BuildSVGShape(lineStyle);
                string actualStraightSkeletonLines = actual.BuildSVG(vertexStyle, lineStyle, vertexLabelStyle, lineLabelStyle);
                string expectedStraightSkeletonLines = expectedStraightSkeleton.BuildSVG(vertexStyle, lineStyle, vertexLabelStyle, lineLabelStyle);

                var expectedAABB = expectedStraightSkeleton.CalculateAABB();
                var actualAABB = actual.CalculateAABB();

                var expectedSpan = expectedAABB.Max - expectedAABB.Min;
                var actualSpan = actualAABB.Max - actualAABB.Min;

                // Find scales such that expected and actual are 2 units high
                var expectedScale = 2 / expectedSpan.Y;
                var actualScale = 2 / actualSpan.Y;

                var expectedTransform = String.Format("scale({2}), translate({0},{1}), scale(-1,1)", -expectedAABB.Max.X, -expectedAABB.Max.Y, -expectedScale);
                var actualTransform = String.Format("scale({2}), translate({0},{1}), scale(-1,1)", -actualAABB.Max.X, -actualAABB.Max.Y, -actualScale);

                string fullText = String.Format(wrapper,
                    expectedStraightSkeletonLines, actualStraightSkeletonLines, expectedTransform, actualTransform);

                pedigree = pedigree.Replace("::", ".");
                pedigree += ".svg";
                pedigree = System.IO.Directory.GetCurrentDirectory() + "\\" + pedigree;
                System.IO.File.WriteAllText(pedigree, fullText);

                if (oldFailedChecks != this.internals.FailedChecks)
                {
                    TODO("Failed skeleton saved as " + pedigree);
                }
            }
        }

        public void Triangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 0),
                new Vector(0.5, Math.Sqrt(3)/2),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.5, Math.Sqrt(3)/6),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 3,
                3, 1,                
                3, 2,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void ReverseTriangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(0.5, Math.Sqrt(3)/2),
                new Vector(1, 0),                
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.5, Math.Sqrt(3)/6),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 3,
                3, 1,
                3, 2,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Rectangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 2,  1),
                new Vector( 2, -1),
                new Vector(-2, -1),
                new Vector(-2,  1),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( 1, 0),
                new Vector(-1, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 4,
                1, 4,
                2, 5,
                3, 5,
                4, 5,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void ReverseRectangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 2, -1),
                new Vector( 2,  1),
                new Vector(-2,  1),
                new Vector(-2, -1),                
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( 1, 0),
                new Vector(-1, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 4,
                1, 4,
                2, 5,
                3, 5,
                4, 5,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Prism()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 3,  0), //0
                new Vector( 2,  1), //1
                new Vector(-2,  1), //2
                new Vector(-3,  0), //3
                new Vector(-2, -1), //4
                new Vector( 2, -1), //5
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( 3 - Math.Sqrt(2), 0), //6
                new Vector(-3 + Math.Sqrt(2), 0), //7
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 6,
                1, 6,
                5, 6,
                2, 7,
                3, 7,
                4, 7,
                6, 7,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Prism_Reverse()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 2, -1), //5
                new Vector(-2, -1), //4
                new Vector(-3,  0), //3
                new Vector(-2,  1), //2
                new Vector( 2,  1), //1
                new Vector( 3,  0), //0
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( 3 - Math.Sqrt(2), 0), //6
                new Vector(-3 + Math.Sqrt(2), 0), //7
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                5, 6,
                4, 6,
                0, 6,
                3, 7,
                2, 7,
                1, 7,
                6, 7,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void InvertedPrism_Tall()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 2,  0),
                new Vector( 3,  1),
                new Vector(-3,  1),
                new Vector(-2,  0),
                new Vector(-3, -1),
                new Vector( 3, -1),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( 2 - Math.Sqrt(2), 0),
                new Vector(-2 + Math.Sqrt(2), 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 6,
                1, 6,
                2, 7,
                3, 7,
                4, 7,
                5, 6,
                6, 7,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void ConjoinedTriangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-0.5, Math.Sqrt(3)/2),
                new Vector(-1, 0),
                new Vector(1, 0),
                new Vector(0.5, Math.Sqrt(3)/2),
                new Vector(0, 0),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.5, Math.Sqrt(3)/6),
                new Vector(-0.5, Math.Sqrt(3)/6),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 6,
                4, 6,
                1, 6,
                4, 5,
                2, 5,
                3, 5,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void InvertedPrism_Short_Half()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 1,  0), //0
                new Vector( 2,  1), //1
                new Vector(-2,  1), //2
                new Vector(-2, -1), //4
                new Vector( 2, -1), //5
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(1 - Math.Sqrt(2.0), 0),
                new Vector(-1, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                1, 5,
                4, 5,
                0, 5,
                2, 6,
                3, 6,
                5, 6,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void InvertedPrism_Short()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector( 1,  0), //0
                new Vector( 2,  1), //1
                new Vector(-2,  1), //2
                new Vector(-1,  0), //3
                new Vector(-2, -1), //4
                new Vector( 2, -1), //5
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0,  3 - 2 * Math.Sqrt(2)),
                new Vector(0, -3 + 2 * Math.Sqrt(2)),
                new Vector(0, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                1, 6,
                2, 6,
                4, 7,
                5, 7,
                6, 8,
                7, 8,
                0, 8,
                3, 8,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void HollowSquare()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-10, 10), //0
                new Vector( 10, 10),
                new Vector( 10,-10),
                new Vector(-10,-10),
            }), new SimplePolygon[] { new SimplePolygon(new Vector[]
            {
                new Vector(-8,-8), // 4
                new Vector( 8,-8),
                new Vector( 8, 8),
                new Vector(-8, 8),
            })});

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-9, 9), //8
                new Vector( 9, 9),
                new Vector( 9,-9),
                new Vector(-9,-9),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 8,
                7, 8,

                1, 9,
                6, 9,

                2, 10,
                5, 10,

                3, 11,
                4, 11,

                08, 11,
                08, 09,
                09, 10,
                10, 11,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void HollowTriangle()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 6.0/4.0*Math.Sqrt(3)),
                new Vector(-1.5, 0),
                new Vector( 1.5, 0),
            }), new SimplePolygon[] { new SimplePolygon(new Vector[]
            {
                new Vector(0, Math.Sqrt(3)),
                new Vector(-.75, Math.Sqrt(3)/4),
                new Vector( .75, Math.Sqrt(3)/4),
            })});

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0,  5 * Math.Sqrt(3) / 4),
                new Vector(-9.0/8, 1 * Math.Sqrt(3) / 8),
                new Vector( 9.0/8, 1 * Math.Sqrt(3) / 8),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 6,
                1, 7,
                2, 8,
                
                3, 8,
                4, 7,
                5, 6,

                6, 8,
                6, 7,

                7, 8,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }        

        public void Clover()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 2),
                new Vector(2, 1),
                new Vector(0, 0),
                new Vector(2, -1),
                new Vector(1, -2),
                new Vector(0, 0),
                new Vector(-1, -2),
                new Vector(-2, -1),
                new Vector(0, 0),
                new Vector(-2, 1),
                new Vector(-1, 2),
            }));

            var sq5 = Math.Sqrt(5);
            var sq2 = Math.Sqrt(2);
            var pos = 1 + (sq5 - sq2) / (2 * sq5 + sq2);

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( pos,  pos),
                new Vector( pos, -pos),
                new Vector(-pos, -pos),
                new Vector(-pos,  pos),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 12,
                1, 12,
                2, 12,

                3, 13,
                4, 13,
                5, 13,

                6, 14,
                7, 14,
                8, 14,

                09, 15,
                10, 15,
                11, 15,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void CloverReverse()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(-1, 2),
                new Vector(-2, 1),
                new Vector(0, 0),
                new Vector(-2, -1),
                new Vector(-1, -2),
                new Vector(0, 0),
                new Vector(1, -2),
                new Vector(2, -1),
                new Vector(0, 0),
                new Vector(2, 1),
                new Vector(1, 2),
            }));

            var sq5 = Math.Sqrt(5);
            var sq2 = Math.Sqrt(2);
            var pos = 1 + (sq5 - sq2) / (2 * sq5 + sq2);

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector( pos,  pos),
                new Vector(-pos,  pos),
                new Vector(-pos, -pos),
                new Vector( pos, -pos),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 13,
                1, 13,
                2, 13,

                3, 14,
                4, 14,
                5, 14,

                6, 15,
                7, 15,
                8, 15,

                09, 12,
                10, 12,
                11, 12,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Cave()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-2, 2),
                new Vector(2, 2),
                new Vector(2, 1),
                new Vector(1.5, 0),
                new Vector(1, 1),
                new Vector(-1, 1),
                new Vector(-1, -1),
                new Vector(1, -1),
                new Vector(1.5, 0),
                new Vector(2, -1),
                new Vector(2, -2),
                new Vector(-2, -2),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-1.5,  1.5),
                new Vector(-1.5, -1.5),
                new Vector((Math.Sqrt(5) + 3) / 4.0, 1.5),
                new Vector((Math.Sqrt(5) + 3) / 4.0, -1.5),
                new Vector(1.5,  Math.Sqrt(5) / 2.0),
                new Vector(1.5, -Math.Sqrt(5) / 2.0),
                new Vector(1.4270509831, 1.4270509831),
                new Vector(1.4270509831, -1.4270509831),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 12,
                5, 12,
                11, 13,
                6, 13,
                12,13,

                12, 14,
                4, 14,

                13, 15,
                7, 15,

                2, 16,
                3, 16,

                8, 17,
                9, 17,

                14, 18,
                1, 18,
                16, 18,

                17, 19,
                15, 19,
                10, 19,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void DoubleDonut()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-2, 3),
                new Vector(2, 3),
                new Vector(2, -3),
                new Vector(-2, -3),
            }), new SimplePolygon[] { new SimplePolygon(new Vector[]
            {
                new Vector(1, 1),                    
                new Vector(1, 2),
                new Vector(-1, 2),
                new Vector(-1, 1),
            }), new SimplePolygon(new Vector[]
            {
                new Vector(1, -2),
                new Vector(1, -1),
                new Vector(-1, -1),
                new Vector(-1, -2),
            })});

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(1.5, 2.5),
                new Vector(-1.5, 2.5),
                new Vector(1.5, -2.5),
                new Vector(-1.5, -2.5),

                new Vector(1.5, 0.5),
                new Vector(1.5, -0.5),

                new Vector(-1.5, 0.5),
                new Vector(-1.5, -0.5),

                new Vector(-1, 0),
                new Vector(1, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 13,
                6, 13,
                12, 13,
                1, 12,
                5, 12,

                3, 15,
                11, 15,
                14, 15,
                8, 14,
                2, 14,

                4, 16,
                7, 18,
                10, 19,
                9, 17,
                
                18, 20,
                19, 20,
                16, 21,
                17, 21,
                20, 21,

                19, 15,
                13, 18,
                12, 16,
                14, 17,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void DoublePeakMountain()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 2),
                new Vector(1, -1),
                new Vector(-1, -1),
                new Vector(-1, 2),
            }));

            var sq5 = Math.Sqrt(5);
            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-(5 + 3 * sq5) / (14 + 6 * sq5), -(5 + 3 * sq5) / (14 + 6 * sq5)),
                new Vector( (5 + 3 * sq5) / (14 + 6 * sq5), -(5 + 3 * sq5) / (14 + 6 * sq5)),
                new Vector(0, -sq5 / (1 + sq5)),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                3, 5,
                4, 5,
                5, 7,

                1, 6,
                2, 6,
                6, 7,

                7, 0,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Crown()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-2, 2),
                new Vector(-1, 0),
                new Vector(0, 2),
                new Vector(1, 0),
                new Vector(2, 2),
                new Vector(2, -1),
                new Vector(-2, -1),
            }));

            var sq5 = Math.Sqrt(5);
            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-(3 + 2 * sq5) / (3 + sq5), -(5 + 3 * sq5) / (14 + 6 * sq5)),
                new Vector((3 + 2 * sq5) / (3 + sq5), -(5 + 3 * sq5) / (14 + 6 * sq5)),
                new Vector(-1, -sq5 / (1 + sq5)),
                new Vector(1, -sq5 / (1 + sq5)),
                new Vector(0, (2 - sq5) / (1 + sq5)),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 7,
                6, 7,

                4, 8,
                5, 8,

                1, 9,
                3, 10,

                7, 9,
                8, 10,

                2, 11,
                9, 11,
                10, 11,

            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void FatTriforce()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, -Math.Sqrt(3)) * 2,
                new Vector(-1.5, Math.Sqrt(3)/2) * 2,
                new Vector( 1.5, Math.Sqrt(3)/2) * 2,
            }), new SimplePolygon[] { new SimplePolygon(new Vector[]
            {
                new Vector(0, Math.Sqrt(3)/2),
                new Vector(-.75, -Math.Sqrt(3)/4),
                new Vector( .75, -Math.Sqrt(3)/4),
            })});

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, Math.Sqrt(25.0/12.0)),
                new Vector(-1.25, Math.Sqrt(25.0/48.0)),
                new Vector(-1.25, -Math.Sqrt(25.0/48.0)),
                new Vector(0, -Math.Sqrt(25.0/12.0)),
                new Vector(1.25, -Math.Sqrt(25.0/48.0)),
                new Vector(1.25, Math.Sqrt(25.0/48.0)),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                6, 7,
                7, 8,
                8, 9,
                9, 10,
                10, 11,
                11, 6,

                0, 9,
                1, 7,
                2, 11,

                3, 6,
                4, 8,
                5, 10,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void HalfCross()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-1, 3),
                new Vector(1, 3),
                new Vector(1, 1),
                new Vector(3, 1),
                new Vector(3, -1),
                new Vector(-3, -1),
                new Vector(-3, 1),
                new Vector(-1,1),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, 2),
                new Vector(0, 0),
                new Vector(-2, 0),
                new Vector(2, 0),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 8,
                1, 8,
                7, 9,
                2, 9,
                5, 10,
                3, 11,
                4, 11,
                10, 9,
                11, 9,
                8, 9,
                6, 10,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void HalfCross_Reverse()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(1, 3),
                new Vector(1, 1),
                new Vector(3, 1),
                new Vector(3, -1),
                new Vector(-3, -1),
                new Vector(-3, 1),
                new Vector(-1,1),
                new Vector(-1, 3),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, 0),
                new Vector(-2, 0),
                new Vector(2, 0),
                new Vector(0, 2),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                7, 11,
                0, 11,
                4, 9,
                5, 9,
                2, 10,
                3, 10,
                8, 10,
                9, 8,
                11, 8,
                6, 8,
                1, 8,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Cross()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-1, 3),
                new Vector(1, 3),
                new Vector(1, 1),
                new Vector(3, 1),
                new Vector(3, -1),
                new Vector(1, -1),
                new Vector(1, -3),
                new Vector(-1, -3),
                new Vector(-1, -1),
                new Vector(-3, -1),
                new Vector(-3, 1),
                new Vector(-1,1),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, 2),
                new Vector(0, 0),
                new Vector(-2, 0),
                new Vector(2, 0),
                new Vector(0, -2),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 12,
                1, 12,

                9, 14, 
                10, 14,

                3, 15,
                4, 15,
                6, 16,
                7, 16,
                
                12, 13,
                14, 13,
                15, 13,
                16, 13,
                11, 13,
                8, 13,
                5, 13,
                2, 13,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void HammerAndAnvil()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 0),
                new Vector(1, 2),
                new Vector(-2, 2),
                new Vector(-2, -2),
                new Vector(1, -2),
                new Vector(1, 0),
                new Vector(0, 0),
                new Vector(0, -1),
                new Vector(-1, -1),
                new Vector(-1, 1),
                new Vector(0, 1),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-1.5, -1.5), //12
                new Vector(-1.5, 1.5), //13
                new Vector(0.5, -1.5), //14
                new Vector(0.5, 1.5), //15
                new Vector(0.5, -0.5), //16,
                new Vector(0.5, 0.5), //17
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                9, 12,
                4, 12,
                3, 13,
                10, 13,
                12, 13,
                8, 14,
                5, 14,
                12, 14,
                2, 15,
                11, 15,
                13, 15,
                1, 16,
                0, 16,
                14, 16,
                0, 17,
                1, 17,
                15, 17,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void ReverseHammerAndAnvil()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(0, 1),
                new Vector(-1, 1),
                new Vector(-1, -1),
                new Vector(0, -1),
                new Vector(0, 0),
                new Vector(1, 0),
                new Vector(1, -2),
                new Vector(-2, -2),
                new Vector(-2, 2),
                new Vector(1, 2),
                new Vector(1, 0),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-1.5, -1.5), //12
                new Vector(-1.5, 1.5), //13
                new Vector(0.5, -1.5), //14
                new Vector(0.5, 1.5), //15
                new Vector(0.5, -0.5), //16,
                new Vector(0.5, 0.5), //17
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                0, 17,
                11, 17,
                10, 15,
                1, 15,
                15, 17,
                13, 15,
                2, 13,
                3, 12,
                8, 12,
                12, 13,
                12, 14,
                14, 7,
                14, 16,
                6, 16,
                4, 14,
                5, 16,
                9, 13,

            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }
    }
}