public GridIndexTriangle(int index1, int index2, int index3, ref GridVector2[] pointArray)
 {
     i1 = index1;
     i2 = index2;
     i3 = index3;
     this.points = pointArray;
 }

        public static GridCircle CircleFromThreePoints(GridVector2 One, GridVector2 Two, GridVector2 Three)
        {
            if (One.X == Two.X && Two.X == Three.X)
            {
                throw new ArgumentException("Circle from three points with three points on a vertical line");
            }

            double A = Two.X - One.X;
            double B = Two.Y - One.Y;
            double C = Three.X - One.X;
            double D = Three.Y - One.Y;
            double E = A * (One.X + Two.X) + B * (One.Y + Two.Y);
            double F = C * (One.X + Three.X) + D * (One.Y + Three.Y);
            double G = 2 * (A * (Three.Y - Two.Y) - B * (Three.X - Two.X));

            //Check for colinear
               //         Debug.Assert(false == (G <= double.Epsilon && G >= -double.Epsilon));
            if (G <= double.Epsilon && G >= -double.Epsilon)
            {
                throw new ArgumentException("Circle from three points with three points on a line");
            }

            GridVector2 Center = new GridVector2();
            Center.X = (D * E - B * F) / G;
            Center.Y = (A * F - C * E) / G;

            return new GridCircle(Center, GridVector2.Distance(Center, One));
        }

        public void QuadTreeTestOne()
        {
            GridVector2[] points = new GridVector2[] { new GridVector2(0,0),
                                                       new GridVector2(1,1),
                                                       new GridVector2(-10,-10),
                                                       new GridVector2(-7.5, 2.5),
                                                       new GridVector2(8.5, -1.5),
                                                       new GridVector2(3.5, -6.5),
                                                       new GridVector2(1.5, -8.5),
                                                       new GridVector2(10, 10)};
            int[] values = new int[] {0,1,2,3,4,5,6,7};
            GridRectangle border = GridVector2.Border(points);
            QuadTree<int> tree = new QuadTree<int>(points, values, border);

            //Start with a basic test ensuring we can find all the existing points
            for(int i = 0; i < points.Length; i++)
            {
                double distance;
                int RetValue;
                RetValue = tree.FindNearest(points[i], out distance);

                Debug.Assert(RetValue == i);
                Debug.Assert(distance == 0);
            }

            //Check to see if we can find nearby points
            GridVector2[] nearpoints = new GridVector2[] { new GridVector2(.25,.25),
                                                       new GridVector2(.5,.51),
                                                       new GridVector2(-7.5,-7.5),
                                                       new GridVector2(-7.5, -1.5),
                                                       new GridVector2(8.5, -5.5),
                                                       new GridVector2(4.5, -7.75),
                                                       new GridVector2(1, -8.75),
                                                       new GridVector2(11, 11)}; //Out of original boundaries

            for (int i = 0; i < nearpoints.Length; i++)
            {
                double distance;
                int RetValue;
                RetValue = tree.FindNearest(nearpoints[i], out distance);

                Debug.Assert(RetValue == i);
                Debug.Assert(distance == GridVector2.Distance(points[i], nearpoints[i]));
            }

            //Check to see if we can return all points in a rectangle
            GridRectangle gridRect = new GridRectangle(0,15, 0,15);
            List<GridVector2> intersectPoints;
            List<int> intersectValues;
            tree.Intersect(gridRect, out intersectPoints, out intersectValues);
            Debug.Assert(intersectValues.Contains(0));
            Debug.Assert(intersectValues.Contains(1));
            Debug.Assert(intersectValues.Contains(7));

            Debug.Assert(false == intersectValues.Contains(2));
            Debug.Assert(false == intersectValues.Contains(3));
            Debug.Assert(false == intersectValues.Contains(4));
            Debug.Assert(false == intersectValues.Contains(5));
            Debug.Assert(false == intersectValues.Contains(6));
        }

        public LinkStructureToParentCommand(Viking.UI.Controls.SectionViewerControl parent,
                                               Structure structure, 
                                               Location_CanvasViewModel location)
            : base(parent)
        {
            this.putativeStruct = structure;
            this.putativeLoc = location;

            StructureType LocType = this.putativeStruct.Type;
            if (LocType != null)
            {
                linecolor = new Microsoft.Xna.Framework.Color(LocType.Color.R,
                    LocType.Color.G,
                    LocType.Color.B,
                    128);
            }
            else
            {
                linecolor = Microsoft.Xna.Framework.Color.Green;
            }

            //Transform the location position to the correct coordinates
            transformedPos = parent.SectionToVolume(new GridVector2(putativeLoc.X, putativeLoc.Y));

            parent.Cursor = Cursors.Cross;
        }

 public GridCircle(GridVector2 center, double radius)
 {
     this.Center = center;
     this.Radius = radius;
     this.RadiusSquared = radius * radius;
     _HashCode = new int?();
 }

        private static List<int> FindExtremes(GridVector2[] points)
        {
            int iMinX = 0;
            int iMinY = 0;
            int iMaxX = 0;
            int iMaxY = 0;

            for(int iPoint = 0; iPoint < points.Length; iPoint++)
            {
                GridVector2 point = points[iPoint];
                if (point.X < points[iMinX].X)
                    iMinX = iPoint;
                if (point.X > points[iMaxX].X)
                    iMaxX = iPoint;
                if (point.Y < points[iMinY].Y)
                    iMinX = iPoint;
                if (point.Y > points[iMaxY].Y)
                    iMaxY = iPoint;
            }

            List<int> ListExtremes = new List<int>( new int[]{ iMinX, iMinY, iMaxX, iMaxY} );
            ListExtremes.Sort();
            for(int iPoint = 1; iPoint < ListExtremes.Count; iPoint++)
            {
                if(ListExtremes[iPoint] == ListExtremes[iPoint-1])
                {
                    ListExtremes.RemoveAt(iPoint);
                    iPoint--;
                }
            }

            return ListExtremes;
        }

 public GridRectangle(GridVector2 position, double width, double height)
 {
     Left = position.X;
     Bottom = position.Y;
     Top = Bottom + height;
     Right = Left + width;
     _HashCode = new int?();
     Debug.Assert(Left <= Right && Bottom <= Top, "Grid Rectable argument error");
 }

 public static int[] Triangulate(GridVector2[] points, GridRectangle bounds)
 {
     double WidthMargin = bounds.Width;
     double HeightMargin = bounds.Height;
     GridVector2[] BoundingPoints = new GridVector2[] { new GridVector2(bounds.Left - WidthMargin, bounds.Bottom - HeightMargin),
                                                        new GridVector2(bounds.Right + WidthMargin, bounds.Bottom - HeightMargin),
                                                        new GridVector2(bounds.Left - WidthMargin, bounds.Top +  HeightMargin),
                                                        new GridVector2(bounds.Right + WidthMargin, bounds.Top + HeightMargin)};
     return Delaunay.Triangulate(points, BoundingPoints);
 }

        public void TestCircleFromPoints()
        {
            //
            // TODO: Add test logic	here
            //
            GridVector2[] points = new GridVector2[]  {new GridVector2(5, 0),
                                                        new GridVector2(0, 5),
                                                        new GridVector2(-5,0)};

            GridCircle circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(circle.Center.X == 0.0 && circle.Center.Y == 0.0);
            Debug.Assert(circle.Radius == 5.0);

            points = new GridVector2[]  {new GridVector2(0,-5),
                                                        new GridVector2(0, 5),
                                                        new GridVector2(Math.Cos(-0.5) * 5, Math.Sin(-0.5) * 5)};

            circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(GridVector2.Distance(circle.Center, new GridVector2(0, 0)) < Utilities.Global.Epsilon);
            Debug.Assert(circle.Radius > 5.0 - Utilities.Global.Epsilon && circle.Radius < 5.0 + Utilities.Global.Epsilon);

            points = new GridVector2[]  {new GridVector2(5,0),
                                                        new GridVector2(10, 5),
                                                        new GridVector2(5, 10)};

            circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(GridVector2.Distance(circle.Center, new GridVector2(5, 5)) < Utilities.Global.Epsilon);
            Debug.Assert(circle.Radius > 5.0 - Utilities.Global.Epsilon && circle.Radius < 5.0 + Utilities.Global.Epsilon);

            points = new GridVector2[]  {new GridVector2(5,0),
                                                        new GridVector2(5, 10),
                                                        new GridVector2(10, 5)};

            circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(GridVector2.Distance(circle.Center, new GridVector2(5, 5)) < Utilities.Global.Epsilon);
            Debug.Assert(circle.Radius > 5.0 - Utilities.Global.Epsilon && circle.Radius < 5.0 + Utilities.Global.Epsilon);

            points = new GridVector2[]  {new GridVector2(Math.Cos(0.5) * 5, Math.Sin(0.5) * 5),
                                                        new GridVector2(5, 0),
                                                        new GridVector2(Math.Cos(-0.5) * 5, Math.Sin(-0.5) * 5)};

            circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(GridVector2.Distance(circle.Center, new GridVector2(0,0)) < Utilities.Global.Epsilon);
            Debug.Assert(circle.Radius > 5.0 - Utilities.Global.Epsilon && circle.Radius < 5.0 + Utilities.Global.Epsilon);

            points = new GridVector2[]  {new GridVector2((Math.Cos(0.5) * 5) + 5, (Math.Sin(0.5) * 5) + 5),
                                                        new GridVector2(10, 5),
                                                        new GridVector2((Math.Cos(-0.5) * 5)+5, (Math.Sin(-0.5) * 5)+5)};

            circle = Utilities.GridCircle.CircleFromThreePoints(points);
            Debug.Assert(GridVector2.Distance(circle.Center, new GridVector2(5, 5)) < Utilities.Global.Epsilon);
            Debug.Assert(circle.Radius > 5.0 - Utilities.Global.Epsilon && circle.Radius < 5.0 + Utilities.Global.Epsilon);
        }

        protected override void OnMouseDown(object sender, System.Windows.Forms.MouseEventArgs e)
        {
            GridVector2 NewPosition = Parent.ScreenToWorld(e.X, e.Y);

            //Figure out if we are starting a rectangle
            if (e.Button == MouseButtons.Left)
            {
                bookmarkPosition = Parent.ScreenToWorld(e.X, e.Y);
                Execute();
            }

            base.OnMouseDown(sender, e);
        }

        protected override void OnMouseDown(object sender, System.Windows.Forms.MouseEventArgs e)
        {
            //            GridVector2 NewPosition = Parent.ScreenToWorld(e.X, e.Y);

            //Figure out if we are starting a rectangle
            if (e.Button == MouseButtons.Left)
            {
                Origin = Parent.ScreenToWorld(e.X, e.Y);
                this.CommandActive = true;
            }

            if (e.Button == MouseButtons.Right)
                this.Execute();

            base.OnMouseDown(sender, e);
        }

        public void GridLineIntersects()
        {
            //
            // TODO: Add test logic	here
            //

            GridLine lineA = new GridLine(new GridVector2(-5, 0),
                                                        new GridVector2(-10, 0));
            GridLine lineB = new GridLine(new GridVector2(0, 5),
                                                        new GridVector2(0, -5));

            GridVector2 intersect = new GridVector2();
            bool result = lineA.Intersects(lineB, out intersect);
            Debug.Assert(result == true);
            Debug.Assert(intersect.X == 0 && intersect.Y == 0);
        }

        public bool Intersects(GridLine seg, out GridVector2 Intersection)
        {
            //Function for each line
            //Ax + By = C
            Intersection = new GridVector2();

            if (seg == null)
                throw new ArgumentNullException("seg");

            if (this.Direction == seg.Direction)
                return false;

            GridVector2 A = Origin;
            GridVector2 B = Origin + Direction;

            GridVector2 segA = seg.Origin;
            GridVector2 segB = seg.Origin + seg.Direction;

            double A1 = B.Y - A.Y;
            double A2 = segB.Y - segA.Y;

            double B1 = A.X - B.X;
            double B2 = segA.X - segB.X;

            double C1 = A1 * A.X + B1 * A.Y;
            double C2 = A2 * segA.X + B2 * segA.Y;

            double det = A1 * B2 - A2 * B1;
            //Check if lines are parallel
            if (det == 0)
            {

                return false;
            }
            else
            {
                double x = (B2 * C1 - B1 * C2) / det;
                double y = (A1 * C2 - A2 * C1) / det;

                Intersection = new GridVector2(x, y);
                return true;
            }
        }

        public void TestAngle()
        {
            GridVector2 A = new GridVector2(5, 0);
            GridVector2 B = new GridVector2(2.5, 2.5);

            double angle = GridVector2.Angle(A,B);
            Debug.Assert(angle - Global.Epsilon < Math.PI / 4 &&
                         angle + Global.Epsilon > Math.PI / 4);

            A = new GridVector2(5, 0);
            B = new GridVector2(2.5, -2.5);

            angle = GridVector2.Angle(A,B);
            Debug.Assert(angle - Global.Epsilon < -Math.PI / 4 &&
                         angle + Global.Epsilon > -Math.PI / 4);

            //
            // TODO: Add test logic	here
            //
        }

        public IUIObjectBasic GetNearestLink(int SectionNumber, GridVector2 WorldPosition, out double distance)
        {
            //            double minDistance = double.MaxValue;
            distance = double.MaxValue;
            GridVector2 NearestIntersection;
            //            IUIObjectBasic FoundLink = null;
            LineSearchGrid<LocationLink> searchGrid = GetSearchGrid(SectionNumber);

            if (searchGrid == null)
                return null;

            LocationLink locLinkObj = searchGrid.GetNearest(WorldPosition, out NearestIntersection, out distance);
            if (locLinkObj != null)
            {
                if (distance > locLinkObj.Radius)
                {
                    locLinkObj = null;
                }
                else
                {
                    //minDistance = distance;
                    //FoundLink = locLinkObj as IUIObjectBasic;
                }
            }

            return locLinkObj;

            /*
            StructureLink structLinkObj = StructureLinksSearch.GetNearest(WorldPosition, out NearestIntersection, out distance);
            if (structLinkObj != null && distance < minDistance)
            {
                if (distance <= structLinkObj.Radius && distance < minDistance)
                {
                    FoundLink = structLinkObj as IUIObjectBasic;
                    minDistance = distance;
                }
            }
            distance = minDistance;
            return FoundLink;
             */
        }

        public void TestDelaunay()
        {
            GridVector2[] points = new GridVector2[]{ new GridVector2(50, 50),
                                                      new GridVector2(50, 100),
                                                      new GridVector2(50, 150),
                                                       new GridVector2(150, 50),
                                                      new GridVector2(150, 100),
                                                      new GridVector2(150, 150)};

            int[] iTriangles = Delaunay.Triangulate(points);
            int[] iExpected = new int[] {0,1,4,0,3,4,1,2,5,1,4,5};

            Debug.WriteLine(iTriangles.ToString());
            Debug.Assert(iTriangles.Length / 3 == 4); //We should find four triangles
            for(int i = 0; i < iExpected.Length; i++)
            {
                Debug.Assert(iExpected[i] == iTriangles[i]);
            }

            points = new GridVector2[]{ new GridVector2(50, 50),
                                                      new GridVector2(50, 100),
                                                      new GridVector2(50, 150),
                                                      new GridVector2(150, 50),
                                                      new GridVector2(150, 100),
                                                      new GridVector2(150, 150),
                                                      new GridVector2(250, 50),
                                                      new GridVector2(250, 100),
                                                      new GridVector2(250, 150)};

            iTriangles = Delaunay.Triangulate(points);
            iExpected = new int[] {3,4,7,3,6,7,4,5,8,4,7,8,0,1,4,0,3,4,1,2,5,1,4,5};

            Debug.WriteLine(iTriangles.ToString());
            Debug.Assert(iTriangles.Length / 3 == 8); //We should find four triangles

            for (int i = 0; i < iExpected.Length; i++)
            {
                Debug.Assert(iExpected[i] == iTriangles[i]);
            }
        }

        /*
        static public void DrawCircle(GraphicsDevice graphicsDevice,
                BasicEffect basicEffect,
                GridVector2 Pos,
                double Radius,
                Microsoft.Xna.Framework.Color color)
        {
            basicEffect.Begin();
            foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
            {
                pass.Begin();
                DrawCircle(Pos, Radius, color);
                pass.End();
            }
            basicEffect.End() ;
        }
         */
        /*
        static public void DrawCircle(
                SpriteBatch spriteBatch,
                GridVector2 Pos,
                double Radius,
                Microsoft.Xna.Framework.Color color)
        {
            int Diameter = (int)Math.Round(Radius * 2);
            if (Diameter < 1)
                return;

            int X = (int)Math.Round((Pos.X - Radius));
            int Y = (int)Math.Round((Pos.Y - Radius));

            spriteBatch.Begin(SpriteBlendMode.Additive | SpriteBlendMode.AlphaBlend);
            Microsoft.Xna.Framework.Rectangle DestRect = new Microsoft.Xna.Framework.Rectangle(X, Y, Diameter, Diameter);
            spriteBatch.Draw(CircleTexture, DestRect, color);
            spriteBatch.End();
            return;
        }
         */
        public static void DrawCircle(GraphicsDevice graphicsDevice,
                BasicEffect basicEffect, 
                GridVector2 Pos,
                double Radius,
                Microsoft.Xna.Framework.Color color)
        {
            //A better way to implement this is to just render a circle texture and add color using lighting, but
            //this will work for now

            VertexPositionColorTexture[] verts;

            //Can't populate until we've referenced CircleVerts
            int[] indicies;
            //int[] lineIndicies;
            float radius = (float)Radius;

            //Figure out if we should draw triangles instead
            verts = new VertexPositionColorTexture[GlobalPrimitives.SquareVerts.Length];
            GlobalPrimitives.SquareVerts.CopyTo(verts, 0);

            indicies = GlobalPrimitives.SquareIndicies;

            //Scale and color the verticies
            for (int i = 0; i < verts.Length; i++)
            {
                verts[i].Position.X *= radius;
                verts[i].Position.Y *= radius;

                verts[i].Position.X += (float)Pos.X;
                verts[i].Position.Y += (float)Pos.Y;
                verts[i].Color = color;
            }

            //PORT XNA 4
            /*
            VertexDeclaration oldVertexDeclaration = graphicsDevice.VertexDeclaration;
            if (VertexPositionColorTextureDecl == null)
            {
                VertexPositionColorTextureDecl = new VertexDeclaration(graphicsDevice, VertexPositionColorTexture.VertexElements);
            }

            graphicsDevice.VertexDeclaration = VertexPositionColorTextureDecl;
            graphicsDevice.RenderState.PointSize = 5.0f;
            */
            basicEffect.Texture = GlobalPrimitives.CircleTexture;
            basicEffect.TextureEnabled = true;
            basicEffect.VertexColorEnabled = true;
            basicEffect.LightingEnabled = false;
            //basicEffect.Alpha = 0.5f;
            //PORT XNA 4
            //basicEffect.CommitChanges();

            //PORT XNA 4
            //basicEffect.Begin();

             foreach (EffectPass pass in basicEffect.CurrentTechnique.Passes)
             {
                 //PORT XNA 4
                 //pass.Begin();
                 pass.Apply();

                 graphicsDevice.DrawUserIndexedPrimitives<VertexPositionColorTexture>(PrimitiveType.TriangleList,
//.........这里部分代码省略.........

 public abstract bool TryTransform(GridVector2 Point, out GridVector2 v);

 /// <summary>
 /// Adjust the output of the transform by the following vector
 /// </summary>
 /// <param name="vector"></param>
 public abstract void Translate(GridVector2 vector);

 public abstract GridVector2 Transform(GridVector2 Point);