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

namespace Annulus.UnitTests.CSG
{
    public class TriangulationTests : UnitTestSharp.TestFixture
    {
        public class GlomTests : UnitTestSharp.TestFixture
        {
            public void Triangle()
            {
                var verts = new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                };

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(
                    new PerforatedPolygon(new SimplePolygon(verts)), out addedChannels);

                CheckEqual(verts.Length, glomed.Count);
                for (int i = 0; i < Math.Min(verts.Length, glomed.Count); ++i)
                {
                    CheckEqual(verts[i], glomed[i]);
                }
            }

            public void Donut_1()
            {
                var silhouette = new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                };

                var hole = new Vector[]
                {
                    new Vector(-.6, .6),
                    new Vector(-.5,-.5),
                    new Vector( .5,-.5),
                    new Vector( .5, .5),
                };

                var expected = new Vector[]
                {
                    new Vector(-1, 1),

                    new Vector(-.6, .6),
                    new Vector( .5, .5),                    
                    new Vector( .5,-.5),
                    new Vector(-.5,-.5),
                    
                    new Vector(-.6, .6),
                    new Vector(-1, 1),

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

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[] { new SimplePolygon(hole), }
                ), out addedChannels);

                CheckEqual(expected.Length, glomed.Count);
                for (int i = 0; i < Math.Min(expected.Length, glomed.Count); ++i)
                {
                    CheckEqual(expected[i], glomed[i]);
                }
            }

            public void Donut_2()
            {
                var silhouette = new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                };

                var hole = new Vector[]
                {
                    new Vector(-.5,-.5),
                    new Vector( .5,-.5),
                    new Vector( .5, .5),
                    new Vector(-.6, .6),                    
                };

                var expected = new Vector[]
                {
                    new Vector(-1, 1),

                    new Vector(-.6, .6),
                    new Vector( .5, .5),
                    new Vector( .5,-.5),
                    new Vector(-.5,-.5),
                    
                    new Vector(-.6, .6),
                    new Vector(-1, 1),

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

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[] { new SimplePolygon(hole), }
                ), out addedChannels);

                CheckEqual(expected, glomed);
            }

            public void Donut_Winding()
            {
                var silhouette = new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                };

                var hole = new Vector[]
                {
                    new Vector(-.6, .6),                    
                    new Vector( .5, .5),
                    new Vector( .5,-.5),                    
                    new Vector(-.5,-.5),
                };

                var expected = new Vector[]
                {
                    new Vector(-1, 1),

                    new Vector(-.6, .6),
                    new Vector( .5, .5),
                    new Vector( .5,-.5),
                    new Vector(-.5,-.5),
                    
                    new Vector(-.6, .6),
                    new Vector(-1, 1),

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

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[] { new SimplePolygon(hole), }
                ), out addedChannels);

                CheckEqual(expected.Length, glomed.Count);
                for (int i = 0; i < Math.Min(expected.Length, glomed.Count); ++i)
                {
                    CheckEqual(expected[i], glomed[i]);
                }
            }

            public void Donut_Silhouette_Winding()
            {
                var silhouette = new Vector[]
                {
                    new Vector( 1, 1),
                    new Vector( 1,-1),
                    new Vector(-1,-1),                    
                    new Vector(-1, 1),
                };

                var hole = new Vector[]
                {
                    new Vector(-.6, .6),                    
                    new Vector( .5, .5),
                    new Vector( .5,-.5),                    
                    new Vector(-.5,-.5),
                };

                var expected = new Vector[]
                {
                    new Vector( 1, 1),
                    new Vector( 1,-1),

                    new Vector(-1,-1),
                    new Vector(-1, 1),
                    new Vector(-.6, .6),
                    new Vector(-.5,-.5),
                    new Vector( .5,-.5),
                    
                    new Vector( .5, .5),

                    new Vector(-.6, .6),
                    new Vector(-1, 1),
                    
                };

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[] { new SimplePolygon(hole), }
                ), out addedChannels);

                CheckEqual(expected.Length, glomed.Count);
                for (int i = 0; i < Math.Min(expected.Length, glomed.Count); ++i)
                {
                    CheckEqual(expected[i], glomed[i]);
                }
            }

            public void Window()
            {
                var silhouette = new Vector[]
                {
                    new Vector( 2, 2),
                    new Vector( 2,-2),
                    new Vector(-2,-2),                    
                    new Vector(-2, 2),
                };

                var holeNE = new Vector[]
                {
                    new Vector( .6,1.6),
                    new Vector(1.5,1.5),
                    new Vector(1.5, .5),
                    new Vector( .5, .5),
                };

                var holeNW = new Vector[]
                {
                    new Vector(-.6,1.6),
                    new Vector(-1.5,1.5),
                    new Vector(-1.5, .5),
                    new Vector(-.5, .5),
                };

                var holeSE = new Vector[]
                {
                    new Vector( .6,-1.6),
                    new Vector(1.5,-1.5),
                    new Vector(1.5,-.5),
                    new Vector( .5,-.5),
                };

                var holeSW = new Vector[]
                {
                    new Vector(-.6,-1.6),
                    new Vector(-1.5,-1.5),
                    new Vector(-1.5,-.5),
                    new Vector(-.5,-.5),
                };

                var expected = new Vector[]
                {
                    new Vector(2, 2),	
                    new Vector(1.5, 1.5),	
                    new Vector(0.6, 1.6),	
                    new Vector(0.5, 0.5),	
                    new Vector(1.5, 0.5),	
                    new Vector(1.5, 1.5),	
                    new Vector(2, 2),	
                    new Vector(2, -2),	
                    new Vector(1.5, -1.5),	
                    new Vector(1.5, -0.5),	
                    new Vector(0.5, -0.5),	
                    new Vector(0.6, -1.6),	
                    new Vector(1.5, -1.5),	
                    new Vector(2, -2),	
                    new Vector(-2, -2),	
                    new Vector(-1.5, -1.5),	
                    new Vector(-0.6, -1.6),	
                    new Vector(-0.5, -0.5),	
                    new Vector(-1.5, -0.5),	
                    new Vector(-1.5, -1.5),	
                    new Vector(-2, -2),	
                    new Vector(-2, 2),	
                    new Vector(-1.5, 1.5),	
                    new Vector(-1.5, 0.5),	
                    new Vector(-0.5, 0.5),	
                    new Vector(-0.6, 1.6),	
                    new Vector(-1.5, 1.5),
                    new Vector(-2, 2),
                };

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[]
                    { 
                        new SimplePolygon(holeNW), 
                        new SimplePolygon(holeSW), 
                        new SimplePolygon(holeNE), 
                        new SimplePolygon(holeSE), 
                    }
                ), out addedChannels);

                CheckEqual(expected, glomed);
            }

            public void InARow()
            {
                var silhouette = new Vector[]
                {
                    new Vector( 0, 2),
                    new Vector( 0,-2),
                    new Vector( 7,-2),                    
                    new Vector( 7, 2),
                };

                var hole1 = new Vector[]
                {
                    new Vector( 2, 1),
                    new Vector( 2,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                };

                var hole2 = new Vector[]
                {
                    new Vector( 4, 1),
                    new Vector( 4,-1),
                    new Vector( 3,-1),
                    new Vector( 3, 1),
                };

                var hole3 = new Vector[]
                {
                    new Vector( 6, 1),
                    new Vector( 6,-1),
                    new Vector( 5,-1),
                    new Vector( 5, 1),
                };

                var expected = new Vector[]
                {
                    new Vector(0, 2),
                    new Vector(1, 1),
                    new Vector(2, 1),
                    new Vector(3, 1),
                    new Vector(4, 1),
                    new Vector(5, 1),
                    new Vector(6, 1),
                    new Vector(6, -1),
                    new Vector(5, -1),
                    new Vector(5, 1),
                    new Vector(4, 1),
                    new Vector(4, -1),
                    new Vector(3, -1),
                    new Vector(3, 1),
                    new Vector(2, 1),
                    new Vector(2, -1),
                    new Vector(1, -1),
                    new Vector(1, 1),
                    new Vector(0, 2),
                    new Vector(0, -2),
                    new Vector(7, -2),
                    new Vector(7, 2),
                };

                HashSet<int> addedChannels;
                var glomed = Annulus.CSG.Triangulation.GlomPolygon(new PerforatedPolygon(
                    new SimplePolygon(silhouette),
                    new SimplePolygon[]
                    { 
                        new SimplePolygon(hole1), 
                        new SimplePolygon(hole2), 
                        new SimplePolygon(hole3),
                    }
                ), out addedChannels);

                CheckEqual(expected.Length, glomed.Count);
                for (int i = 0; i < Math.Min(expected.Length, glomed.Count); ++i)
                {
                    CheckEqual(expected[i], glomed[i]);
                }
            }
        }

        public class TriangulatorTests: UnitTestSharp.TestFixture
        {
            public void Tris()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(1,1),
                    new Vector(0,0),
                    new Vector(1,0),
                });

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(new PerforatedPolygon(silhouette), out vertices, out tris);

                CheckEqual(1, tris.Count);
                CheckEqual(3, vertices.Count);

                if (tris.Count == 1)
                {
                    CheckEqual(new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 0, 1, 2 },
                    }, tris[0]);
                }
            }

            public void Quad()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                });

                var expected = new Triangulation.Triangle[]
                {
                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 0, 1, 2},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 3, 0},
                    },
                };

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(new PerforatedPolygon(silhouette), out vertices, out tris);

                CheckEqual(2, tris.Count);
                if (tris.Count == 2)
                {
                    CheckEqual(expected[0], tris[0]);
                    CheckEqual(expected[1], tris[1]);
                    Check(tris[0].SignedArea * silhouette.SignedArea >= 0);
                    Check(tris[1].SignedArea * silhouette.SignedArea >= 0);
                }
            }

            public void Empty()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    
                });

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(new PerforatedPolygon(silhouette), out vertices, out tris);

                CheckEqual(0, tris.Count);
            }

            public void One()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(1,1),
                });

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                var poly = new PerforatedPolygon(silhouette);
                Triangulation.Triangulate(poly, out vertices, out tris);

                CheckEqual(0, tris.Count);
                CheckEqual(0, vertices.Count);
            }

            public void Two()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(0,0),
                    new Vector(1,1),
                });

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(new PerforatedPolygon(silhouette), out vertices, out tris);

                CheckEqual(0, tris.Count);
                CheckEqual(0, vertices.Count);
            }

            public void Donut()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-1,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                });

                var hole = new SimplePolygon(new Vector[]
                {
                    new Vector(-.6, .6),
                    new Vector(-.5,-.5),
                    new Vector( .5,-.5),
                    new Vector( .5, .5),
                });

                var expectedVerts = new Polygon(new Vector[]
                {
                    new Vector(-1, 1),
                    new Vector(-0.6, 0.6),
                    new Vector(0.5, 0.5),
                    new Vector(0.5, -0.5),
                    new Vector(-0.5, -0.5),
                    new Vector(-0.6, 0.6),
                    new Vector(-1, 1),
                    new Vector(-1, -1),
                    new Vector(1, -1),
                    new Vector(1, 1),
                });

                var expected = new Triangulation.Triangle[]
                {
                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 1, 2, 6},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 4, 5, 0},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 6, 7, 4, },
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 7, 8, 4},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 9, 0, 2},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 2, 3, 9},
                    },                

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 3, 4, 8},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = expectedVerts,
                        indices = new int[] { 8, 9, 3},
                    },
                };

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(
                    new PerforatedPolygon(silhouette, new SimplePolygon[] { hole }), out vertices, out tris);

                CheckEqual(expected, tris);
            }

            public void InARow()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector( 0, 2),
                    new Vector( 0,-2),
                    new Vector( 7,-2),                    
                    new Vector( 7, 2),
                });

                var hole1 = new SimplePolygon(new Vector[]
                {
                    new Vector( 2, 1),
                    new Vector( 2,-1),
                    new Vector( 1,-1),
                    new Vector( 1, 1),
                });

                var hole2 = new SimplePolygon(new Vector[]
                {
                    new Vector( 4, 1),
                    new Vector( 4,-1),
                    new Vector( 3,-1),
                    new Vector( 3, 1),
                });

                var hole3 = new SimplePolygon(new Vector[]
                {
                    new Vector( 6, 1),
                    new Vector( 6,-1),
                    new Vector( 5,-1),
                    new Vector( 5, 1),
                });

                var expectedVerts = new Polygon(new Vector[]
                {
                    new Vector(0, 2),
                    new Vector(1, 1),
                    new Vector(2, 1),
                    new Vector(3, 1),
                    new Vector(4, 1),
                    new Vector(5, 1),
                    new Vector(6, 1),
                    new Vector(6, -1),
                    new Vector(5, -1),
                    new Vector(5, 1),
                    new Vector(4, 1),
                    new Vector(4, -1),
                    new Vector(3, -1),
                    new Vector(3, 1),
                    new Vector(2, 1),
                    new Vector(2, -1),
                    new Vector(1, -1),
                    new Vector(1, 1),
                    new Vector(0, 2),
                    new Vector(0, -2),
                    new Vector(7, -2),
                    new Vector(7, 2),
                });

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

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Annulus.CSG.Triangulation.Triangulate(
                    new PerforatedPolygon(
                        silhouette,
                        new SimplePolygon[] { hole1, hole2, hole3 }
                    ), out vertices, out tris
                );

                CheckEqual(expectedVerts, vertices);
                CheckEqual(expected, tris);
            }

            public void PreGlomed()
            {
                var expectedVerts = new Polygon(new Vector[]
                {
                    new Vector(0, 2),
                    new Vector(1, 1),
                    new Vector(2, 1),
                    new Vector(3, 1),
                    new Vector(4, 1),
                    new Vector(5, 1),
                    new Vector(6, 1),
                    new Vector(6, -1),
                    new Vector(5, -1),
                    new Vector(5, 1),
                    new Vector(4, 1),
                    new Vector(4, -1),
                    new Vector(3, -1),
                    new Vector(3, 1),
                    new Vector(2, 1),
                    new Vector(2, -1),
                    new Vector(1, -1),
                    new Vector(1, 1),
                    new Vector(0, 2),
                    new Vector(0, -2),
                    new Vector(7, -2),
                    new Vector(7, 2),
                });

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

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                Triangulation.Triangulate(new PerforatedPolygon(new SimplePolygon(expectedVerts.VertexList)),
                    out vertices, out tris);

                CheckEqual(expectedVerts, vertices);
                CheckEqual(expected, tris);
            }

            public void NearlyDegenerate()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(0, 32.5495),
                    new Vector(-32.5, 0),
                    new Vector(0.0027519766, 0.0068680235),
                    new Vector(0.0027531388, 0.0068691867),
                });

                var expected = new Triangulation.Triangle[]
                {
                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 0, 1, 2},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 3, 0},
                    },
                };

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                var perf = new PerforatedPolygon(silhouette);
                Triangulation.Triangulate(perf, out vertices, out tris);

                CheckEqual(2, tris.Count);
                if (tris.Count == 2)
                {
                    CheckEqual(expected[0], tris[0]);
                    CheckEqual(expected[1], tris[1]);
                    Check(tris[0].SignedArea * silhouette.SignedArea >= 0);
                    Check(tris[1].SignedArea * silhouette.SignedArea >= 0);
                }
            }

            public void AlmostQuad()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(8.1436723672, 0), 
                    new Vector(2.6436176668, 1.0950222913), 
                    new Vector(0.0869745533, -0.0991503036), 
                    new Vector(0.0870241127, -0.0994347487), 
                    new Vector(0.0871418593, -0.0993287975), 
                    new Vector(4.9297140006, -0.7843685731),
                });

                var expected = new Triangulation.Triangle[]
                {
                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 0, 1, 2},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 3, 4},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 4, 5},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 5, 0},
                    },
                };

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                var perf = new PerforatedPolygon(silhouette);
                Triangulation.Triangulate(perf, out vertices, out tris);

                CheckEqual(expected.Length, tris.Count);
                if (tris.Count == expected.Length)
                {
                    CheckEqual(expected[0], tris[0]);
                    CheckEqual(expected[1], tris[1]);
                    Check(tris[0].SignedArea * silhouette.SignedArea >= 0);
                    Check(tris[1].SignedArea * silhouette.SignedArea >= 0);
                }
            }

            public void SlightlyDegenerate()
            {
                var silhouette = new SimplePolygon(new Vector[]
                {
                    new Vector(-0.0040673664, 0.0091354546),
                    new Vector(-0.2547749775, 0.4412832055),
                    new Vector(-0.7527000745, 0.0783746746),
                    new Vector(-0.0000000352, 0.0000168351),
                    new Vector(0, 0),
                    new Vector(0.0000145973, -0.0000083871),
                });

                var expected = new Triangulation.Triangle[]
                {
                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 0, 1, 2},
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 2, 3, 0, },
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 3, 4, 5, },
                    },

                    new Triangulation.Triangle
                    {
                        vertices = silhouette,
                        indices = new int[] { 5, 0, 3, },
                    },
                };

                Polygon vertices;
                List<Triangulation.Triangle> tris;
                var perf = new PerforatedPolygon(silhouette);
                Triangulation.Triangulate(perf, out vertices, out tris);

                CheckEqual(expected.Length, tris.Count);
                if (expected.Length == tris.Count)
                {
                    CheckEqual(expected[0], tris[0]);
                    CheckEqual(expected[1], tris[1]);
                    Check(tris[0].SignedArea * silhouette.SignedArea >= 0);
                    Check(tris[1].SignedArea * silhouette.SignedArea >= 0);
                }
            }
        }

        public class CanUseTriangleTests : UnitTestSharp.TestFixture
        {
            public void Good()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),                    
                    new Vector(0,1),
                    new Vector(1,0),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = 1;
                
                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);

                CheckTrue(canUse);
            }

            public void VertexInside()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),                    
                    new Vector(0,1),
                    new Vector(1,0),
                    new Vector(0.25,0.25),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = 1;

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);

                CheckFalse(canUse);
            }

            public void BadWinding()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),
                    new Vector(1,0),
                    new Vector(0,1),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = 1;

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);

                CheckFalse(canUse);
            }

            public void Degenerate_1()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,0),
                    new Vector(0,1),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = 1;

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);

                CheckFalse(canUse);
            }

            public void Degenerate_2()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,0),
                    new Vector(0,1),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = -1;

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);

                CheckFalse(canUse);
            }

            public void BadExpectedWinding_1()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,0),
                    new Vector(0,1),
                };

                var triangle = new Triangulation.Triangle
                {
                    vertices = new Polygon(vertices),

                    indices = new int[]
                    {
                        0, 1, 2,
                    },
                };

                Scalar winding = 0;

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                CheckThrow(typeof(Exception));
                bool canUse = Triangulation.CanUseTriangle(triangle, winding, sortNsweep);
            }
        }

        public class CutEdgesWithNearbyVerticesTests : UnitTestSharp.TestFixture
        {
            public void Basic_NoCut()
            {
                var vertices = new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,1),
                    new Vector(1,1),
                };

                var expectedPolygon = new Polygon(new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,1),
                    new Vector(1,1),
                });

                var polygon = new Polygon(vertices);

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                Triangulation.CutEdgesWithNearbyVertices(ref polygon, sortNsweep);

                CheckEqual(expectedPolygon, polygon);
            }

            public void Basic_Cut()
            {
                var vertices = new List<Vector>
                {
                    new Vector(0,0),
                    new Vector(0,1),
                    new Vector(1,1),
                    new Vector(0, 0.5),
                    new Vector(1, 0),
                };

                var expectedPolygon = new Polygon(new Vector[]
                {
                    new Vector(0,0),
                    new Vector(0,0.5),
                    new Vector(0,1),
                    new Vector(1,1),
                    new Vector(0, 0.5),
                    new Vector(1, 0),
                });

                var polygon = new Polygon(vertices);

                var sortNsweep = new Annulus.Broadphase.PointSortAndSweep<Vector>(
                    vertices, vertices.Select(x => x.X).ToList());

                Triangulation.CutEdgesWithNearbyVertices(ref polygon, sortNsweep);

                CheckEqual(expectedPolygon, polygon);
            }
        }
    }
}