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

namespace Annulus.UnitTests.CSG
{
    public class StraightSkeletonTests : UnitTestSharp.TestFixture
    {
        public class EdgeTests : UnitTestSharp.TestFixture
        {
            //StraightSkeleton.Vertex OriginVertex = new StraightSkeleton.Vertex
            //{
            //    Position = new Azimuth.Vector(0, 0),
            //};

            //StraightSkeleton.Vertex XAxis = new StraightSkeleton.Vertex
            //{
            //    Position = new Azimuth.Vector(7, 0),
            //};

            //StraightSkeleton.Vertex YAxis = new StraightSkeleton.Vertex
            //{
            //    Position = new Azimuth.Vector(0, -3),
            //};

            //StraightSkeleton.Vertex Quad4Vertex = new StraightSkeleton.Vertex
            //{
            //    Position = new Azimuth.Vector(7, -3),
            //};

            //public void CompareTo_DifferentTimes()
            //{
            //    StraightSkeleton.Edge edge1 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };                

            //    var edge2 = new StraightSkeleton.Edge
            //    {
            //        TOI = 7,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };

            //    Check(edge1.CompareTo(edge2) < 0);
            //    Check(edge2.CompareTo(edge1) > 0);
            //}

            //public void CompareTo_DifferentVertex1()
            //{
            //    StraightSkeleton.Edge edge1 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };

            //    var edge2 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = XAxis,
            //        vertex2 = Quad4Vertex,
            //    };

            //    Check(edge1.CompareTo(edge2) < 0);
            //    Check(edge2.CompareTo(edge1) > 0);
            //}

            //public void CompareTo_DifferentVertex2()
            //{
            //    StraightSkeleton.Edge edge1 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };

            //    var edge2 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = XAxis,
            //    };

            //    Check(edge1.CompareTo(edge2) < 0);
            //    Check(edge2.CompareTo(edge1) > 0);
            //}

            //public void CompareTo_Same()
            //{
            //    StraightSkeleton.Edge edge1 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };

            //    var edge2 = new StraightSkeleton.Edge
            //    {
            //        TOI = 0,
            //        vertex1 = OriginVertex,
            //        vertex2 = Quad4Vertex,
            //    };

            //    Check(edge1.CompareTo(edge2) == 0);
            //    Check(edge2.CompareTo(edge1) == 0);
            //}
        }

        public class CalculateAABBTests : UnitTestSharp.TestFixture
        {
            public void Basic()
            {
                var poly = new PerforatedPolygon(new SimplePolygon(new Vector[]
                {
                    new Vector(0, 0),
                    new Vector(1, 0),
                    new Vector(0, -1),
                }));

                var ss = StraightSkeleton.BuildStraightSkeleton(poly);

                var aabb = ss.CalculateAABB();
                var expected = new AABB<Vector>(new Vector(0, -1), new Vector(1, 0));

                CheckEqual(expected, aabb);
            }
        }

        public class StraightSkeletonCtorTests : UnitTestSharp.TestFixture
        {
            public void Basic()
            {
                var vertices = 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(2, -1),
                    new Vector(2, -2),
                    new Vector(-2, -2),
                };

                var additionalVertices = 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 allVertices = Enumerable.Concat<Vector>(vertices, additionalVertices).ToList();

                var edges = new Tuple<int, int>[]
                {
                    Tuple.Create(0, 1),
                    Tuple.Create(1, 2),
                    Tuple.Create(2, 3),
                    Tuple.Create(3, 4),
                    Tuple.Create(4, 5),
                    Tuple.Create(5, 6),
                    Tuple.Create(6, 7),
                    Tuple.Create(7, 3),
                    Tuple.Create(3, 8),
                    Tuple.Create(8, 9),
                    Tuple.Create(9, 10),
                    Tuple.Create(10, 0),
                    Tuple.Create(0, 11),
                    Tuple.Create(5, 11),
                    Tuple.Create(11, 12),
                    Tuple.Create(6, 12),
                    Tuple.Create(10, 12),
                    Tuple.Create(12, 14),
                    Tuple.Create(7, 14),
                    Tuple.Create(14, 18),
                    Tuple.Create(18, 16),
                    Tuple.Create(18, 9),
                    Tuple.Create(16, 8),
                    Tuple.Create(16, 3),
                    Tuple.Create(3, 15),
                    Tuple.Create(2, 15),
                    Tuple.Create(15, 17),
                    Tuple.Create(17, 1),
                    Tuple.Create(17, 13),
                    Tuple.Create(13, 4),
                    Tuple.Create(13, 11),
                };

                var straightSkeleton = new StraightSkeleton(allVertices, edges, vertices.Length, 1);

                CheckEqualCommutative(
                    allVertices.Select(vertex => new StraightSkeleton.ExportVertex { Position = vertex }),
                    straightSkeleton.Vertices);
                
                foreach(var vertex in straightSkeleton.Vertices)
                {
                    CheckGreater(vertex.Edges.Count, 0);
                }
            }
        }

        public class DecomposeTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            private void CheckEqual(IList<SimplePolygon> actualFaces, List<SimplePolygon> expectedFaces)
            {
                CheckEqual(expectedFaces.Count, actualFaces.Count);
                if (expectedFaces.Count == actualFaces.Count)
                {
                    for (int i = 0; i < expectedFaces.Count; ++i)
                    {
                        var oldFailures = this.internals.FailedChecks;
                        CheckEqual(expectedFaces[i].VertexList, actualFaces[i].VertexList);
                        if (oldFailures != this.internals.FailedChecks)
                        {
                            TODO("In sub polygon " + i);
                        }
                    }
                }
            }

            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 centerVertex = new Vector(0.5, Math.Sqrt(3) / 6);

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

                var actualFaces = straightSkeleton.Decompose();

                var expectedFaces = new List<SimplePolygon>
                {
                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[0],
                        vertices.Silhouette.VertexList[1],
                        centerVertex,
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[1],
                        vertices.Silhouette.VertexList[2],
                        centerVertex,
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[2],
                        vertices.Silhouette.VertexList[0],
                        centerVertex,
                    }),
                };

                CheckEqual(actualFaces, expectedFaces);
            }

            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 centerVertex = new Vector(0.5, Math.Sqrt(3) / 6);

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

                var actualFaces = straightSkeleton.Decompose();

                var expectedFaces = new List<SimplePolygon>
                {
                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[0],
                        vertices.Silhouette.VertexList[1],
                        centerVertex,
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[1],
                        vertices.Silhouette.VertexList[2],
                        centerVertex,
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices.Silhouette.VertexList[2],
                        vertices.Silhouette.VertexList[0],
                        centerVertex,
                    }),
                };

                CheckEqual(actualFaces, expectedFaces);
            }

            public void LongArrowFailedOnce()
            {
                var vertices = 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),
                    new Vector(1, 0),
                    new Vector(6, 0),
                    new Vector(6.4641016152, -0.4641016152),
                    new Vector(6.7320508076, 0),
                };

                var edges = new Tuple<int, int>[]
                {
                    Tuple.Create( 0, 1 ),
                    Tuple.Create( 1, 2 ),
                    Tuple.Create( 2, 3 ),
                    Tuple.Create( 3, 4 ),
                    Tuple.Create( 4, 5 ),
                    Tuple.Create( 5, 6 ),
                    Tuple.Create( 6, 0 ),
                    Tuple.Create( 7, 0 ),
                    Tuple.Create( 7, 1 ),
                    Tuple.Create( 8, 6 ),
                    Tuple.Create( 8, 7 ),
                    Tuple.Create( 9, 5 ),
                    Tuple.Create( 9, 8 ),
                    Tuple.Create( 8, 2 ),
                    Tuple.Create( 10, 3 ),
                    Tuple.Create( 10, 4 ),
                    Tuple.Create( 10, 9 ),
                };

                var straightSkeleton = new StraightSkeleton(vertices, edges, boundaryEdgeCount: 7, winding: 1);
                var actualFaces = straightSkeleton.Decompose();

                var expectedFaces = new List<SimplePolygon>
                {
                    new SimplePolygon(new Vector[] 
                    {
                        vertices[0],
                        vertices[1],
                        vertices[7],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[1],
                        vertices[2],
                        vertices[8],
                        vertices[7],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[2],
                        vertices[3],
                        vertices[10],
                        vertices[9],
                        vertices[8],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[3],
                        vertices[4],
                        vertices[10],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[4],
                        vertices[5],
                        vertices[9],
                        vertices[10],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[5],
                        vertices[6],
                        vertices[8],
                        vertices[9],
                    }),

                    new SimplePolygon(new Vector[] 
                    {
                        vertices[6],
                        vertices[0],
                        vertices[7],
                        vertices[8],
                    }),
                };

                CheckEqual(actualFaces, expectedFaces);
            }

            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 verts = vertices.Silhouette.VertexList.Concat(expectedStraightSkeleton_AdditionalVerts).ToList();

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

                var actualFaces = straightSkeleton.Decompose();

                var expectedFaces = new List<SimplePolygon>
                {
                    new SimplePolygon(new Vector[]
                    {
                        verts[0],
                        verts[1],
                        verts[17],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[1],
                        verts[2],
                        verts[15],
                        verts[17],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[2],
                        verts[3],
                        verts[13],
                        verts[15],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[3],
                        verts[4],
                        verts[12],
                        verts[13],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[4],
                        verts[5],
                        verts[14],
                        verts[12],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[5],
                        verts[6],
                        verts[16],
                        verts[14],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[6],
                        verts[7],
                        verts[16],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[7],
                        verts[8],
                        verts[14],
                        verts[16],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[8],
                        verts[9],
                        verts[12],
                        verts[14],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[9],
                        verts[10],
                        verts[13],
                        verts[12],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[10],
                        verts[11],
                        verts[15],
                        verts[13],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[11],
                        verts[0],
                        verts[17],
                        verts[15],
                    }),
                };

                CheckEqual(actualFaces, expectedFaces);
            }

            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 verts = vertices.Silhouette.VertexList.Concat(expectedStraightSkeleton_AdditionalVerts).ToList();

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);

                var actualFaces = straightSkeleton.Decompose();

                var expectedFaces = new List<SimplePolygon>
                {
                    new SimplePolygon(new Vector[]
                    {
                        verts[0],
                        verts[1],
                        verts[15],
                        verts[17],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[1],
                        verts[2],
                        verts[13],
                        verts[15],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[2],
                        verts[3],
                        verts[12],
                        verts[13],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[3],
                        verts[4],
                        verts[14],
                        verts[12],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[4],
                        verts[5],
                        verts[16],
                        verts[14],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[5],
                        verts[6],
                        verts[16],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[6],
                        verts[7],
                        verts[14],
                        verts[16],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[7],
                        verts[8],
                        verts[12],
                        verts[14],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[8],
                        verts[9],
                        verts[13],
                        verts[12],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[9],
                        verts[10],
                        verts[15],
                        verts[13],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[10],
                        verts[11],
                        verts[17],
                        verts[15],
                    }),

                    new SimplePolygon(new Vector[]
                    {
                        verts[11],
                        verts[0],
                        verts[17],
                    }),
                };

                CheckEqual(actualFaces, expectedFaces);
            }

            public void BigCloverShape()
            {
                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 verts = vertices.Silhouette.VertexList.Concat(expectedStraightSkeleton_AdditionalVerts).ToList();

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
                var actualFaces = straightSkeleton.Decompose();

                var expectedFacesIndices = new int[]
                {
                    0, 1, 167, 130, 117, 
                    1, 2, 177, 167, 
                    2, 3, 187, 177, 
                    3, 4, 197, 187, 
                    4, 5, 207, 197, 
                    5, 6, 214, 207, 
                    6, 7, 202, 214, 
                    7, 8, 193, 202, 
                    8, 9, 182, 193, 
                    9, 10, 172, 182, 
                    10, 11, 162, 172, 
                    11, 12, 154, 162, 
                    12, 13, 137, 154, 
                    13, 14, 123, 137, 
                    14, 15, 123, 
                    15, 16, 114, 130, 167, 177, 187, 197, 207, 214, 202, 193, 182, 172, 162, 154, 137, 123, 
                    16, 17, 120, 111, 115, 114, 
                    17, 18, 135, 120, 
                    18, 19, 149, 135, 
                    19, 20, 159, 149, 
                    20, 21, 168, 159, 
                    21, 22, 178, 168, 
                    22, 23, 189, 178, 
                    23, 24, 199, 189, 
                    24, 25, 208, 199, 
                    25, 26, 213, 208, 
                    26, 27, 203, 213, 
                    27, 28, 192, 203, 
                    28, 29, 183, 192, 
                    29, 30, 173, 183, 
                    30, 31, 163, 173, 
                    31, 32, 152, 163, 
                    32, 33, 141, 152, 
                    33, 34, 124, 141, 
                    34, 35, 124, 
                    35, 36, 111, 120, 135, 149, 159, 168, 178, 189, 199, 208, 213, 203, 192, 183, 173, 163, 152, 141, 124, 
                    36, 37, 119, 112, 115, 111, 
                    37, 38, 133, 119, 
                    38, 39, 148, 133, 
                    39, 40, 157, 148, 
                    40, 41, 166, 157, 
                    41, 42, 176, 166, 
                    42, 43, 186, 176, 
                    43, 44, 196, 186, 
                    44, 45, 206, 196, 
                    45, 46, 211, 206, 
                    46, 47, 201, 211, 
                    47, 48, 191, 201, 
                    48, 49, 181, 191, 
                    49, 50, 171, 181, 
                    50, 51, 161, 171, 
                    51, 52, 153, 161, 
                    52, 53, 139, 153, 
                    53, 54, 125, 139, 
                    54, 55, 125, 
                    55, 56, 112, 119, 133, 148, 157, 166, 176, 186, 196, 206, 211, 201, 191, 181, 171, 161, 153, 139, 125, 
                    56, 57, 121, 113, 115, 112, 
                    57, 58, 134, 121, 
                    58, 59, 150, 134, 
                    59, 60, 158, 150, 
                    60, 61, 169, 158, 
                    61, 62, 179, 169, 
                    62, 63, 188, 179, 
                    63, 64, 198, 188, 
                    64, 65, 209, 198, 
                    65, 66, 212, 209, 
                    66, 67, 204, 212, 
                    67, 68, 194, 204, 
                    68, 69, 184, 194, 
                    69, 70, 174, 184, 
                    70, 71, 165, 174, 
                    71, 72, 156, 165, 
                    72, 73, 138, 156, 
                    73, 74, 127, 138, 
                    74, 75, 127, 
                    75, 76, 113, 121, 134, 150, 158, 169, 179, 188, 198, 209, 212, 204, 194, 184, 174, 165, 156, 138, 127, 
                    76, 77, 122, 110, 115, 113, 
                    77, 78, 136, 122, 
                    78, 79, 151, 136, 
                    79, 80, 160, 151, 
                    80, 81, 170, 160, 
                    81, 82, 180, 170, 
                    82, 83, 190, 180, 
                    83, 84, 200, 190, 
                    84, 85, 210, 200, 
                    85, 86, 215, 210, 
                    86, 87, 205, 215, 
                    87, 88, 195, 205, 
                    88, 89, 185, 195, 
                    89, 90, 175, 185, 
                    90, 91, 164, 175, 
                    91, 92, 155, 164, 
                    92, 93, 140, 155, 
                    93, 94, 126, 140, 
                    94, 95, 126, 
                    95, 96, 110, 122, 136, 151, 160, 170, 180, 190, 200, 210, 215, 205, 195, 185, 175, 164, 155, 140, 126, 
                    96, 97, 118, 117, 130, 114, 115, 110, 
                    97, 98, 129, 118, 
                    98, 99, 132, 129, 
                    99, 100, 143, 132, 
                    100, 101, 145, 143, 
                    101, 102, 147, 145, 
                    102, 103, 146, 147, 
                    103, 104, 144, 146, 
                    104, 105, 142, 144, 
                    105, 106, 131, 142, 
                    106, 107, 128, 131, 
                    107, 108, 116, 128, 
                    108, 109, 116, 
                    109, 0, 117, 118, 129, 132, 143, 145, 147, 146, 144, 142, 131, 128, 116, 
                };

                var expectedFaces = new List<SimplePolygon>();
                for (int i = 0; i < expectedFacesIndices.Length; )
                {
                    var vertexList = new List<Vector>();
                    vertexList.Add(verts[expectedFacesIndices[i]]);
                    ++i;
                    do
                    {
                        vertexList.Add(verts[expectedFacesIndices[i]]);
                        ++i;
                    } while (i < expectedFacesIndices.Length && expectedFacesIndices[i] >= vertices.Silhouette.Count);

                    expectedFaces.Add(new SimplePolygon(vertexList));
                }
                
                CheckEqual(actualFaces, expectedFaces);
            }

            public void DegenerateCloverShape()
            {
                var vertices = new List<Vector>(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 poly = new SimplePolygon(vertices);

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(new PerforatedPolygon(poly));
                var actualFaces = straightSkeleton.Decompose();

                foreach (var face in actualFaces)
                {
                    var vertexIndices = new List<int>();

                    foreach(var vertex in face.VertexList)
                    {
                        vertexIndices.Add(straightSkeleton.Vertices.FindIndex(
                            x => x.Position.X.Value.Equals(vertex.X) && x.Position.Y.Equals(vertex.Y)));
                    }

                    if (!face.ValidateIsSimplePolygon())
                    {
                        throw new Exception("Non simple face found.");
                    }
                }
            }

            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[]
                {
                
                };

                var expectedStraightSkeleton_AdditionalEdges = new int[]
                {
                
                };

                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) });

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
                var actualFaces = straightSkeleton.Decompose();

                foreach (var face in actualFaces)
                {
                    var vertexIndices = new List<int>();

                    foreach (var vertex in face.VertexList)
                    {
                        vertexIndices.Add(straightSkeleton.Vertices.FindIndex(
                            x => x.Position.X.Value.Equals(vertex.X) && x.Position.Y.Equals(vertex.Y)));
                    }

                    if (!face.ValidateIsSimplePolygon())
                    {
                        throw new Exception("Non simple face found.");
                    }
                }
            }

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

                var expectedStraightSkeleton_AdditionalVerts = new Vector[]
                {
                
                };

                var expectedStraightSkeleton_AdditionalEdges = new int[]
                {
                
                };

                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) });

                var straightSkeleton = StraightSkeleton.BuildStraightSkeleton(vertices);
                var actualFaces = straightSkeleton.Decompose();

                foreach (var face in actualFaces)
                {
                    var vertexIndices = new List<int>();

                    foreach (var vertex in face.VertexList)
                    {
                        vertexIndices.Add(straightSkeleton.Vertices.FindIndex(
                            x => x.Position.X.Value.Equals(vertex.X) && x.Position.Y.Equals(vertex.Y)));
                    }

                    if (!face.ValidateIsSimplePolygon())
                    {
                        throw new Exception("Non simple face found.");
                    }
                }
            }
        }
    }
}