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
    {
        [UnitTestSharp.IgnoreTest]
        public void CheckSimilarity(StraightSkeleton actual,
            PerforatedPolygon poly,
            IList<Vector> additionalVerts,
            IList<int> additionalEdges)
        {
            var vertexCycles = Enumerable.Concat<IList<Vector>>(new[] { poly.Silhouette.VertexList },
                poly.Holes.Select(hole => hole.VertexList));
            var st = new System.Diagnostics.StackTrace();
            CheckSimilarity(actual, vertexCycles, additionalVerts, additionalEdges,
                UnitTestSharp.Extensions.MethodBaseExtensions.ExtractPedigree(st.GetFrame(1).GetMethod()));
        }
        
        [UnitTestSharp.IgnoreTest]
        public void CheckSimilarity(StraightSkeleton actual,
            IEnumerable<IList<Vector>> vertexCycles,
            IList<Vector> additionalVerts,
            IList<int> additionalEdges,
            string pedigree = null)
        {
            var vertexList = vertexCycles.SelectMany(cycle => cycle).Concat(additionalVerts);
            
            StraightSkeleton expectedStraightSkeleton;
            var expectedEdges = new List<StraightSkeleton.ExportEdge>();
            {
                var expectedVertices = vertexList
                    .Select(x => new StraightSkeleton.ExportVertex 
                    {
                        Position = x,
                        Edges = new List<StraightSkeleton.ExportEdge>(),
                    })
                    .ToList();

                int runningTotal = 0;

                foreach(var cycle in vertexCycles)
                {
                    for (int i = 0; i < cycle.Count; ++i)
                    {
                        expectedEdges.Add(new StraightSkeleton.ExportEdge
                        {
                            Vertices = expectedVertices,
                            Vertex1Index = runningTotal + i,
                            Vertex2Index = runningTotal + Polygon.Utilities.CyclicIncrement(i, cycle.Count),
                        });
                    }
                    runningTotal += cycle.Count;
                }

                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())
                        .GroupBy(y => new { y.Vertex1, y.Vertex2 }).Select(y => y.First())
                        .ToList(),
                }).ToList();

                for (int i = 0; i < additionalEdges.Count; i += 2)
                {
                    var expectedEdge = new StraightSkeleton.ExportEdge
                    {
                        Vertices = expectedVertices,
                        Vertex1Index = additionalEdges[i],
                        Vertex2Index = additionalEdges[i + 1],
                    };
                    
                    expectedEdges.Add(expectedEdge);
                    expectedEdge.Vertex1.Edges.Add(expectedEdge);
                    expectedEdge.Vertex2.Edges.Add(expectedEdge);                    
                }

                for (int i = 0; i < expectedVertices.Count; ++i)
                {
                    var vert = expectedVertices[i];
                    var repEdge1 = vert.Edges
                        .Where(edge => edge.Vertex1.Equals(vert))
                        .Select(edge => new StraightSkeleton.ExportEdge
                        {
                            Vertices = expectedVertices,
                            Vertex1Index = i,
                            Vertex2Index = edge.Vertex2Index,
                        });

                    var repEdge2 = vert.Edges
                        .Where(edge => edge.Vertex2.Equals(vert))
                        .Select(edge => new StraightSkeleton.ExportEdge
                        {
                            Vertices = expectedVertices,
                            Vertex1Index = edge.Vertex1Index,
                            Vertex2Index = i,
                        });

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

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

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

            int oldFailedChecks = this.internals.FailedChecks;

            if (actual != null)
            {
                CheckEqualCommutative(expectedStraightSkeleton.Vertices, actual.Vertices);
                CheckEqualCommutative(expectedEdges, actual.Edges);                
            }
            else
            {
                actual = new StraightSkeleton();
            }

            //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 actualStraightSkeletonLines = actual.BuildSVG();
                string expectedStraightSkeletonLines = expectedStraightSkeleton.BuildSVG();

                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.Min.X, -expectedAABB.Max.Y, -expectedScale);
                var actualTransform = String.Format("scale({2}), translate({0},{1}), scale(-1,1)", actualAABB.Min.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 TriangleWithCenteredSplitEdge()
        {
            var vertices = new Vector[]
            {
                new Vector(0, 0),
                new Vector(0.5, 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, 4,
                4, 1,
                4, 2,
                3, 4,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                new[] { vertices },
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

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

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                new[] { vertices },
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

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

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                new[] { vertices },
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

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

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

            CheckSimilarity(straightSkeleton,
                new[] { vertices },
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void ShortArrow()
        {
            // Long shaft and an equilateral triangle head.
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 1),
                new Vector(0, -1),
                new Vector(5, -1),
                new Vector(5, -2),
                new Vector(5 + Math.Sqrt(3)/2 * 4, 0),
                new Vector(5, 2),
                new Vector(5, 1),
            }));

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void ShortArrowPerturbed()
        {
            // Long shaft and an equilateral triangle head.
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 1),
                new Vector(0, -1),
                new Vector(5, -1),
                new Vector(5.001, -2),
                new Vector(5.001 + Math.Sqrt(3)/2 * 4, 0),
                new Vector(5.001, 2),
                new Vector(5, 1),
            }));

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void Arrow()
        {
            // Long shaft and an equilateral triangle head.
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 1),
                new Vector(0, -1),
                new Vector(10, -1),
                new Vector(10, -2),
                new Vector(10 + Math.Sqrt(3)/2 * 4, 0),
                new Vector(10, 2),
                new Vector(10, 1),
            }));

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

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

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void IrregularQuad()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(32.511, 0),
                new Vector(0, 32.5495),
                new Vector(-32.5, 0),
                new Vector(0, -32.522)
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0027519766250489, 0.0068680234756019),
                new Vector(0.0027531388072445, 0.0068691867392462),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                2, 4,
                3, 4,
                4, 5,
                0, 5,
                1, 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, 6,
                4, 8,
                5, 7,

                6, 8,
                6, 7,

                7, 8,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void Pacman()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0.7263546355, 0), 
                new Vector(3.5387162047, 3.5387162047), 
                new Vector(0, 5.00450045), 
                new Vector(-3.5387162047, 3.5387162047), 
                new Vector(-5.00450045, 0), 
                new Vector(-3.5387162047, -3.5387162047), 
                new Vector(0, -5.00450045), 
                new Vector(3.5387162047, -3.5387162047), 
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, 2.6227377902),
                new Vector(0, -2.6227377902),
                new Vector(-2.3758050411, 0),
                new Vector(-1.4953849533, 1.4953849533),
                new Vector(-1.4953849533, -1.4953849533),
            };

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

            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, 9,
                0, 10,
                0, 11,
                0, 12,

                1, 9,
                2, 9,

                3, 10,
                4, 10,
                
                5, 11,
                6, 11,

                7, 12,
                8, 12,
            };

            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, 10,
                1, 10,
                2, 10,

                0, 11,
                3, 11,
                4, 11,

                0, 12,
                5, 12,
                6, 12,

                0, 9,
                7, 9,
                8, 9,
            };

            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, 11,
                5, 11,
                11, 12,
                6, 12,
                10, 12,
                12, 14,
                7, 14,
                14, 18,
                18, 16,
                18, 9,
                16, 8,
                16, 3,
                3, 15,
                2, 15,
                15, 17,
                17, 1,
                17, 13,
                13, 4,
                13, 11,
            };

            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[]
            {
                0, 15,
                1, 15,
                15, 13,
                2, 13,
                9, 13,
                13, 11,
                11, 3,
                11, 8,
                11, 10,
                4, 10,
                10, 7,
                10, 12,
                6, 12,
                5, 12,
                12, 14,
                14, 0,
                14, 1,
            };

            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[]
            {
                15, 0,
                15, 5,
                15, 13,
                13, 1,
                13, 9,
                13, 11,
                11, 8,
                11, 2,
                11, 10,
                10, 7,
                10, 3,
                10, 12,
                12, 4,
                12, 6,
                12, 14,
                14, 0,
                14, 5,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void HammerAndAnvilAndIntrudingVertex()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 0),
                new Vector(1, 2),
                new Vector(0.5, 0),
                new Vector(0, 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(0.1096117968, 1.1096117968), //12
                new Vector(0.7807764064, 0.2192235936), //13
                new Vector(0.2192235936, 0.2192235936), //14
                new Vector(-0.3903882032, 1.5), //15
                new Vector(-1.5, 1.5), //16
                new Vector(-1.5, -1.5), //17
                new Vector(0.5, -1.5), //18
                new Vector(0.5, -0.5), //19           
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void HammerAndAnvilAndTwoIntrudingVertices()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0, 0),
                new Vector(1, 0),
                new Vector(1, 2),
                new Vector(0.5, 0),
                new Vector(0, 2),
                new Vector(-2, 2),
                new Vector(-2, -2),
                new Vector(0, -2),
                new Vector(0.5, 0),
                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(0.1096117968, 1.1096117968),
                new Vector(0.7807764064, 0.2192235936),
                new Vector(0.2192235936, 0.2192235936),
                new Vector(-0.3903882032, 1.5),
                new Vector(-1.5, 1.5),
                new Vector(-1.5, -1.5),
                new Vector(0.1096117968, -1.1096117968),
                new Vector(0.7807764064, -0.2192235936),
                new Vector(0.2192235936, -0.2192235936),
                new Vector(-0.3903882032, -1.5),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                3, 14,
                1, 14,
                2, 14,
                3, 15,
                0, 15,
                12, 13,
                13, 15,
                13, 16,
                4, 16,
                16, 17,
                11, 17,
                5, 17,
                17, 18,
                6, 18,
                10, 18,
                18, 22,
                22, 19,
                7, 22,
                9, 19,
                19, 21,
                0, 21,
                3, 21,
                3, 20,
                20, 1,
                20, 8,
            };

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

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

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

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

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

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0, -0.4142135624),
                new Vector(0, 0.527864045),
                new Vector(-1.2928932188, -1.2928932188),
                new Vector(1.2928932188, -1.2928932188),
                new Vector(1.1213203436, -0.8786796564),
                new Vector(-1.1213203436 , -0.8786796564),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

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

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(1, -0.4142135624),
                new Vector(0, 0.527864045),
                new Vector(1.4142135624, -0.5857864376),
                new Vector(-1, -1),
                new Vector(-0.4142135624, -1),
                new Vector(0, -0.8284271247),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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

        public void IrregularOctogon_OneReflexVertex()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(54.5825,0),
                new Vector(38.926228304,38.926228304),
                new Vector(0,36.614),
                new Vector(-41.9441600464,41.944160046),
                new Vector(-32.5,0),
                new Vector(-22.9809703886,-22.9809703886),
                new Vector(0,-32.5),
                new Vector(22.980970389,-22.9809703886)
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(20.48080291975186, 9.799370574873834),                 
                new Vector(-5.297994362051657, 8.626143422407683),                 
                new Vector(0.0000000000999822, 0.0000000000999822),
                new Vector(-1.0478157974022897, 5.380032857876351),
                new Vector(7.266531812293615, 5.064796778424883),
                new Vector(1.5537934327323422, 3.751189178233879),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void IrregularOctogon_TwoReflexVertex()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(35.096, 0),
                new Vector(38.30008525, 38.30008525),
                new Vector(0, 40.277),
                new Vector(-35.4960533088, 35.496053309),
                new Vector(-54.3735, 0),
                new Vector(-39.4745896131, -39.4745896131),
                new Vector(0, -35.415),
                new Vector(39.326804296, -39.3268042959)
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(1.4081681481, 6.0814026579),
                new Vector(-16.5671059612, -2.4205881092),
                new Vector(0.1012560032, -0.4148026413),
                new Vector(-0.0587232651, -0.222576269),
                new Vector(-11.4885899037, 0.9963340311),
                new Vector(-2.400797515, 2.0753763509),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void IrregularOctogon_TwoOppositeReflexVertices()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(59.384, 0),
                new Vector(30.821370378, 30.821370378),
                new Vector(0, 58.3115),
                new Vector(-26.527818003, 26.527818003),
                new Vector(-52.1295, 0),
                new Vector(-31.7236386312, -31.7236386312),
                new Vector(0, -46.1345),
                new Vector(24.174920189, -24.1749201886),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-8.0485689608, -4.334410328),
                new Vector(6.3717081058, 5.9014864287),
                new Vector(-6.5966992128, -4.0576182117),
                new Vector(0.1979609236, 2.5347609672),
                new Vector(1.7514131247, 4.1547202215),
                new Vector(3.8461849035, 6.0616277961),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void IrregularOctogon_TwoOppositeReflexVertices2()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(59.1805, 0),
                new Vector(32.054211051, 32.054211051),
                new Vector(0, 49.3905),
                new Vector(-23.8249023319, 23.824902332),
                new Vector(-54.6925, 0),
                new Vector(-28.5073634369, -28.5073634369),
                new Vector(0, -44.9135),
                new Vector(24.023245784, -24.023245784),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-8.8257729056, -3.9196020325),
                new Vector(11.28475311, 6.4820919161),
                new Vector(-1.0509346725, -1.1678786244),
                new Vector(-4.0110534725, -3.5938236289),
                new Vector(3.2007123677, 2.9399118538),
                new Vector(7.0670048528, 6.2633113949),

            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void IrregularNonogram()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(58.465346535, 0),
                new Vector(43.41902538, 31.545768463),
                new Vector(15.868991526, 48.839733972),
                new Vector(-11.3748169767, 35.008086947),
                new Vector(-28.2755444569, 20.54338555),
                new Vector(-58.3168316832, 0),
                new Vector(-43.0096218407, -31.2483193807),
                new Vector(-13.310847541, -40.9665763427),
                new Vector(16.790263314, -51.6751169855),
                new Vector(29.450354614, -21.3969350917),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-23.758004344, -9.1101682569),
                new Vector(19.068343458, 9.8569826718),
                new Vector(14.090038049, 9.6705646315),
                new Vector(-2.2620219038, -8.6059205853),
                new Vector(-7.3473757429, -6.7678250079),
                new Vector(1.3807116689, 0.6458670456),
                new Vector(8.0394939578, 5.9392466828),
                new Vector(-3.4566253612, -5.9960432125),

            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void _7gram()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-3.4744727835, -0.4548106187),
                new Vector(-61.0864419834, -36.5869180706),
                new Vector(22.390582622, -27.5538736909),
                new Vector(-3.6834765739, -2.4813353007),
                new Vector(134.27426602, 87.704691313),
                new Vector(-1.7535738592, 4.0155507588),
                new Vector(-3.491408032, 4.2609182765),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-2.6860177798, -0.8891622033),
                new Vector(-4.9823475298, -2.359645842),
                new Vector(-1.2755608595, 1.7239093591),
                new Vector(-1.2788040917, 1.7231862835),
                new Vector(-6.5621956643, -17.6687008714),

            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void PrecursorTo_Irregular_11gram()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-12.3676733734, 2.5607593122),
                new Vector(-26.6382945803, -15.9245719431),
                new Vector(-1.0492078508, -11.6058985007),
                new Vector(4.0180131195, -14.3875634023),
                new Vector(4.8194370778, -6.6168649425),
                new Vector(19.975097948, 8.0263987385),
                new Vector(18.571020378, 15.181606543),
                new Vector(14.663186733, 19.600915263),
                new Vector(-2.740972779, 13.125374693),
                new Vector(-12.4105162453, 14.490632618),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.1697421489, -6.4020872148),
                new Vector(12.849333183, 12.354559768),
                new Vector(11.854467904, 10.577706354),
                new Vector(-4.186402395, -2.2367291895),
                new Vector(-4.3025117649, -2.5273442153),
                new Vector(-2.7972169659, -0.6844593552),
                new Vector(-1.5495185698, 2.1329198165),
                new Vector(-1.6169524027, 2.1110233343),
            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void Irregular_11gram()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(45.522552255, 0),
                new Vector(40.424592205, 25.979307928),
                new Vector(21.591069625, 47.277847767),
                new Vector(-5.3559852776, 37.251695849),
                new Vector(-36.031748744, 41.582854743),
                new Vector(-35.9202925106, 10.547149515),
                new Vector(-56.9784716344, -16.730388799),
                new Vector(-35.812020995, -41.3292754028),
                new Vector(-5.1994232993, -36.1627833717),
                new Vector(23.780110233, -52.0711780839),
                new Vector(27.338426138, -17.5693396564),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-26.6382945803, -15.9245719431),
                new Vector(-0.1697421489, -6.4020872148),
                new Vector(12.849333183, 12.354559768),
                new Vector(11.854467903, 10.577706354),
                new Vector(-4.186402395, -2.2367291896),
                new Vector(-4.3025117649, -2.5273442153),
                new Vector(-2.7972169659, -0.6844593552),
                new Vector(-1.5495185699, 2.1329198165),
                new Vector(-1.6169524026, 2.1110233345),
            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("",exc);
                }
            }
        }

        public void Irregular_11gram2()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(55.115511551, 0),
                new Vector(35.056857892, 22.529674549),
                new Vector(17.850506499, 39.087157028),
                new Vector(-4.8213261217, 33.533059739),
                new Vector(-32.4260524036, 37.421659342),
                new Vector(-42.6494098998, 12.522996655),
                new Vector(-55.4320940697, -16.2763313779),
                new Vector(-33.222115232, -38.34036482),
                new Vector(-7.9470860184, -55.2731973486),
                new Vector(15.659180881, -34.2888232352),
                new Vector(27.338426138, -17.5693396564),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(17.181344797, 5.333593764),
                new Vector(8.9877343062, 6.1648004199),
                new Vector(5.9147450655, 4.8578945272),
                new Vector(-3.0730055713, -1.2995142772),
                new Vector(-10.9604685938, -11.1569384819),
                new Vector(-10.2031730365, -1.335642573),
                new Vector(-10.9457462336, -10.6259183643),
                new Vector(-11.1836937446, -7.9736215343),
                new Vector(-8.8322490488, -3.8064413224),
            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void Irregular_Nonogram2()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(9.7552205221, 0),
                new Vector(6.7128458179, 4.8771679706),
                new Vector(2.0577472251, 6.3330947584),
                new Vector(-2.958955932, 9.106729959),
                new Vector(-4.509450532, 3.2763075894),
                new Vector(-5.0684428443, 0),
                new Vector(-7.4710207182, -5.4280142793),
                new Vector(-2.0000130599, -6.1554072687),
                new Vector(2.9614258428, -9.1143315629),
                new Vector(7.580139707, -5.5072938654),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0608577803, 2.3073954788),
                new Vector(0.1493902678, 1.8703399691),
                new Vector(-0.3589583915, -1.4408845002),
                new Vector(-0.3252385681, -1.4301512013),
                new Vector(2.496876605, -1.7070967353),
                new Vector(2.4267380873, -0.6672391249),
                new Vector(1.6206801985, -0.5329378101),
                new Vector(2.1823053834, -0.7840399858),
            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void OctogonTrouble()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(4.6658055806, 0),
                new Vector(2.7199171021, 2.7199171021),
                new Vector(0, 9.6792889289),
                new Vector(-1.1494335776, 1.1494335776),
                new Vector(-8.1866336634, 0),
                new Vector(-6.8124996742, -6.8124996742),
                new Vector(0, -2.3229162916),
                new Vector(1.9286703421, -1.9286703421),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.4479091564, -0.4038607662),
                new Vector(-0.7059792034, -0.6159455193),
                new Vector(0.9493834108, 1.7600414341),
                new Vector(1.0101676787, 0.1978047915),
                new Vector(1.2424400633, 0.58054091),
                new Vector(-4.9171930285, -2.2604685141),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void OctogonTrouble2()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(1.0860306031, 0),
                new Vector(4.8569898245, 4.8569898245),
                new Vector(0, 1.1279927993),
                new Vector(-3.9025484202, 3.9025484202),
                new Vector(-5.3941494149, 0),
                new Vector(-3.0886946099, -3.0886946099),
                new Vector(0, -9.6962736274),
                new Vector(2.6174789055, -2.6174789055),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0423638074, 0.0683546334),
                new Vector(0.0214248614, -0.0386034895),
                new Vector(-2.8294826532, 0.3563522186),
                new Vector(-0.8676514689, -1.7596408978),
                new Vector(-1.2420455551, -1.1947385496),
                new Vector(-0.2836869693, -2.8722860144),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void OctogonTrouble2_Precursor()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0.0423638074, 0.0683546334),
                new Vector(0.0197789943, 0.0510149428),
                new Vector(-3.4927532575, 2.5482846891),
                new Vector(-4.4147238614, 0.1360880385),
                new Vector(-2.3414481246, -2.6415485384),
                new Vector(-0.093346158, -7.4508655025),
                new Vector(1.6628609026, -2.7013222512),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0214248614, -0.0386034896),
                new Vector(-2.8294826533, 0.3563522186),
                new Vector(-0.8676514688, -1.7596408978),
                new Vector(-1.2420455551, -1.1947385497),
                new Vector(-0.2836869693, -2.8722860144),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void OctogonTrouble2_Precursor2()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(0.0214248614, -0.0386034896),
                new Vector(-3.4586530206, 2.4355924996),
                new Vector(-4.3332230374, 0.1474123165),
                new Vector(-2.2792675902, -2.6043402247),
                new Vector(-0.1011137609, -7.2640186188),
                new Vector(1.5834243864, -2.7082990977),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-2.8294826533, 0.3563522186),
                new Vector(-0.8676514688, -1.7596408978),
                new Vector(-1.2420455551, -1.1947385497),
                new Vector(-0.2836869692, -2.8722860144),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void OctogonTrouble2_Precursor3()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-2.8294826533, 0.3563522186),
                new Vector(-1.1319984459, -1.9178239266),
                new Vector(-0.2444308174, -3.816578572),
                new Vector(0.1177717524, -2.8370262117),
                new Vector(-0.9822148564, -0.9569811978),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.8676514688, -1.7596408978),
                new Vector(-1.2420455551, -1.1947385497),
                new Vector(-0.2836869693, -2.8722860144),
            };

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

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void SnowflakeTree_16gram()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(8.1436723672, 0), 
                new Vector(2.6436176668, 1.0950222913), 
                new Vector(4.5115258373, 4.5115258373), 
                new Vector(0.991790766, 2.3943947182), 
                new Vector(0, 8.3484878488), 
                new Vector(-1.3676299861, 3.3017508607), 
                new Vector(-2.5765036269, 2.5765036269), 
                new Vector(-6.1290467554, 2.5387342905), 
                new Vector(-3.1211971197, 0), 
                new Vector(-6.5379570007, -2.7081104599), 
                new Vector(-3.1339087105, -3.1339087105), 
                new Vector(-3.2682370697, -7.8902222588), 
                new Vector(0, -8.3374977498), 
                new Vector(2.2527447313, -5.438606883), 
                new Vector(1.9322026937, -1.9322026937), 
                new Vector(5.3675321902, -2.2233046297), 
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.2920212548, 2.4882520606), 
                new Vector(4.9297140006, -0.7843685731), 
                new Vector(-2.1626257936, 1.1124372233), 
                new Vector(0.0869745533, -0.0991503036), 
                new Vector(0.0871418593, -0.0993287975), 
                new Vector(0.0870241127, -0.0994347487), 
                new Vector(-0.3690468884, -0.0424024417), 
                new Vector(-0.9717486259, 1.016574392), 
                new Vector(-0.9749823195, -5.9457635067), 
                new Vector(-0.7665452795, -1.1029537037), 
                new Vector(-0.7746660687, -1.0951562424), 
                new Vector(-0.7477307278, -1.3775451015), 
                new Vector(-0.6034208365, -1.4618572664), 
                new Vector(-0.5036467541, -4.6318572007),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                4, 16,
                5, 16,
                16, 23,
                23, 18,
                18, 6,
                7, 18,
                22, 23,
                22, 8,
                22, 26,
                25, 26,
                26, 9,
                25, 10,
                25, 27,
                27, 28,
                3, 27,
                28, 29,
                24, 29,
                11, 24,
                12, 24,
                29, 13,
                28, 21,
                21, 20,
                19, 21,
                20, 14,
                20, 17,
                0, 17,
                15, 17,
                19, 1,
                19, 2,
            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void NumericalNoiseInFraction()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(6.5680918092, 0), 
                new Vector(3.9520013427, 3.9520013427), 
                new Vector(0, 5.8177677768), 
                new Vector(-3.932926644, 3.932926644), 
                new Vector(-5.405139514, 0), 
                new Vector(-4.409794111, -4.409794111), 
                new Vector(0, -6.9077857786), 
                new Vector(4.7015663538, -4.7015663538), 
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.016005806, 0.3196878937), 
                new Vector(0.227813498, -0.9662796996), 
                new Vector(0.268670919, -0.3024686834), 
                new Vector(0.2783581698, -0.3876193306), 
                new Vector(0.3867133628, -0.6415142086), 
                new Vector(0.3867121196, -0.6415138597), 
            };

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

            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void PotatoShape_16()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(5.7108640864, 0),
                new Vector(5.2115370853, 2.1586893416),
                new Vector(4.0685689458, 4.0685689458),
                new Vector(2.3540645618, 5.6832145918),
                new Vector(0, 5.4011431143),
                new Vector(-1.9331093417, 4.6669387903),
                new Vector(-4.1102506947, 4.1102506947),
                new Vector(-6.4567287804, 2.6744646294),
                new Vector(-6.8868046805, 0),
                new Vector(-6.3302712102, -2.6220841888),
                new Vector(-4.6945016505, -4.6945016505),
                new Vector(-2.6301133074, -6.3496552173),
                new Vector(0, -6.7569216922),
                new Vector(1.9331093417, -4.6669387903),
                new Vector(4.1102506947, -4.1102506947),
                new Vector(5.1764612629, -2.1441604602),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-1.2413735665, -3.1952669232),
                new Vector(1.0133913642, 1.6114181198),
                new Vector(1.4487170988, -0.6957920183),
                new Vector(0.9591005478, 1.5007649532),
                new Vector(-2.6252016286, 0.1059259432),
                new Vector(-2.3726481332, -0.002722827),
                new Vector(-1.3749539411, -1.4001875709),
                new Vector(0.7060175536, 0.0424105394),
                new Vector(0.5322881011, 0.2718316109),
                new Vector(-0.7355579379, -0.1880798172),
                new Vector(-0.4212495405, -0.1077121631),
                new Vector(-1.6730239419, -0.437132718),
                new Vector(0.4824410981, 0.1784351517),
                new Vector(-1.3416470789, -0.5492097989),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                2, 17,
                3, 17,
                17, 19,
                4, 19,
                19, 24,
                1, 24,
                14, 18,
                15, 18,
                18, 23,
                0, 23,
                23, 28,
                24, 28,
                28, 26,
                26, 25,
                5, 26,
                13, 25,
                25, 29,
                29, 22,
                22, 10,
                22, 16,
                11, 16,
                12, 16,
                29, 27,
                9, 27,
                21, 27,
                21, 6,
                21, 20,
                7, 20,
                8, 20,
            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void PotatoShape_16_Preshape()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(-0.6206867833, -4.9760943077), 
                new Vector(1.0445731792, -3.1756970028), 
                new Vector(2.9933582146, -2.6773988888), 
                new Vector(3.6121415673, -1.5363635781), 
                new Vector(3.9986754342, 0.0145089053), 
                new Vector(3.6484947933, 1.5284090462), 
                new Vector(2.758758179, 3.0151432376), 
                new Vector(1.7792933277, 3.9375606267), 
                new Vector(0.4005188389, 3.7723514972), 
                new Vector(-1.4297336994, 3.077212687), 
                new Vector(-3.4550427026, 2.5593476387), 
                new Vector(-4.934557545, 1.6540475607), 
                new Vector(-5.1937748975, 0.0420817647), 
                new Vector(-4.782437595, -1.8959167471), 
                new Vector(-3.5051363456, -3.5141773374), 
                new Vector(-1.935743437, -4.7724610702), 
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-1.2413735665, -3.1952669231),
                new Vector(1.0133913641, 1.6114181197),
                new Vector(1.4487170989, -0.6957920183),
                new Vector(0.9591005479, 1.5007649532),
                new Vector(-2.6252016286, 0.1059259433),
                new Vector(-2.3726481333, -0.002722827),
                new Vector(-1.3749539412, -1.4001875709),
                new Vector(0.7060175536, 0.0424105395),
                new Vector(0.5322881012, 0.271831611),
                new Vector(-0.4212495405, -0.1077121631),
                new Vector(-0.7355579379, -0.1880798172),
                new Vector(-1.6730239418, -0.437132718),
                new Vector(0.4824410981, 0.1784351517),
                new Vector(-1.3416470789, -0.5492097989),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                7, 17,
                8, 19,
                6, 17,
                17, 19,
                19, 24,
                24, 5,
                24, 28,
                28, 23,
                23, 4,
                23, 18,
                2, 18,
                3, 18,
                25, 28,
                25, 26,
                26, 29,
                25, 9,
                26, 1,
                29, 22,
                22, 16,
                22, 14,
                15, 16,
                0, 16,
                27, 29,
                13, 27,
                21, 27,
                21, 10,
                20, 21,
                11, 20,
                12, 20,
            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void _13()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(2.518739874, 0), 
                new Vector(5.9360700983, 3.1154899234), 
                new Vector(3.2390325799, 4.6925488155), 
                new Vector(0.9177842934, 7.5586336929), 
                new Vector(-1.9071231726, 5.0286705241), 
                new Vector(-1.7783631735, 1.5754922929), 
                new Vector(-9.2757978308, 2.2862788273), 
                new Vector(-0.9128426167, -0.2249954974), 
                new Vector(-7.4656637192, -6.6140009119), 
                new Vector(-1.0299117528, -2.7156541058), 
                new Vector(0.1884711966, -1.552199953), 
                new Vector(0.3206728052, -0.4645747627), 
                new Vector(1.9612970517, -1.0293681005), 
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0691330123, -0.0180685302), 
                new Vector(-0.9034577548, 0.649006763), 
                new Vector(-1.5505453073, -2.0357220055), 
                new Vector(-0.626180876, -1.1437950921), 
                new Vector(-0.6389832185, 0.8534939696), 
                new Vector(-0.6305258393, 1.0554947822), 
                new Vector(1.1401017857, 1.0787125455), 
                new Vector(0.62920015, 3.9516151977), 
                new Vector(1.4812459906, 2.6457683335), 
                new Vector(0.9088439532, 2.1974635385), 
                new Vector(1.1086859498, 2.6739163251), 
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                8, 15,
                15, 9,
                15, 16,
                16, 10,
                16, 13,
                13, 7,
                13, 17,
                14, 17,
                17, 18,
                14, 5,
                14, 6,
                18, 11,
                18, 22,
                22, 19,
                0, 19,
                12, 19,
                22, 23,
                23, 21,
                21, 1,
                21, 2,
                23, 20,
                20, 4,
                20, 3,
            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void Clover110()
        {
            var verticesStrings = new string[]
            {
                "<0x400039B7639B7639 : 0x0>",
                "<0x4004305A1352F7B7 : 0x3FC27897C3B4E67D>",
                "<0x40080F75E7AE3397 : 0x3FD615DBAC34FA91>",
                "<0x400BCD29AA6FE3DC : 0x3FE33EB1A78FCE58>",
                "<0x400F5FBB28E85558 : 0x3FED2ECBD311E918>",
                "<0x40115ED26B759DEB : 0x3FF466D1A5EECF82>",
                "<0x4012EED19BF59878 : 0x3FFB055DA91FC482>",
                "<0x40145B60FF3C85A4 : 0x400134B1B88A3E67>",
                "<0x4015A03469590CDF : 0x400543EFECF358CA>",
                "<0x4016B933D842EBE5 : 0x4009AA402D54C94D>",
                "<0x4017A2816794C1AD : 0x400E60D8F82F051D>",
                "<0x4018587F01C6D749 : 0x4011B02C69AC25F7>",
                "<0x4018D7D3C81B7B5C : 0x40145067AB16B8FB>",
                "<0x40191D712ABB7390 : 0x40170CE377D0985D>",
                "<0x40192697AAD60F69 : 0x4019E127AEB04923>",
                "<0x4018F0DB40F43126 : 0x401CC884643C1341>",
                "<0x3F92BF72DA7DAA64 : 0x3F9850091F4454E8>",
                "<0x3FD321068B0904E0 : 0x3FDBF9ABEED33DF7>",
                "<0x3FE1015AA0D20E40 : 0x3FEC333A1BB8CBC6>",
                "<0x3FE6D3DDAD52F3DF : 0x3FF5A1ADC4BC0245>",
                "<0x3FEAF6108645929C : 0x3FFD84B4E442C003>",
                "<0x3FED58B956F84CBC : 0x4002D8119901D442>",
                "<0x3FEDEF76E679B788 : 0x4007086DFA1467E0>",
                "<0x3FECB0D39A87CE95 : 0x400B49A7951C8FD5>",
                "<0x3FE99654DA9FF65D : 0x400F91CA309CDCA7>",
                "<0x3FE49C86C015E697 : 0x4011EB6181002FC6>",
                "<0x3FDB860808621974 : 0x4014073741FF67A3>",
                "<0x3FC431E885E95B9D : 0x401617533592CA0E>",
                "<0xBFC605597992E082 : 0x401816A7D4249A00>",
                "<0xBFE1DD9D6A91AC7A : 0x401A00343446A72C>",
                "<0xBFEFFC82C6DC9D38 : 0x401BCF0B0156C3A1>",
                "<0xBFF7E7989AB13947 : 0x401D7E59609FBCAA>",
                "<0xC00050F958E4F67A : 0x401F096DBCE27A93>",
                "<0xC00511802302D302 : 0x402035DF3825995E>",
                "<0xC00A2F87AE9DBF66 : 0x4020D078227BBC3C>",
                "<0xC00FA48C26B21401 : 0x4021526E622DA951>",
                "<0xBF8CA7A34ADABA88 : 0x3F9B274A36631DE5>",
                "<0xBFD180300D4F1BC6 : 0x3FDD058E99F5CC14>",
                "<0xBFE2966427CE8B2F : 0x3FEB2EECE536302B>",
                "<0xBFEDDEDEB5E0B690 : 0x3FF35E5190C2C326>",
                "<0xBFF54036246774EA : 0x3FF88656B829DF65>",
                "<0xBFFC2FCE2D9D471A : 0x3FFD00E361CFAFCC>",
                "<0xC001D7B393C3B56B : 0x40006032D07820FA>",
                "<0xC005D7964F00B0A1 : 0x4001DC37D694EBF1>",
                "<0xC00A0F2D968C7837 : 0x4002EEE503949D39>",
                "<0xC00E75AB7602287E : 0x40039342111D5901>",
                "<0xC01180F0BD0085C5 : 0x4003C501BF5F1426>",
                "<0xC013D5267A07E54B : 0x400380889199C476>",
                "<0xC0163291D86EFF78 : 0x4002C2F2B1AF8512>",
                "<0xC018943089258069 : 0x40018A18F370E45F>",
                "<0xC01AF4E9BF12086E : 0x3FFFA929E2901CD8>",
                "<0xC01D4F9509139D2D : 0x3FFB438879CA47CD>",
                "<0xC01F9F0146C1FDA2 : 0x3FF5E3953F23852B>",
                "<0xC020EEFDD7F3CE64 : 0x3FEF164D9B6A1127>",
                "<0xC02203AB734B67BB : 0x3FE07B46ED27C6AA>",
                "<0xC0230AF905D5956F : 0x3CF84B47A149731C>",
                "<0xBF9EA6C861E58CD7 : 0xBF5C0B1FD4CBC82B>",
                "<0xBFE0D5A66736F20E : 0xBFAEE7C7C6AAE773>",
                "<0xBFF0396258909144 : 0xBFC6762BDD8B979D>",
                "<0xBFF7D28EBB76D147 : 0xBFD628A29C449B1D>",
                "<0xBFFF22EC5F64CDA3 : 0xBFE248F2D29B0442>",
                "<0xC0030BBC214B8128 : 0xBFEB2EA284637AC4>",
                "<0xC0064ED9828048F8 : 0xBFF2DAD9B59FB9E3>",
                "<0xC00951DD79868DE6 : 0xBFF8E5D64866E663>",
                "<0xC00C0C32AAFDD8B5 : 0xBFFFADB041768C0F>",
                "<0xC00E75AB76022884 : 0xC0039342111D58F7>",
                "<0xC0104346DAD8B19B : 0xC007A19863836160>",
                "<0xC0111BCEFD1AA0CE : 0xC00BFAB40F4A7CC7>",
                "<0xC011C11515FB73EF : 0xC0104B705975CEEE>",
                "<0xC0123009C6219F21 : 0xC012B6F334E7D67C>",
                "<0xC01265EC03AB6A90 : 0xC0153B8A2780DF69>",
                "<0xC012604D66427B74 : 0xC017D4A5D0766298>",
                "<0xC0121D1610FB60AC : 0xC01A7D85BCCCC41C>",
                "<0xC0119A883529F28E : 0xC01D313E871B282C>",
                "<0xC010D74329C31420 : 0xC01FEAC0340A13CC>",
                "<0xC00FA48C26B213F0 : 0xC021526E622DA953>",
                "<0xBF86470C2CF86322 : 0xBF9C9C145350E9C5>",
                "<0xBFC4F1F89B69D124 : 0xBFE01D9CD0D9A3CC>",
                "<0xBFD0BE3E1CC95849 : 0xBFEFD94774C32535>",
                "<0xBFD36DB80F05852C : 0xBFF7F8914975FE07>",
                "<0xBFD27915729E60D3 : 0xC0000F70015337D0>",
                "<0xBFCBB01166400CA2 : 0xC00425CE071150D2>",
                "<0xBFB62167873395AA : 0xC008355839737496>",
                "<0x3FB9C8496E869F5F : 0xC00C34017697147F>",
                "<0x3FD60D3B7FE145D4 : 0xC0100BE3F5CFE7F1>",
                "<0x3FE49C86C015E713 : 0xC011EB6181002FC3>",
                "<0x3FEFEFB862453EDA : 0xC013B3989AAECDD7>",
                "<0x3FF679186BB85BCE : 0xC0155FC2E0EC974E>",
                "<0x3FFDC983E636047F : 0xC016EB3B0D5C3344>",
                "<0x4002EFA0650CA4AC : 0xC01851838CC9DF3D>",
                "<0x400757897A51D9B2 : 0xC0198E4CEB4271BA>",
                "<0x400C16368B7C462E : 0xC01A9D7C0D11764C>",
                "<0x4010925FE1E4A29A : 0xC01B7B302D436B66>",
                "<0x40133DD22D44A1DD : 0xC01C23C89A865631>",
                "<0x40160969CA2414B7 : 0xC01C93EA2B87CEF9>",
                "<0x4018F0DB40F43153 : 0xC01CC884643C131A>",
                "<0x3F9565A6B2E171BF : 0xBF96045EAB7959DF>",
                "<0x3FD8F7DB521DB0B9 : 0xBFD6EA649E147180>",
                "<0x3FE97E32E3FBEDE1 : 0xBFE4D8723EC7DB32>",
                "<0x3FF3C97A916059B3 : 0xBFECC0924EFECAC1>",
                "<0x3FFB4CA839B59B5A : 0xBFF18B56541759A6>",
                "<0x40019BAC74790C7F : 0xBFF3E333658B219C>",
                "<0x4005BBC19AE43ECA : 0xBFF55F0791B3BD78>",
                "<0x4009FD3B34E53CB8 : 0xBFF5F75BA7EA46DD>",
                "<0x400E5679FBAB511F : 0xBFF5A6257FF3C11E>",
                "<0x40115ED26B759DF8 : 0xBFF466D1A5EECED6>",
                "<0x4013945B237D26DD : 0xBFF2364B37527942>",
                "<0x4015C6C507AE3010 : 0xBFEE2603CE1A2011>",
                "<0x4017F0F588F76145 : 0xBFE5F9DC41BA4031>",
                "<0x401A0DD0A54F392A : 0xBFD7D64D1849E0F6>",
            };
            var vertices = new PerforatedPolygon(new SimplePolygon(verticesStrings.Select(x => Vector.Parse(x)).ToList()));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0000539388, -0.0000143758),
                new Vector(0.000055804, -0.0000014029),
                new Vector(0.0000244579, 0.0000501783),
                new Vector(-0.0000354836, 0.0000430925),
                new Vector(0.0000081806, -0.0000692028),
                new Vector(0, 0),
                new Vector(5.8942087391, -0.5154734488),
                new Vector(0.5587824554, -0.1478647487),
                new Vector(0.560301219, -0.1485266401),
                new Vector(-0.5128574002, 0.2885911235),
                new Vector(0.0494630559, 0.5863965855),
                new Vector(-0.475560383, -0.3466264149),
                new Vector(0.1177475548, -0.5765787568),
                new Vector(5.9908919097, 6.4610413575),
                new Vector(-3.3884635015, 8.1335205413),
                new Vector(-8.8061291287, 0.2965317253),
                new Vector(5.5426844593, -6.849415324),
                new Vector(-3.9279329915, -7.8871530802),
                new Vector(5.3113572304, -0.6209516501),
                new Vector(1.0113792621, -0.3152178305),
                new Vector(0.6012517934, 0.0352901536),
                new Vector(4.7605852989, -0.6929893083),
                new Vector(1.4556755899, -0.4513146388),
                new Vector(-0.9684293828, 0.5117223537),
                new Vector(-0.8677791303, -0.6683372036),
                new Vector(0.0631789211, 1.0934915),
                new Vector(0.2474524254, -1.06699697),
                new Vector(5.7367938263, 5.7928833899),
                new Vector(-3.8723695185, -7.1744725023),
                new Vector(-8.1347701718, 0.542047624),
                new Vector(4.917489304, -6.5028147997),
                new Vector(-2.8862417949, 7.6248219439),
                new Vector(4.2377011961, -0.7349212964),
                new Vector(1.8980635245, -0.560029696),
                new Vector(3.7386049808, -0.7493655613),
                new Vector(2.3431824904, -0.6434708959),
                new Vector(3.2592275228, -0.7382444571),
                new Vector(2.7954755966, -0.7027810218),
                new Vector(-1.4046452803, 0.6954886286),
                new Vector(0.0491279716, 1.5666267068),
                new Vector(-1.2161494463, -0.9887938714),
                new Vector(0.3942318042, -1.5170082665),
                new Vector(-2.4417222544, 7.1338468469),
                new Vector(-7.5035034239, 0.7424383943),
                new Vector(5.4748472598, 5.184575767),
                new Vector(4.3526522589, -6.1569632706),
                new Vector(-3.7924136905, -6.5170067364),
                new Vector(-1.8276939375, 0.8462972033),
                new Vector(-1.5290705145, -1.3109643195),
                new Vector(0.0105675129, 2.0140934469),
                new Vector(0.5572962421, -1.935485723),
                new Vector(-6.9087347094, 0.9027695897),
                new Vector(5.2065268155, 4.6300849599),
                new Vector(-2.0488040159, 6.6594301799),
                new Vector(3.8419913493, -5.812461672),
                new Vector(-3.6911802223, -5.9093820982),
                new Vector(-2.2431218669, 0.9688076521),
                new Vector(2.2011084028, 1.0608043061),
                new Vector(-0.0505680618, 2.442872663),
                new Vector(-1.8130849372, -1.6379581763),
                new Vector(0.7367564614, -2.3296724863),
                new Vector(-6.3470630104, 1.0273879999),
                new Vector(4.932890385, 4.1239941088),
                new Vector(-1.7021202666, 6.2002839901),
                new Vector(-3.5712102594, -5.3466991914),
                new Vector(3.3799942977, -5.4695862282),
                new Vector(-2.6559368188, 1.066273001),
                new Vector(2.5451041011, 1.3089628003),
                new Vector(-0.1333999906, 2.8588709206),
                new Vector(-2.0732320656, -1.9729792954),
                new Vector(0.9334333678, -2.7054834404),
                new Vector(-5.8152214456, 1.120001927),
                new Vector(4.6546011635, 3.6614058483),
                new Vector(-1.3969407047, 5.7549771021),
                new Vector(-3.4345198801, -4.8244458719),
                new Vector(2.9617192043, -5.1282964162),
                new Vector(-3.0706932405, 1.140798425),
                new Vector(2.8730343533, 1.5736110156),
                new Vector(-2.31331882, -2.3192960269),
                new Vector(-0.2379053248, 3.267105612),
                new Vector(1.1487185051, -3.0677392033),
                new Vector(-5.3100212364, 1.1837383743),
                new Vector(-1.1290962416, 5.3219079048),
                new Vector(4.3719341766, 3.2378625087),
                new Vector(-3.2826288403, -4.3384225205),
                new Vector(2.5827146317, -4.7882300698),
                new Vector(-3.4915660381, 1.1935380515),
                new Vector(3.1885053727, 1.8571483428),
                new Vector(-2.5361293504, -2.680226557),
                new Vector(-0.3647685518, 3.6718538074),
                new Vector(1.384473624, -3.4203507515),
                new Vector(-4.8282974232, 1.2211789592),
                new Vector(4.0847678728, 2.8492815729),
                new Vector(-0.8949237835, 4.8992698924),
                new Vector(-3.1165706901, -3.884677746),
                new Vector(2.2389569156, -4.4486858719),
                new Vector(-3.9224168277, 1.2248437345),
                new Vector(3.4943118936, 2.1622627811),
                new Vector(-0.5152737873, 4.0767743215),
                new Vector(-2.7435878877, -3.0591373697),
                new Vector(1.6429616317, -3.7664669149),
                new Vector(-4.3668553134, 1.2343753087),
                new Vector(-2.9368845319, -3.4594532772),
                new Vector(-0.6912299817, 4.4850093471),
                new Vector(3.7925606897, 2.4919051237),
                new Vector(1.9268034614, -4.108592965),                
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                115, 112,
                115, 113,
                115, 110,
                115, 114,
                115, 111,
                
                112, 56,
                111, 36,
                114, 16,
                110, 96,
                113, 76,
                114, 130,
                110, 122,
                77, 122,
                78, 136,
                122, 136,
                136, 151,
                79, 151,
                80, 160,
                151, 160,
                160, 170,
                81, 170,
                170, 180,
                180, 190,
                190, 200,
                200, 210,
                210, 215,
                215, 205,
                205, 195,
                185, 195,
                185, 175,
                175, 164,
                164, 155,
                155, 140,
                140, 126,
                126, 95,
                126, 94,
                140, 93,
                155, 92,
                164, 91,
                175, 90,
                185, 89,
                195, 88,
                205, 87,
                215, 86,
                210, 85,
                200, 84,
                190, 83,
                180, 82,
                129, 98,
                129, 132,
                132, 99,
                132, 143,
                143, 100,
                143, 145,
                145, 101,
                145, 147,
                147, 102,
                147, 146,
                146, 103,
                146, 144,
                144, 104,
                144, 142,
                142, 105,
                142, 131,
                131, 106,
                131, 128,
                128, 107,
                128, 116,
                116, 108,
                116, 109,
                124, 35,
                124, 34,
                124, 141,
                141, 33,
                141, 152,
                152, 32,
                152, 163,
                163, 31,
                163, 173,
                173, 30,
                173, 183,
                183, 29,
                183, 192,
                192, 28,
                192, 203,
                203, 27,
                203, 213,
                213, 26,
                213, 208,
                208, 25,
                199, 24,
                208, 199,
                199, 189,
                189, 23,
                189, 178,
                178, 22,
                178, 168,
                168, 21,
                168, 159,
                159, 20,
                159, 149,
                149, 19,
                149, 135,
                135, 18,
                135, 120,
                120, 17,
                15, 123, 123, 14,
                123, 137, 137, 13,
                137, 154, 154, 12,
                154, 162, 162, 11,
                162, 172, 172, 10,
                172, 182, 182, 9,
                182, 193, 193, 8,
                193, 202, 202, 7,
                202, 214, 214, 6,
                214, 207, 207, 5,
                207, 197, 197, 4,
                197, 187, 187, 3,
                187, 177, 177, 2,
                177, 167, 167, 1,

                127, 75, 127, 74,
                127, 138, 138, 73,
                138, 156, 156, 72,
                156, 165, 165, 71,
                165, 174, 174, 70,
                174, 184, 184, 69,
                184, 194, 194, 68,
                194, 204, 204, 67,
                204, 212, 212, 66,
                212, 209, 209, 65,
                209, 198, 198, 64,
                198, 188, 188, 63,
                188, 179, 179, 62,
                179, 169, 169, 61,
                169, 158, 158, 60,
                158, 150, 150, 59,
                150, 134, 134, 58,
                134, 121, 121, 57,

                55, 125, 125, 54,
                125, 139, 139, 53,
                139, 153, 153, 52,
                153, 161, 161, 51,
                161, 171, 171, 50,
                171, 181, 181, 49,
                181, 191, 191, 48,
                191, 201, 201, 47,
                201, 211, 211, 46,
                211, 206, 206, 45,
                206, 196, 196, 44,
                196, 186, 186, 43,
                186, 176, 176, 42,
                176, 166, 166, 41,
                166, 157, 157, 40,
                157, 148, 148, 39,
                148, 133, 133, 38,
                133, 119, 119, 37,

                117, 118,
                117, 130,
                117, 0,
                118, 97,
                118, 129,

                130, 167,
                120, 111,
                119, 112,
                121, 113,
            };

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void AwkwardDegenerateClover()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                new Vector(2.5, 0.5),
                new Vector(2.6888772695, 1.159868436),
                new Vector(0.0089363264, 0.0044879918),
                new Vector(5.3662628852, 3.0982133213),
                new Vector(-2.7692749288, 6.4199008937),
                new Vector(-0.0044879918, 0.0089363264),
                new Vector(-2.5, 4.5),
                new Vector(-7.5, -1.75),
                new Vector(7.571224879, -3.2659076183),
                new Vector(0.0093969262, -0.0034202014),
                new Vector(9.0582607798, -2.7118652563),
                new Vector(0.01, 0),
            }));

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0000002271, 0.0000001308),
                new Vector(0.0000003245, 0.0000007518),
                new Vector(0.0000003253, 0.0000007515),
                new Vector(0.0033312441, 0.0003104013),
                new Vector(0.0033379413, 0.0001949149),
                new Vector(1.2236618366, -2.4876639594),
                new Vector(2.2996367177, 0.7172030409),
                new Vector(1.7577948442, -1.7580654565),
                new Vector(0.9263799783, 2.7957073088),
                new Vector(-2.8611154014, 0.1998423818),

            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void TrisWithTrisHole()
        {
            var vertices = new PerforatedPolygon(new SimplePolygon(new Vector[]
            {
                Vector.Parse("<0x3FF573EBD558160C : 0x0>"),
                //new Vector(1.3408010801, 0),
                Vector.Parse("<0xBFE573EBD5581609 : 0x3FF29424AF0674F1>"),
                //new Vector(-0.6704005401, 1.1611677968),
                Vector.Parse("<0xBFF353A0088DA54E : 0xC000BCC4E08DE630>"),
                // new Vector(-1.2079162916, -2.0921723884),
            }), new[] { new SimplePolygon(new Vector[]
            {
                //new Vector(0.009 , 0),
                //new Vector(-0.0045, 0.0077942286),
                //new Vector(-0.0045, -0.0077942286),
                Vector.Parse("<0x3F826E978D4FDF3C : 0x0>"),
                Vector.Parse("<0xBF726E978D4FDF3A : 0x3F7FECD7514B18D6>"),
                Vector.Parse("<0xBF726E978D4FDF41 : 0xBF7FECD7514B18D3>"),
            })});

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.6749005401, 0),
                new Vector(-0.33745027, 0.5844810127),
                new Vector(0.6749005401, -0.0546395588),
                new Vector(-0.384769516, 0.5571612333),
                new Vector(-0.5018034604, -0.8691490888),
            };

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

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void ConchWithHole()
        {
            var radiiOut = new string[] {
                "1.3947524752", //0x3FF650E7F8B3402E",
                "1.3947524752", //0x3FF650E7F8B3402E",
                "1.775409541", //0x3FFC6813D5B677A7",
                "2.175049505", //0x400166805AD78C03",
                "3.4748784878", //0x400BCC8D17B71362",
                "3.7026732673", //0x400D9F13297788C4",
                "4.3450945095", //0x4011616074807BE0",
                "4.9145814581", //0x4013A8880AB10E9C",
                "5.2712601260", //0x401515C536E7BB5A",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.5725234137, 0.4804041853),
                new Vector(0.7473762376, 0),
                new Vector(0.5056552889, 0.5600945133),
                new Vector(0.1498047604, 0.8495850143),
                new Vector(0.7473762376, -0.358539028),
                new Vector(-0.1031276235, 0.9373138295),
                new Vector(0.796302796, -0.6681773825),
                new Vector(-0.5315119527, 0.9206057069),
                new Vector(-0.9659234156, 0.7430288218),
                new Vector(-1.3442490666, 0.4892666477),
                new Vector(-1.7300497159, -0.0388634716),
                new Vector(-1.7561737062, -0.6391949553),
                new Vector(-1.6724585209, -0.9045716755),
                new Vector(-1.0547175132, -1.8268243205),
                new Vector(-0.7098080678, -2.0791224385),
                new Vector(0.7566260727, -2.5842233097),
                new Vector(0.4191856687, -2.3773200621),
                new Vector(0.464233639, -2.3732167883),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                18, 19,
                18, 20,
                20, 21,
                21, 23,
                23, 25,
                25, 26,
                26, 27,
                27, 28,
                28, 29,
                29, 30,
                30, 31,
                31, 32,
                32, 34,
                34, 35,
                19, 22,
                22, 24,
                24, 35,
                33, 35,

                8, 33,
                7, 33,
                6, 32,
                5, 30,
                4, 28,
                3, 26,
                2, 23,
                1, 20,
                0, 22,

                9, 19,
                17, 18,
                16, 21,
                25, 15,
                27, 14,
                29, 13,
                31, 12,
                34, 11,
                10, 24,
            };

            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.1));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void ThinPentagon()
        {
            var radiiOut = new string[] {
                "0x3F847AE147AE147B",//--0.01",
                "0x3F847AE147AE147B",//--0.01",
                "0x3F847AE147AE147B",//--0.01",
                "0x3F847AE147AE147B",//--0.01",
                "0x3F847AE147AE147B",//--0.01",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0029356614, -0.0090350369),
                new Vector(0.0095, 0),
                new Vector(-0.0076856614, -0.0055839599),
                new Vector(0.0029356614, 0.0090350369),
                new Vector(-0.0076856614, 0.0055839599),
            };

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

            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void BoxyOctogon()
        {
            var radiiOut = new string[] {
                "0x40073A26497EE865",
                "0x400F4AB8B9BD49B5",
                "0x400264398CEAE250",
                "0x400266455DD66513",
                "0x3FF2FDB479FEC3D3",
                "0x3FF2FDB479FEC3D3",
                "0x4019F7F8D900D1FF",
                "0x401832BF953B2E8E",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.597969847, 0),
                new Vector(-0.4228285337, -0.4228285337),
                new Vector(-0.597969847, 0.2006055906),
                new Vector(-0.1869409006, -0.6587161669),
                new Vector(-0.5738898892, 0.5738898892),
                new Vector(0, -0.8982259062),
                new Vector(0, 1.1540932262),
                new Vector(-0.3622592503, 1.0041518187),
                new Vector(0.3288626364, 1.1540069845),
                new Vector(1.5125642304, 0),
                new Vector(1.0700903068, 1.0700903068),
                new Vector(1.4672289311, -0.2617441731),
                new Vector(1.3006136322, 0.9425240155),
                new Vector(1.4198116217, -1.4198116217),
                new Vector(1.3161490341, -1.6436993531),
                new Vector(1.6806865023, -3.2067590393),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                3, 23,
                23, 22,
                22, 24,
                24, 2,
                24, 26,
                26, 28,
                28, 1,
                28, 25,
                25, 27,
                27, 0,
                27, 29,
                29, 30,
                30, 31,
                31, 7,
                31, 6,
                30, 21,
                19, 21,
                5, 19,
                17, 19,
                16, 17,
                16, 18,
                4, 18, 
                18, 20,
                20, 23,
                25, 8,
                29, 9,
                21, 10,
                17, 11,
                16, 12,
                20, 13,
                22, 14,
                26, 15,
            };

            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void LetYourFingersDoTheWalking()
        {
            var radiiOut = new string[] {
                "0x3F926CB451E214F6",
                "0x3F9FB9824CB40660",
                "0x3F9060E3665F5248",
                "0x3F9166CBDC20B39E",
                "0x3FB5BE22C8DFA3AF",
                "0x3FBA9A32F836320C",
                "0x3FA80C04D4650DE9",
                "0x3FA80C04D4650DE9",
                "0x3FA3F462FD5F888C",
                "0x3F8892831EB399D7",
                "0x3FB26AEF4A2B2754",
                "0x3F926CB451E214F6",
                "0x3FB0A0987C18BCFC",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0034952289, -0.0094914245),
                new Vector(-0.0036085579, -0.0095149852),
                new Vector(0.0070085571, -0.0102554888),
                new Vector(0.0070777041, -0.0102538246),
                new Vector(0.0071214698, 0.0103172301),
                new Vector(0.0082888827, 0.0094012692),
                new Vector(0.001557385, 0.0128262197),
                new Vector(0.0127729886, -0.0008911604),
                new Vector(0.0131613681, 0),
                new Vector(-0.0014719352, 0.0133836081),
                new Vector(-0.0104565078, -0.0092636575),
                new Vector(0.0017320826, -0.0142649837),
                new Vector(0.0136903788, 0.0071852651),
                new Vector(0.0034823423, -0.0152175151),
                new Vector(0.0143121645, 0.0067309793),
                new Vector(-0.0059826498, 0.0157749512),
                new Vector(0.0152824229, -0.0080208343),
                new Vector(-0.023019141, -0.0056737087),
                new Vector(-0.0269683592, -0.0034125024),
                new Vector(-0.0271702031, -0.0029630159),
                new Vector(-0.0271702031, 0.0066968536),
                new Vector(-0.0224774283, 0.0199132638),
                new Vector(-0.0247110206, 0.0166741491),
                new Vector(-0.0247526881, 0.0199227098),
                new Vector(-0.0425090076, 0.053052962),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                26, 9,
                27, 26,
                27, 17,
                28, 11,
                29, 15,
                29, 28,
                30, 24,
                31, 2,
                31, 30,
                32, 23,
                32, 30,
                33, 0,
                34, 13,
                34, 33,
                35, 32,
                35, 3,
                36, 27,
                36, 18,
                37, 16,
                37, 26,
                38, 31,
                38, 25,
                39, 10,
                39, 28,
                39, 37,
                40, 34,
                40, 1,
                40, 38,
                41, 22,
                41, 35,
                42, 14,
                42, 29,
                42, 12,
                42, 33,
                43, 36,
                43, 19,
                44, 8,
                44, 43,
                45, 7,
                45, 44,
                46, 20,
                46, 45,
                47, 21,
                47, 41,
                48, 6,
                48, 46,
                49, 48,
                49, 47,
                50, 4,
                50, 5,
                50, 49,
            };

            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            StraightSkeleton straightSkeleton = null;
            Exception exc = null;
            try
            {
                straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            }
            catch (Exception exception)
            {
                exc = exception;
            }
            finally
            {
                CheckSimilarity(straightSkeleton,
                    vertices,
                    expectedStraightSkeleton_AdditionalVerts,
                    expectedStraightSkeleton_AdditionalEdges);

                if (exc != null)
                {
                    throw new Exception("", exc);
                }
            }
        }

        public void LumpyCrownOnItsSide()
        {
            var radiiOut = new string[] {
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                "0x3F8CAA24F5B91F34",
                "0x3F8A9E540A365C85",
                "0x3F93729CC7A3764C",
                "0x3F8A9E540A365C85",
                "0x3F8CAA24F5B91F34",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
                ".01",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(-0.0089645241, 0.00148057450),
                new Vector(-0.0076450175, -0.0050348462),
                new Vector(-0.0073918916, -0.0047999360),
                new Vector(-0.0094584349, 0.00081121120),
                new Vector(-0.0086484479, -0.0039312019),
                new Vector(-0.0084088121, -0.0044083560),
                new Vector(-0.0094928555, 0.00036836600),
                new Vector(-0.0088126861, -0.0035698861),
                new Vector(-0.0095082452, -0.0000282276),
                new Vector(-0.0097873117, -0.0003797923),
                new Vector(-0.0092039864, -0.0033499771),
                new Vector(-0.0079488166, 0.00092575410),
                new Vector(-0.0102408484, -0.0020112371),
                new Vector(-0.0102262526, -0.0020083705),
                new Vector(-0.0100866938, -0.0028078231),
                new Vector(-0.0103994126, -0.0012155170),
                new Vector(-0.0105418957, -0.0014267764),
                new Vector(-0.0102984921, -0.0026661423),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                20, 11,
                21, 12,
                22, 21,
                22, 10,
                23, 20,
                23, 1,
                24, 13,
                25, 9,
                25, 21,
                25, 24,
                26, 19,
                23, 26,
                27, 8,
                27, 24,
                28, 26,
                28, 2,
                29, 18,
                29, 28,
                30, 27,
                30, 14,
                31, 0,
                31, 20,
                31, 22,
                32, 4,
                32, 5,
                32, 6,
                33, 32,
                33, 16,
                34, 30,
                34, 15,
                35, 17,
                35, 29,
                36, 3,
                36, 33,
                36, 35,
                37, 33,
                37, 7,
                37, 34,
            };

            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            points.RemoveRange(1, 38);
            holePoints.RemoveRange(1, 38);

            points.RemoveRange(10, 33);
            holePoints.RemoveRange(10, 33);

            holePoints.RemoveAt(0);
            points.Add(new Vector(-.007, points[9].Y*1.1));
            points[0] = new Vector(-0.007, points[1].Y*2);

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void SpkeyBlob()
        {
            var radiiOut = new string[] {
                "0x3FB5FF9CE64FFC05",
                "0x3FAEB26BD1CE069F",
                "0x3FAFB854478F67F6",
                "0x3FB0A0987C18BCFC",
                "0x3FB229752CBACEFE",
                "0x3FB57CA8AB6F4B59",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FB952D06504785F",
                "0x3FB5FF9CE64FFC05",
                "0x3FAEB26BD1CE069F",
                "0x3FAFB854478F67F6",
                "0x3FB0A0987C18BCFC",
                "0x3FB229752CBACEFE",
                "0x3FB57CA8AB6F4B59",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FB952D06504785F",
                "0x3FB5FF9CE64FFC05",
                "0x3FAEB26BD1CE069F",
                "0x3FAFB854478F67F6",
                "0x3FB0A0987C18BCFC",
                "0x3FB229752CBACEFE",
                "0x3FB57CA8AB6F4B59",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FB952D06504785F",
                "0x3FB5FF9CE64FFC05",
                "0x3FAEB26BD1CE069F",
                "0x3FAFB854478F67F6",
                "0x3FB0A0987C18BCFC",
                "0x3FB229752CBACEFE",
                "0x3FB57CA8AB6F4B59",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FB952D06504785F",
                "0x3FB5FF9CE64FFC05",
                "0x3FAEB26BD1CE069F",
                "0x3FAFB854478F67F6",
                "0x3FB0A0987C18BCFC",
                "0x3FB229752CBACEFE",
                "0x3FB57CA8AB6F4B59",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FBBA01B6DF79363",
                "0x3FB57CA8AB6F4B59",
                "0x3FB229752CBACEFE",
                "0x3FB0A0987C18BCFC",
                "0x3FAFB854478F67F6",
                "0x3FAEB26BD1CE069F",
                "0x3FB5FF9CE64FFC05",
                "0x3FB952D06504785F",
                "0x3FBADBAD15A68A62",
                "0x3FBBA01B6DF79363",
                "0x3FBADBAD15A68A62",
                "0x3FBBA01B6DF79363",
                "0x3FB57CA8AB6F4B59",
                "0x3FB229752CBACEFE",
                "0x3FB0A0987C18BCFC",
                "0x3FAFB854478F67F6",
                "0x3FAEB26BD1CE069F",
                "0x3FB5FF9CE64FFC05",
                "0x3FB952D06504785F",
                "0x3FBADBAD15A68A62",
                "0x3FBBA01B6DF79363",
                "0x3FAFB854478F67F6",
                "0x3FAEB26BD1CE069F",
                "0x3FB5FF9CE64FFC05",
                "0x3FB952D06504785F",
                "0x3FBBA01B6DF79363",
                "0x3FB57CA8AB6F4B59",
                "0x3FB229752CBACEFE",
                "0x3FB0A0987C18BCFC",
                "0x3FAFB854478F67F6",
                "0x3FAEB26BD1CE069F",
                "0x3FB5FF9CE64FFC05",
                "0x3FB952D06504785F",
                "0x3FB0A0987C18BCFC",
                "0x3FAFB854478F67F6",
                "0x3FAEB26BD1CE069F",
                "0x3FB5FF9CE64FFC05",
                "0x3FB952D06504785F",
                "0x3FBADBAD15A68A62",
                "0x3FBBA01B6DF79363",
                "0x3FB57CA8AB6F4B59",
                "0x3FB229752CBACEFE",
                "0x3FB0A0987C18BCFC",
                "0x3FAFB854478F67F6",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0534147345, -0.0003065739),
                new Vector(-0.033973453, -0.0038677912),
                new Vector(0.0738534467, -0.0355763006),
                new Vector(0.0164763183, -0.0182961456),
                new Vector(0.0504776989, -0.0188333195),
                new Vector(0.0354505292, -0.0104092145),
                new Vector(0.0442129194, -0.0129820845),
                new Vector(0.0308378237, -0.0090548020),
                new Vector(0.0303261469, -0.0109267776),
                new Vector(0.0318466215, -0.0058435309),
                new Vector(0.032613807, -0.00233258550),
                new Vector(0.0330368957, 0),
                new Vector(0.0333824454, 0.00238755960),
                new Vector(0.0336481912, 0.00483787950),
                new Vector(0.0338308995, 0.00735946170),
                new Vector(0.0048871802, 0.04151492240),
                new Vector(0.0339262641, 0.00996164990),
                new Vector(-0.0368167761, 0.0149656658),
                new Vector(0.0339351818, 0.01953472550),
                new Vector(0.0325473093, 0.02499357260),
                new Vector(0.0324207793, 0.02710027510),
                new Vector(0.0189485820, 0.03994208200),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                23, 11,
                23, 0,
                24, 16,
                25, 8,
                25, 9,
                26, 15,
                26, 24,
                27, 25,
                27, 10,
                28, 1 ,
                28, 7 ,
                29, 27,
                29, 23,
                29, 28,
                30, 28,
                31, 26,
                31, 6 ,
                31, 30,
                32, 14,
                32, 30,
                33, 13,
                33, 32,
                34, 12,
                34, 33,
                35, 22,
                35, 34,
                36, 21,
                36, 35,
                37, 20,
                37, 36,
                38, 17,
                39, 19,
                39, 37,
                40, 5 ,
                40, 24,
                40, 38,
                41, 18,
                41, 39,
                42, 41,
                42, 2 ,
                43, 42,
                43, 3 ,
                44, 4 ,
                44, 38,
                44, 43,
            };
            
            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            points.RemoveRange(19, 24);
            holePoints.RemoveRange(19, 24);

            points.RemoveRange(20, 32);
            holePoints.RemoveRange(20, 32);

            points.RemoveRange(6, 12);
            holePoints.RemoveRange(6, 12);

            points.RemoveRange(15, 3);
            holePoints.RemoveRange(15, 3);

            points.RemoveRange(8, 2);
            holePoints.RemoveRange(8, 2);

            points.RemoveRange(11, 1);
            holePoints.RemoveRange(11, 1);

            holePoints.RemoveRange(8, 3);

            points.RemoveRange(3, 2);

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
            
            CheckSimilarity(straightSkeleton,
                vertices,
                expectedStraightSkeleton_AdditionalVerts,
                expectedStraightSkeleton_AdditionalEdges);
        }

        public void Spoiler()
        {
            var radiiOut = new string[] {
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8A9E540A365C85",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8CAA24F5B91F34",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8CAA24F5B91F34",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8A9E540A365C85",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F847AE147AE147B",
                "0x3F8686B23330D729",
                "0x3F8686B23330D729",
            }.Select(x => Scalar.ParseFromUnknownFormat(x)).ToArray();

            var expectedStraightSkeleton_AdditionalVerts = new Vector[]
            {
                new Vector(0.0076529808, 0.0050869983),
                new Vector(0.0086293056, 0.0032551722),
                new Vector(-0.0026406893, -0.0088367313),
                new Vector(-0.0054549337, -0.0075539918),
                new Vector(0.0087541644, 0.0040091394),
                new Vector(-0.0033840178, -0.0090142674),
                new Vector(0.0087421815, 0.0053214911),
                new Vector(-0.0038037512, -0.0090329539),
                new Vector(0.0087433074, 0.0044291482),
                new Vector(-0.0055382059, -0.0084549352),
                new Vector(0.0087097154, 0.0048901861),
                new Vector(-0.0047266723, -0.0088118992),
                new Vector(-0.0053569301, -0.0084347647),
                new Vector(0.0086847961, 0.0049341374),
                new Vector(-0.0042660099, -0.0090318449),
            };

            var expectedStraightSkeleton_AdditionalEdges = new int[]
            {
                16, 14,
                17, 9 ,
                18, 10,
                18, 17,
                19, 13,
                19, 16,
                20, 17,
                20, 0 ,
                21, 8 ,
                21, 18,
                22, 2 ,
                22, 3 ,
                23, 21,
                23, 11,
                24, 15,
                24, 20,
                25, 4 ,
                25, 5 ,
                26, 24,
                26, 1 ,
                27, 12,
                27, 6 ,
                28, 19,
                28, 25,
                28, 27,
                29, 22,
                29, 16,
                29, 26,
                30, 7 ,
                30, 23,
                30, 27,
            };
            
            Scalar cumulativeAngle = 0;
            List<Vector> points = new List<Vector>();
            List<Vector> holePoints = new List<Vector>();

            for (int i = 0; i < radiiOut.Length; ++i)
            {
                points.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, radiiOut[i]));
                holePoints.Add(Vector.BuildFromAngleMagnitude(cumulativeAngle, 0.0090000000000000011));
                cumulativeAngle += Math.PI * 2.0 / radiiOut.Length;
            }

            points.RemoveRange(10, 30);
            holePoints.RemoveRange(10, 30);

            points.RemoveRange(25, 12);
            holePoints.RemoveRange(25, 12);

            points.RemoveRange(7, 2);
            holePoints.RemoveRange(7, 2);

            points.RemoveRange(0, 4);
            holePoints.RemoveRange(0, 4);

            points.RemoveRange(5, 3);
            holePoints.RemoveRange(5, 3);

            points.RemoveRange(9, 7);
            holePoints.RemoveRange(9, 7);

            holePoints.RemoveRange(3, 2);
            points[4] = (points[4] + 3 * points[5]) / 4;
            points[3] = (points[3] + 3 * points[2]) / 4;

            var vertices = new PerforatedPolygon(new SimplePolygon(points), new[] { new SimplePolygon(holePoints) });

            var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

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