using System;
using System.Collections.Generic;
using Annulus.BezierCurves;
using Annulus.CSG;
using Azimuth;

namespace Annulus.UnitTests.CSG
{
    public class BoundaryLabellingTests : UnitTestSharp.TestFixture
    {
        public static QuadraticBezierCurve[] Rectangle(Scalar halfWidth, Scalar halfHeight)
        {
            return new QuadraticBezierCurve[]
            {
                DiskQueryTests.Line(new Vector(-halfWidth, -halfHeight), new Vector(halfWidth, -halfHeight)),
                DiskQueryTests.Line(new Vector(halfWidth, -halfHeight), new Vector(halfWidth, halfHeight)),
                DiskQueryTests.Line(new Vector(halfWidth, halfHeight), new Vector(-halfWidth, halfHeight)),
                DiskQueryTests.Line(new Vector(-halfWidth, halfHeight), new Vector(-halfWidth, -halfHeight)),
            };
        }

        // An L whose reflex corner is at (2, 2), between pieces 2 and 3.
        public static QuadraticBezierCurve[] LShape()
        {
            return new QuadraticBezierCurve[]
            {
                DiskQueryTests.Line(new Vector(-1, 0), new Vector(4, 0)),
                DiskQueryTests.Line(new Vector(4, 0), new Vector(4, 2)),
                DiskQueryTests.Line(new Vector(4, 2), new Vector(2, 2)),
                DiskQueryTests.Line(new Vector(2, 2), new Vector(2, 6)),
                DiskQueryTests.Line(new Vector(2, 6), new Vector(-1, 6)),
                DiskQueryTests.Line(new Vector(-1, 6), new Vector(-1, 0)),
            };
        }

        public class CtorTests : UnitTestSharp.TestFixture
        {
            public void Square_HasFourConvexJointsAndFourPieceStretches()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                CheckEqual(4, labelling.Joints.Length);
                for (int i = 0; i < 4; ++i)
                {
                    CheckEqual(JointKind.Convex, labelling.Joints[i].Kind);
                    CheckEqual(i, labelling.Joints[i].Piece);
                    CheckEqual((i + 1) % 4, labelling.Joints[i].NextPiece);
                    CheckEqual((Scalar)(Math.PI / 2), labelling.Joints[i].Turn);
                }

                CheckEqual(4, labelling.Stretches.Length);
                for (int i = 0; i < 4; ++i)
                {
                    CheckFalse(labelling.Stretches[i].IsFan);
                    CheckEqual(i, labelling.Stretches[i].Piece);
                    CheckEqual(i, labelling.Stretches[i].OwnSite);
                }
            }

            public void JointPositions_AreWherePiecesMeet()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(2, 1));

                CheckEqual(new Vector(2, -1), labelling.Joints[0].Position);
                CheckEqual(new Vector(2, 1), labelling.Joints[1].Position);
                CheckEqual(new Vector(-2, 1), labelling.Joints[2].Position);
                CheckEqual(new Vector(-2, -1), labelling.Joints[3].Position);
            }

            public void SharedTangent_IsASmoothJointWithNoTurn()
            {
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Line(new Vector(0, 0), new Vector(4, 0)),
                    DiskQueryTests.Piece(new Vector(4, 0), new Vector(6, 0), new Vector(8, 8)),
                    DiskQueryTests.Line(new Vector(8, 8), new Vector(0, 8)),
                    DiskQueryTests.Line(new Vector(0, 8), new Vector(0, 0)),
                };

                BoundaryLabelling labelling = new BoundaryLabelling(pieces);

                CheckEqual(JointKind.Smooth, labelling.Joints[0].Kind);
                CheckEqual((Scalar)0, labelling.Joints[0].Turn);
            }

            public void RightTurn_IsAReflexJointWithANegativeTurn()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                CheckEqual(JointKind.Reflex, labelling.Joints[2].Kind);
                CheckEqual((Scalar)(-Math.PI / 2), labelling.Joints[2].Turn);
            }

            public void ReflexJoint_AddsAFanStretchAfterItsPiece()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                CheckEqual(7, labelling.Stretches.Length);
                CheckTrue(labelling.Stretches[3].IsFan);
                CheckEqual(2, labelling.Stretches[3].Piece);
                CheckEqual(-3, labelling.Stretches[3].OwnSite);
                CheckEqual(3, labelling.Stretches[4].Piece);
                CheckFalse(labelling.Stretches[4].IsFan);
            }

            public void SinglePiece_Throws()
            {
                CheckThrow(typeof(ArgumentException));
                new BoundaryLabelling(new QuadraticBezierCurve[] { DiskQueryTests.Lens(bulge: 1)[0] });
            }

            public void PiecesThatDontMeet_Throws()
            {
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Line(new Vector(0, 0), new Vector(1, 0)),
                    DiskQueryTests.Line(new Vector(2, 0), new Vector(0, 0)),
                };

                CheckThrow(typeof(ArgumentException));
                new BoundaryLabelling(pieces);
            }

            public void JointThatDoublesBack_Throws()
            {
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Line(new Vector(0, 0), new Vector(2, 0)),
                    DiskQueryTests.Line(new Vector(2, 0), new Vector(0, 0)),
                };

                CheckThrow(typeof(ArgumentException));
                new BoundaryLabelling(pieces);
            }

            public void JointWithAZeroTangent_Throws()
            {
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Piece(new Vector(0, 0), new Vector(0, 0), new Vector(1, 0)),
                    DiskQueryTests.Line(new Vector(1, 0), new Vector(0, 0)),
                };

                CheckThrow(typeof(ArgumentException));
                new BoundaryLabelling(pieces);
            }
        }

        public class PointOnTests : UnitTestSharp.TestFixture
        {
            public void PieceMidpoint_IsOnThePieceWithTheInteriorOnTheLeft()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                BoundaryPoint point = labelling.PointOn(stretch: 0, parameter: 0.5);

                CheckEqual(new Vector(0, -1), point.Position);
                CheckEqual(new Vector(0, 1), point.Inward);
            }

            public void FanStart_FacesTheEndingPiecesNormal()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                BoundaryPoint point = labelling.PointOn(stretch: 3, parameter: 0);

                CheckEqual(new Vector(2, 2), point.Position);
                CheckEqual(new Vector(0, -1), point.Inward);
            }

            public void FanEnd_FacesTheNextPiecesNormal()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                BoundaryPoint point = labelling.PointOn(stretch: 3, parameter: 1);

                CheckEqual(new Vector(2, 2), point.Position);
                CheckEqual(new Vector(-1, 0), point.Inward);
            }

            public void FanMiddle_FacesBetweenTheTwoNormals()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());
                Scalar side = Math.Sqrt(0.5);

                BoundaryPoint point = labelling.PointOn(stretch: 3, parameter: 0.5);

                CheckEqual(new Vector(-side, -side), point.Inward);
            }
        }

        public class LabelAtTests : UnitTestSharp.TestFixture
        {
            public void SquareSideNearItsStart_IsLabelledWithThePreviousSide()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                CheckEqual(3, labelling.LabelAt(stretch: 0, parameter: 0.25));
            }

            public void SquareSideNearItsEnd_IsLabelledWithTheNextSide()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                CheckEqual(1, labelling.LabelAt(stretch: 0, parameter: 0.75));
            }

            public void MiddleOfALongSide_IsLabelledWithTheOppositeSide()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(2, 1));

                CheckEqual(2, labelling.LabelAt(stretch: 0, parameter: 0.5));
            }

            public void VertexOfATightLens_IsLabelledWithItsOwnSiteWhereTheCurvatureStopsTheDisk()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 2));

                CheckEqual(0, labelling.LabelAt(stretch: 0, parameter: 0.5));
            }

            public void VertexOfAShallowLens_IsLabelledWithTheOpposingPiece()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 1));

                CheckEqual(1, labelling.LabelAt(stretch: 0, parameter: 0.5));
            }

            public void FanDirectionDownward_IsLabelledWithTheFloor()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                CheckEqual(0, labelling.LabelAt(stretch: 3, parameter: 0));
            }

            public void FanDirectionLeftward_IsLabelledWithTheLeftWall()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                CheckEqual(5, labelling.LabelAt(stretch: 3, parameter: 1));
            }
        }

        public static QuadraticBezierCurve Corner(Vector start, Vector corner, Vector end)
        {
            return DiskQueryTests.Piece(start, corner, end);
        }

        // Regular N-gon whose sides are quadratic arcs meeting the unit circle at their ends, tangent to it there.
        public static QuadraticBezierCurve[] CircleArcs(int count)
        {
            QuadraticBezierCurve[] returnMe = new QuadraticBezierCurve[count];
            double half = Math.PI / count;
            double reach = 1 / Math.Cos(half);
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = DiskQueryTests.Piece(
                    new Vector(Math.Cos((2 * i - 1) * half), Math.Sin((2 * i - 1) * half)),
                    new Vector(reach * Math.Cos(2 * i * half), reach * Math.Sin(2 * i * half)),
                    new Vector(Math.Cos((2 * i + 1) * half), Math.Sin((2 * i + 1) * half)));
            }

            return returnMe;
        }

        public static QuadraticBezierCurve[] RoundedRectangle()
        {
            return new QuadraticBezierCurve[]
            {
                DiskQueryTests.Line(new Vector(-2, -2), new Vector(2, -2)),
                Corner(new Vector(2, -2), new Vector(3, -2), new Vector(3, -1)),
                DiskQueryTests.Line(new Vector(3, -1), new Vector(3, 1)),
                Corner(new Vector(3, 1), new Vector(3, 2), new Vector(2, 2)),
                DiskQueryTests.Line(new Vector(2, 2), new Vector(-2, 2)),
                Corner(new Vector(-2, 2), new Vector(-3, 2), new Vector(-3, 1)),
                DiskQueryTests.Line(new Vector(-3, 1), new Vector(-3, -1)),
                Corner(new Vector(-3, -1), new Vector(-3, -2), new Vector(-2, -2)),
            };
        }

        // Two lobes meeting at a reflex dip at (0, 0.5), and a convex tip at (0, -2).
        public static QuadraticBezierCurve[] Heart()
        {
            return new QuadraticBezierCurve[]
            {
                Corner(new Vector(0, -2), new Vector(3, -1), new Vector(2, 1)),
                Corner(new Vector(2, 1), new Vector(1.5, 2), new Vector(0, 0.5)),
                Corner(new Vector(0, 0.5), new Vector(-1.5, 2), new Vector(-2, 1)),
                Corner(new Vector(-2, 1), new Vector(-3, -1), new Vector(0, -2)),
            };
        }

        [UnitTestSharp.IgnoreFixture]
        public abstract class ShapeFixture : UnitTestSharp.TestFixture
        {
            // A vertex found next to a joint is only about 1e-8 accurate, so these compare to 1e-6.
            [UnitTestSharp.IgnoreTest]
            public void CheckNear(Vector expected, Vector actual)
            {
                CheckTrue((expected - actual).Length() < 1e-6);
            }

            // Every foot of a vertex is on the disk centred there, so each is the same distance from the centre.
            [UnitTestSharp.IgnoreTest]
            public void CheckFeetAreEquidistant(BoundaryLabelling labelling)
            {
                foreach (BoundaryVertex vertex in labelling.Vertices)
                {
                    Scalar radius = (labelling.Cuts[vertex.Cuts[0]].Foot - vertex.Centre).Length();
                    foreach (int cut in vertex.Cuts)
                    {
                        CheckEqual(radius, (labelling.Cuts[cut].Foot - vertex.Centre).Length());
                    }
                }
            }
        }

        public class ShapeTests : ShapeFixture
        {
            public void TightLens_CutsEachPieceWhereTheOriginIsAsNearAsItsCurvatureAllows()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 2));
                Scalar side = Math.Sqrt(0.5);

                List<BoundaryCut> cuts = labelling.FindChanges(0);

                CheckEqual(2, cuts.Count);
                CheckEqual((1 - side) / 2, cuts[0].Parameter);
                CheckEqual(new Vector(-side, -0.5), cuts[0].Foot);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
                CheckEqual(1, cuts[0].AcrossBefore);
                CheckEqual(0, cuts[0].AcrossAfter);
                CheckEqual((1 + side) / 2, cuts[1].Parameter);
                CheckEqual(0, cuts[1].AcrossBefore);
                CheckEqual(1, cuts[1].AcrossAfter);
            }

            public void TightLens_HasOneVertexWithTwoFeetOnEachPiece()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 2));

                CheckEqual(1, labelling.Vertices.Length);
                CheckEqual(4, labelling.Vertices[0].Cuts.Length);
            }

            public void OneSample_MissesTheMiddleOfATightLensWhereThePieceIsItsOwnNearest()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 2), sampleCount: 1);

                CheckEqual(0, labelling.FindChanges(0).Count);
                CheckEqual(0, labelling.Vertices.Length);
            }

            public void ThreeSamples_MissTheNarrowMiddleOfALensJustPastTheCurvatureThreshold()
            {
                BoundaryLabelling coarse = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 1.45), sampleCount: 3);
                BoundaryLabelling fine = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 1.45));

                CheckEqual(0, coarse.Vertices.Length);
                CheckEqual(1, fine.Vertices.Length);
            }

            public void ShallowLens_HasNoCutsBeyondItsCorners()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(DiskQueryTests.Lens(bulge: 1));

                CheckEqual(0, labelling.FindChanges(0).Count);
                CheckEqual(0, labelling.FindChanges(1).Count);
                CheckEqual(0, labelling.Vertices.Length);
            }

            public void Crescent_HasOneVertexWithItsTwoFeetOnTheOuterPiece()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Piece(new Vector(-1, 0), new Vector(0, -3), new Vector(1, 0)),
                    DiskQueryTests.Piece(new Vector(1, 0), new Vector(0, -1), new Vector(-1, 0)),
                });

                CheckEqual(1, labelling.Vertices.Length);
                CheckEqual(2, labelling.Vertices[0].Cuts.Length);
                BoundaryCut left = labelling.Cuts[labelling.Vertices[0].Cuts[0]];
                BoundaryCut right = labelling.Cuts[labelling.Vertices[0].Cuts[1]];
                CheckEqual(0, left.Stretch);
                CheckEqual(0, right.Stretch);
                CheckEqual(left.Foot.X, -right.Foot.X);
                CheckEqual(left.Foot.Y, right.Foot.Y);
                CheckEqual((Scalar)0, labelling.Vertices[0].Centre.X);
            }

            public void Crescent_VertexTouchesTheInnerPiecesMiddleAsWellAsItsFeet()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Piece(new Vector(-1, 0), new Vector(0, -3), new Vector(1, 0)),
                    DiskQueryTests.Piece(new Vector(1, 0), new Vector(0, -1), new Vector(-1, 0)),
                });
                BoundaryVertex vertex = labelling.Vertices[0];

                Scalar toFeet = (labelling.Cuts[vertex.Cuts[0]].Foot - vertex.Centre).Length();

                CheckEqual(toFeet, -0.5 - vertex.Centre.Y);
            }

            public void ThreeArcsTangentToACircle_MeetAtTheCircleCentre()
            {
                CheckArcsMeetAtTheCentre(3);
            }

            public void FourArcsTangentToACircle_MeetAtTheCircleCentre()
            {
                CheckArcsMeetAtTheCentre(4);
            }

            public void EightArcsTangentToACircle_MeetAtTheCircleCentre()
            {
                CheckArcsMeetAtTheCentre(8);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckArcsMeetAtTheCentre(int count)
            {
                BoundaryLabelling labelling = new BoundaryLabelling(CircleArcs(count));

                CheckEqual(1, labelling.Vertices.Length);
                CheckEqual(new Vector(0, 0), labelling.Vertices[0].Centre);
                CheckEqual(count, labelling.Vertices[0].Cuts.Length);
                for (int i = 0; i < count; ++i)
                {
                    CheckEqual(0, labelling.FindChanges(i).Count);
                }
            }

            public void SmoothJointWhereCurvatureStopsTheDisk_EndsItsSpokeAtALeaf()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(G1Corner());

                BoundaryCut cut = labelling.StretchStartCut(1);

                CheckEqual(SpokeEnd.Leaf, cut.Spoke);
                CheckEqual(-1, cut.Vertex);
                CheckEqual(new Vector(4, 1), cut.Centre);
            }

            public void SmoothJointWhereCurvatureStopsTheDisk_HasTwoVerticesWithEquidistantFeet()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(G1Corner());

                CheckEqual(2, labelling.Vertices.Length);
                CheckEqual(labelling.Vertices[0].Centre.X, labelling.Vertices[0].Centre.Y);
                CheckFeetAreEquidistant(labelling);
            }
        }

        public class HeartTests : ShapeFixture
        {
            private BoundaryLabelling labelling;

            public override void FixtureSetup()
            {
                labelling = new BoundaryLabelling(Heart());
            }

            public void HasAReflexDipWithAFanBetweenItsLobes()
            {
                CheckEqual(JointKind.Reflex, labelling.Joints[1].Kind);
                CheckEqual(5, labelling.Stretches.Length);
                CheckTrue(labelling.Stretches[2].IsFan);
            }

            public void CutsTheDipsFanAtTheMiddleOnTheAxisOfSymmetry()
            {
                List<BoundaryCut> cuts = labelling.FindChanges(2);

                CheckEqual(1, cuts.Count);
                CheckEqual((Scalar)0.5, cuts[0].Parameter);
                CheckEqual((Scalar)0, cuts[0].Centre.X);
                CheckEqual(new Vector(0, 0.5), cuts[0].Foot);
            }

            public void HasFiveVerticesMirroredAcrossTheAxis()
            {
                CheckEqual(5, labelling.Vertices.Length);
                CheckNear(new Vector(0, labelling.Vertices[0].Centre.Y), labelling.Vertices[0].Centre);
                CheckNear(new Vector(-labelling.Vertices[1].Centre.X, labelling.Vertices[1].Centre.Y),
                    labelling.Vertices[3].Centre);
                CheckNear(new Vector(40.0 / 29, 20.0 / 29), labelling.Vertices[2].Centre);
                CheckNear(new Vector(-40.0 / 29, 20.0 / 29), labelling.Vertices[4].Centre);
            }

            public void VertexFeetAreEquidistantFromTheirCentres()
            {
                CheckFeetAreEquidistant(labelling);
            }
        }

        public class RoundedRectangleTests : ShapeFixture
        {
            private BoundaryLabelling labelling;

            public override void FixtureSetup()
            {
                labelling = new BoundaryLabelling(RoundedRectangle());
            }

            public void HasVerticesAtTheCornerCentresAndTheEndsOfTheAxis()
            {
                CheckEqual(6, labelling.Vertices.Length);
                CheckEqual(new Vector(-2, -1), labelling.Vertices[0].Centre);
                CheckEqual(new Vector(-1, 0), labelling.Vertices[1].Centre);
                CheckEqual(new Vector(1, 0), labelling.Vertices[2].Centre);
                CheckEqual(new Vector(2, -1), labelling.Vertices[3].Centre);
                CheckEqual(new Vector(2, 1), labelling.Vertices[4].Centre);
                CheckEqual(new Vector(-2, 1), labelling.Vertices[5].Centre);
            }

            public void AxisVerticesHaveThreeFeetAndCornerVerticesTwo()
            {
                CheckEqual(2, labelling.Vertices[0].Cuts.Length);
                CheckEqual(3, labelling.Vertices[1].Cuts.Length);
                CheckEqual(3, labelling.Vertices[2].Cuts.Length);
                CheckEqual(2, labelling.Vertices[3].Cuts.Length);
            }

            public void HasNoLeaves()
            {
                foreach (BoundaryCut cut in labelling.Cuts)
                {
                    CheckFalse(cut.Spoke == SpokeEnd.Leaf);
                }
            }
        }

        // A curve that leaves a straight floor tangentially but curves at once, so the joint is G1 but not G2.
        public static QuadraticBezierCurve[] G1Corner()
        {
            return new QuadraticBezierCurve[]
            {
                DiskQueryTests.Line(new Vector(0, 0), new Vector(4, 0)),
                DiskQueryTests.Piece(new Vector(4, 0), new Vector(6, 0), new Vector(8, 8)),
                DiskQueryTests.Line(new Vector(8, 8), new Vector(0, 8)),
                DiskQueryTests.Line(new Vector(0, 8), new Vector(0, 0)),
            };
        }

        public class VerticesTests : UnitTestSharp.TestFixture
        {
            public void Square_HasOneVertexWithAFootOnEachSide()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                CheckEqual(1, labelling.Vertices.Length);
                CheckEqual(new Vector(0, 0), labelling.Vertices[0].Centre);
                CheckEqual(4, labelling.Vertices[0].Cuts.Length);
                foreach (int cut in labelling.Vertices[0].Cuts)
                {
                    CheckEqual(0, labelling.Cuts[cut].Vertex);
                }
            }

            public void Rectangle_HasAVertexAtEachEndOfItsAxis()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(2, 1));

                CheckEqual(2, labelling.Vertices.Length);
                CheckEqual(new Vector(-1, 0), labelling.Vertices[0].Centre);
                CheckEqual(3, labelling.Vertices[0].Cuts.Length);
                CheckEqual(new Vector(1, 0), labelling.Vertices[1].Centre);
                CheckEqual(3, labelling.Vertices[1].Cuts.Length);
            }

            public void ConvexCornerCuts_BelongToNoVertex()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                CheckEqual(-1, labelling.Cuts[0].Vertex);
            }

            public void LShape_HasAPseudoVertexWhoseFarFootIsOnTheFloorBelowTheCorner()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                BoundaryVertex pseudo = labelling.Vertices[1];

                CheckEqual(new Vector(2, 1), pseudo.Centre);
                CheckEqual(2, pseudo.Cuts.Length);
                CheckEqual(new Vector(2, 0), labelling.Cuts[pseudo.Cuts[0]].Foot);
                CheckEqual(new Vector(2, 2), labelling.Cuts[pseudo.Cuts[1]].Foot);
            }

            public void LShape_CornersFanReachesTheFloorAndLeftWallAtTheirCommonVertex()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());
                Scalar angle = Math.Atan(1.5) + Math.Asin(1 / Math.Sqrt(13));
                Scalar radius = 2 / (1 + Math.Cos(angle));

                BoundaryVertex vertex = labelling.Vertices[0];

                CheckEqual(new Vector(2 - radius * Math.Sin(angle), 2 - radius * Math.Cos(angle)), vertex.Centre);
                CheckEqual(3, vertex.Cuts.Length);
            }
        }

        public class StretchStartCutTests : UnitTestSharp.TestFixture
        {
            public void ConvexCorner_HasAZeroLengthSpokeAtTheJoint()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                BoundaryCut cut = labelling.StretchStartCut(1);

                CheckTrue(cut.AtStretchStart);
                CheckEqual(1, cut.Stretch);
                CheckEqual((Scalar)0, cut.Parameter);
                CheckEqual(SpokeEnd.Corner, cut.Spoke);
                CheckEqual(new Vector(1, -1), cut.Foot);
                CheckEqual(new Vector(1, -1), cut.Centre);
            }

            public void ConvexCorner_TakesItsLabelsFromEitherSideOfTheJoint()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                BoundaryCut cut = labelling.StretchStartCut(1);

                CheckEqual(1, cut.AcrossBefore);
                CheckEqual(0, cut.AcrossAfter);
            }

            public void SmoothJointWhereTheCurvatureStopsTheDisk_HasALeafSpoke()
            {
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Line(new Vector(0, 0), new Vector(4, 0)),
                    DiskQueryTests.Piece(new Vector(4, 0), new Vector(6, 0), new Vector(8, 8)),
                    DiskQueryTests.Line(new Vector(8, 8), new Vector(0, 8)),
                    DiskQueryTests.Line(new Vector(0, 8), new Vector(0, 0)),
                };
                BoundaryLabelling labelling = new BoundaryLabelling(pieces);

                BoundaryCut cut = labelling.StretchStartCut(1);

                CheckEqual(SpokeEnd.Leaf, cut.Spoke);
                CheckEqual(new Vector(4, 0), cut.Foot);
                CheckEqual(new Vector(4, 1), cut.Centre);
            }

            public void ReflexJointsFan_StartsWithASpokeAlongTheEndingPiecesNormalToTheFloor()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                BoundaryCut cut = labelling.StretchStartCut(3);

                CheckTrue(cut.AtStretchStart);
                CheckEqual(SpokeEnd.Vertex, cut.Spoke);
                CheckEqual(new Vector(2, 2), cut.Foot);
                CheckEqual(new Vector(2, 1), cut.Centre);
                CheckEqual(0, cut.AcrossBefore);
                CheckEqual(0, cut.AcrossAfter);
            }

            public void PieceAfterAReflexJointsFan_StartsWithASpokeAlongItsNormalToTheLeftWall()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());

                BoundaryCut cut = labelling.StretchStartCut(4);

                CheckEqual(SpokeEnd.Vertex, cut.Spoke);
                CheckEqual(new Vector(2, 2), cut.Foot);
                CheckEqual(new Vector(0.5, 2), cut.Centre);
                CheckEqual(5, cut.AcrossBefore);
                CheckEqual(5, cut.AcrossAfter);
            }

            public void FirstStretch_TakesItsPreviousLabelFromTheLastOne()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                BoundaryCut cut = labelling.StretchStartCut(0);

                CheckEqual(new Vector(-1, -1), cut.Foot);
                CheckEqual(0, cut.AcrossBefore);
                CheckEqual(3, cut.AcrossAfter);
            }
        }

        public class FindChangesTests : UnitTestSharp.TestFixture
        {
            public void CutsWithinAStretch_AreNotStretchStarts()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                BoundaryCut cut = labelling.FindChanges(0)[0];

                CheckFalse(cut.AtStretchStart);
                CheckEqual(SpokeEnd.Vertex, cut.Spoke);
            }

            public void SquareBottom_CutsAtItsMidpointWhereTheCentreIsTheSquaresCentre()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(0);

                CheckEqual(1, cuts.Count);
                CheckEqual(0, cuts[0].Stretch);
                CheckEqual((Scalar)0.5, cuts[0].Parameter);
                CheckEqual(new Vector(0, -1), cuts[0].Foot);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
                CheckEqual(3, cuts[0].AcrossBefore);
                CheckEqual(1, cuts[0].AcrossAfter);
            }

            public void SquareRight_SwitchesFromTheBottomToTheTop()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(1);

                CheckEqual(1, cuts.Count);
                CheckEqual(0, cuts[0].AcrossBefore);
                CheckEqual(2, cuts[0].AcrossAfter);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
            }

            public void SquareTop_SwitchesFromTheRightToTheLeft()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(2);

                CheckEqual(1, cuts.Count);
                CheckEqual(1, cuts[0].AcrossBefore);
                CheckEqual(3, cuts[0].AcrossAfter);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
            }

            public void SquareLeft_SwitchesFromTheTopToTheBottom()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(1, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(3);

                CheckEqual(1, cuts.Count);
                CheckEqual(2, cuts[0].AcrossBefore);
                CheckEqual(0, cuts[0].AcrossAfter);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
            }

            public void RectangleLongSide_CutsWhereTheCornerBisectorsMeetTheAxis()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(2, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(0);

                CheckEqual(2, cuts.Count);
                CheckEqual((Scalar)0.25, cuts[0].Parameter);
                CheckEqual(new Vector(-1, 0), cuts[0].Centre);
                CheckEqual(3, cuts[0].AcrossBefore);
                CheckEqual(2, cuts[0].AcrossAfter);
                CheckEqual((Scalar)0.75, cuts[1].Parameter);
                CheckEqual(new Vector(1, 0), cuts[1].Centre);
                CheckEqual(2, cuts[1].AcrossBefore);
                CheckEqual(1, cuts[1].AcrossAfter);
            }

            public void RectangleShortSide_CutsOnceAtItsMiddle()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(Rectangle(2, 1));

                List<BoundaryCut> cuts = labelling.FindChanges(1);

                CheckEqual(1, cuts.Count);
                CheckEqual((Scalar)0.5, cuts[0].Parameter);
                CheckEqual(new Vector(1, 0), cuts[0].Centre);
                CheckEqual(0, cuts[0].AcrossBefore);
                CheckEqual(2, cuts[0].AcrossAfter);
            }

            public void TriangleSide_CutsAtTheTangentPointOfTheInscribedCircle()
            {
                Scalar root3 = Math.Sqrt(3);
                QuadraticBezierCurve[] pieces = new QuadraticBezierCurve[]
                {
                    DiskQueryTests.Line(new Vector(0, 2), new Vector(-root3, -1)),
                    DiskQueryTests.Line(new Vector(-root3, -1), new Vector(root3, -1)),
                    DiskQueryTests.Line(new Vector(root3, -1), new Vector(0, 2)),
                };
                BoundaryLabelling labelling = new BoundaryLabelling(pieces);

                List<BoundaryCut> cuts = labelling.FindChanges(0);

                CheckEqual(1, cuts.Count);
                CheckEqual((Scalar)0.5, cuts[0].Parameter);
                CheckEqual(new Vector(-root3 / 2, 0.5), cuts[0].Foot);
                CheckEqual(new Vector(0, 0), cuts[0].Centre);
                CheckEqual(2, cuts[0].AcrossBefore);
                CheckEqual(1, cuts[0].AcrossAfter);
            }

            public void FanOfAReflexCorner_CutsWhereTheFloorAndTheLeftWallTie()
            {
                BoundaryLabelling labelling = new BoundaryLabelling(LShape());
                Scalar angle = Math.Atan(1.5) + Math.Asin(1 / Math.Sqrt(13));
                Scalar radius = 2 / (1 + Math.Cos(angle));

                List<BoundaryCut> cuts = labelling.FindChanges(3);

                CheckEqual(1, cuts.Count);
                CheckEqual(3, cuts[0].Stretch);
                CheckEqual(angle / (Math.PI / 2), cuts[0].Parameter);
                CheckEqual(new Vector(2, 2), cuts[0].Foot);
                CheckEqual(new Vector(2 - radius * Math.Sin(angle), 2 - radius * Math.Cos(angle)), cuts[0].Centre);
                CheckEqual(0, cuts[0].AcrossBefore);
                CheckEqual(5, cuts[0].AcrossAfter);
            }
        }
    }
}