public static IEnvelope GetEnvelopeForImage(IMap map, ICoordinate centre, double pixelWidth, double pixelHeight)
 {
     var envelope = new Envelope();
     ICoordinate size = ImageToWorld(map, pixelWidth, pixelHeight);
     envelope.SetCentre(centre, size.X, size.Y);
     return envelope;
 }

        /// <summary>
        /// Generates the WKT for a 2-point <c>LineString</c>.
        /// </summary>
        /// <param name="p0">The first coordinate.</param>
        /// <param name="p1">The second coordinate.</param>
        /// <returns></returns>
        public static String ToLineString(ICoordinate p0, ICoordinate p1)
        {
			if (double.IsNaN(p0.Z))
				return "LINESTRING(" + p0.X + " " + p0.Y + "," + p1.X + " " + p1.Y + ")";
			else
				return "LINESTRING(" + p0.X + " " + p0.Y + " " + p0.Z + "," + p1.X + " " + p1.Y + " " + p1.Z + ")";
		}

 /// <summary>
 /// 
 /// </summary>
 /// <param name="pts"></param>
 /// <param name="start"></param>
 /// <param name="end"></param>
 /// <param name="context"></param>
 public MonotoneChain(ICoordinate[] pts, int start, int end, object context)
 {
     this.pts = pts;
     this.start = start;
     this.end = end;
     this.context = context;
 }

        public override void OnMouseDown(ICoordinate worldPosition, MouseEventArgs e)
        {
            if (e.Button != MouseButtons.Left)
            {
                return;
            }
            MapControl.Cursor = Cursors.Hand;

            Dragging = true;
            DragImage = (Bitmap)Map.Image.Clone();
            StaticToolsImage = new Bitmap(Map.Image.Width, Map.Image.Height);
            Graphics g = Graphics.FromImage(StaticToolsImage);

            foreach (IMapTool tool in MapControl.Tools)
            {
                if (tool.IsActive)
                {
                    tool.OnPaint(new PaintEventArgs(g, MapControl.ClientRectangle));
                }
            }
            g.Dispose();

            DragStartPoint = e.Location;
            DragEndPoint = e.Location;
        }

        /// <summary>
        ///  Compares two <see cref="Coordinate" />s for their relative position along a segment
        /// lying in the specified <see cref="Octant" />.
        /// </summary>
        /// <param name="octant"></param>
        /// <param name="p0"></param>
        /// <param name="p1"></param>
        /// <returns>
        /// -1 if node0 occurs first, or
        ///  0 if the two nodes are equal, or
        ///  1 if node1 occurs first.
        /// </returns>
        public static int Compare(Octants octant, ICoordinate p0, ICoordinate p1)
        {
            // nodes can only be equal if their coordinates are equal
            if (p0.Equals2D(p1)) 
                return 0;

            int xSign = RelativeSign(p0.X, p1.X);
            int ySign = RelativeSign(p0.Y, p1.Y);

            switch (octant)
            {
                case Octants.Zero: 
                    return CompareValue(xSign, ySign);
                case Octants.One:
                    return CompareValue(ySign, xSign);
                case Octants.Two:
                    return CompareValue(ySign, -xSign);
                case Octants.Three:
                    return CompareValue(-xSign, ySign);
                case Octants.Four:
                    return CompareValue(-xSign, -ySign);
                case Octants.Five:
                    return CompareValue(-ySign, -xSign);
                case Octants.Six:
                    return CompareValue(-ySign, xSign);
                case Octants.Seven:
                    return CompareValue(xSign, -ySign);
            }

            Assert.ShouldNeverReachHere("invalid octant value: " + octant);
            return 0;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="pts1"></param>
        /// <param name="orientation1"></param>
        /// <param name="pts2"></param>
        /// <param name="orientation2"></param>
        /// <returns></returns>
        private static int CompareOriented(ICoordinate[] pts1, bool orientation1, ICoordinate[] pts2, bool orientation2)
        {
            int dir1 = orientation1 ? 1 : -1;
            int dir2 = orientation2 ? 1 : -1;
            int limit1 = orientation1 ? pts1.Length : -1;
            int limit2 = orientation2 ? pts2.Length : -1;

            int i1 = orientation1 ? 0 : pts1.Length - 1;
            int i2 = orientation2 ? 0 : pts2.Length - 1;            
            while (true)
            {
                int compPt = pts1[i1].CompareTo(pts2[i2]);
                if (compPt != 0)
                    return compPt;

                i1 += dir1;
                i2 += dir2;
                bool done1 = i1 == limit1;
                bool done2 = i2 == limit2;
                if(done1 && !done2) 
                    return -1;
                if(!done1 && done2) 
                    return 1;
                if(done1 && done2) 
                    return 0;
            }
        }

 /// <summary>
 /// 
 /// </summary>
 /// <param name="coord"></param>
 /// <param name="pt"></param>
 /// <returns></returns>
 public static ICoordinate FindDifferentPoint(ICoordinate[] coord, ICoordinate pt)
 {
     foreach (ICoordinate c in coord)
         if (!c.Equals(pt))
             return c;            
     return null;
 }

        ///// <summary>
        ///// snapping specific for a tool. Called before layer specific snappping is applied.
        ///// </summary>
        ///// <param name="sourceLayer"></param>
        ///// <param name="snapSource"></param>
        ///// <param name="worldPos"></param>
        ///// <param name="Envelope"></param>
        ///// <returns></returns>
        public void Snap(ILayer sourceLayer, IGeometry snapSource, ICoordinate worldPos, IEnvelope Envelope)
        {
            SnapResult = null;
            IFeature sourceFeature = MapControl.SelectTool.FeatureEditors[0].SourceFeature;
            if (sourceFeature.Geometry != snapSource)
                return;
            SnapRole snapRole = SnapRole.FreeAtObject;
            if ((Control.ModifierKeys & Keys.Control) == Keys.Control)
                snapRole = SnapRole.Free;
            ISnapRule snapRule = new SnapRule
                                     {
                                         SourceLayer = sourceLayer,
                                         TargetLayer = sourceLayer,
                                         Obligatory = true,
                                         SnapRole = snapRole,
                                         PixelGravity = 4
                                     };

            SnapResult = MapControl.SnapTool.ExecuteSnapRule(
                                                snapRule,
                                                sourceFeature,
                                                sourceFeature.Geometry,
                                                new List<IFeature>
                                                    {
                                                        sourceFeature
                                                    },
                                                worldPos,
                                                -1);
        }

 /// <summary>
 /// Test the point q to see whether it intersects the Envelope
 /// defined by p1-p2.
 /// </summary>
 /// <param name="p1">One extremal point of the envelope.</param>
 /// <param name="p2">Another extremal point of the envelope.</param>
 /// <param name="q">Point to test for intersection.</param>
 /// <returns><c>true</c> if q intersects the envelope p1-p2.</returns>
 public static bool Intersects(ICoordinate p1, ICoordinate p2, ICoordinate q)
 {
     if  (((q.X >= (p1.X < p2.X ? p1.X : p2.X))  && (q.X <= (p1.X > p2.X ? p1.X : p2.X))) &&
          ((q.Y >= (p1.Y < p2.Y ? p1.Y : p2.Y))  && (q.Y <= (p1.Y > p2.Y ? p1.Y : p2.Y))))            
         return true;                        
     return false;
 }

 private void AddCoordinates(ICoordinate[] coordinates)
 {
     int points = 0;
     Array.ForEach<ICoordinate>(coordinates, delegate(ICoordinate coordinate)
     {
         double? z = null;
         if (!double.IsNaN(coordinate.Z) && !double.IsInfinity(coordinate.Z))
         {
             z = coordinate.Z;
         }
         if (points == 0)
         {
             builder.BeginFigure(coordinate.X, coordinate.Y, z, null);
         }
         else
         {
             builder.AddLine(coordinate.X, coordinate.Y, z, null);
         }
         points++;
     });
     if (points != 0)
     {
         builder.EndFigure();
     }
 }

        /// <summary>
        /// snapping specific for a tool. Called before layer specific snapping is applied.
        /// </summary>
        /// <returns></returns>
        private void Snap(IGeometry snapSource, ICoordinate worldPos)
        {
            SnapResult = null;
            var sourceFeature = SelectTool.SelectedFeatureInteractors[0].SourceFeature;
            if (!Equals(sourceFeature.Geometry, snapSource))
            {
                return;
            }

            SnapRole snapRole;
            if (Mode == EditMode.Add)
            {
                snapRole = SnapRole.FreeAtObject;
                if ((Control.ModifierKeys & Keys.Control) == Keys.Control)
                    snapRole = SnapRole.Free;
            }
            else
            {
                snapRole = SnapRole.AllTrackers;
            }

            ISnapRule snapRule = new SnapRule {Obligatory = true, SnapRole = snapRole, PixelGravity = 4};

            SnapResult = MapControl.SnapTool.ExecuteSnapRule(snapRule, sourceFeature, sourceFeature.Geometry,
                                                             new List<IFeature> {sourceFeature}, worldPos, -1);
        }

        public override void OnMouseDown(ICoordinate worldPosition, MouseEventArgs e)
        {
            if (VectorLayer == null)
            {
                return;
            }

            if (e.Button != MouseButtons.Left)
            {
                return;
            }
            isBusy = true;
            StartDrawing();
            newNetworkFeature = GeometryFactory.CreatePoint(worldPosition);
            ((DataTableFeatureProvider)newNetworkFeatureLayer.DataSource).Clear();
            newNetworkFeatureLayer.DataSource.Add(newNetworkFeature);

            snapResult = MapControl.SnapTool.ExecuteLayerSnapRules(VectorLayer, null, newNetworkFeature, worldPosition, -1); //TODO check: why is this commented out in trunk?
            if (snapResult != null)
            {
                newNetworkFeature.Coordinates[0].X = snapResult.Location.X;
                newNetworkFeature.Coordinates[0].Y = snapResult.Location.Y;
            }

            newNetworkFeatureLayer.Style = MapControl.SnapTool.Failed ? errorNetworkFeatureStyle : networkFeatureStyle;
        }

        /// <summary>
        /// Creates a new segment string from a list of vertices.
        /// </summary>
        /// <param name="pts">The vertices of the segment string.</param>
        /// <param name="data">The user-defined data of this segment string (may be null).</param>
        public SegmentString(ICoordinate[] pts, Object data)
        {
            nodeList = new SegmentNodeList(this);

            this.pts = pts;
            Data = data;
        }

		public static ExtendedCoordinate[] Copy(ICoordinate[] coordinates)
		{
			ExtendedCoordinate[] copy = new ExtendedCoordinate[coordinates.Length];
			for (int i = 0; i < coordinates.Length; i++)			
				copy[i] = new ExtendedCoordinate(coordinates[i]);			
			return copy;
		}

        // 0 0 0 0
        // 0 1 0 0
        // 0 1 2 0
        // 0 1 2 3 0 ...
        private void AppendCurvePoint(IPolygon polygon, ICoordinate worldPos)
        {
            List<ICoordinate> vertices = new List<ICoordinate>();

            ILineString linearRing = polygon.ExteriorRing;
            for (int i = 0; i < linearRing.Coordinates.Length; i++)
            {
                if (linearRing.Coordinates.Length <= 4)
                {
                    if (1 == i)
                    {
                        if (linearRing.Coordinates[0].Equals2D(linearRing.Coordinates[1]))
                        {
                            // 0 0 ? 0 -> 0 1 ? 0 
                            vertices.Add(worldPos);
                        }
                        else
                        {
                            // 0 1 ? 0 -> 0 1 ? 0
                            vertices.Add(linearRing.Coordinates[i]);
                        }
                    }
                    else if (2 == i)
                    {
                        if (linearRing.Coordinates[1].Equals2D(linearRing.Coordinates[2]))
                        {
                            // 0 0 0 0 -> 0 1 1 0
                            vertices.Add(worldPos);
                        }
                        else
                        {
                            // 0 1 2 0 -> 0 1 2 3 0
                            vertices.Add(linearRing.Coordinates[i]);
                            vertices.Add(worldPos);
                        }
                    }
                    else
                    {
                        vertices.Add(linearRing.Coordinates[i]);
                    }
                }
                else
                {
                    if (i == (linearRing.Coordinates.Length - 1))
                    {
                        // insert before last point to keep ring closed
                        vertices.Add(worldPos);
                    }
                    vertices.Add(linearRing.Coordinates[i]);
                }
            }
            int index = FeatureProvider.GetFeatureCount() - 1;
            ILinearRing newLinearRing = GeometryFactory.CreateLinearRing(vertices.ToArray());
            IPolygon newPolygon = GeometryFactory.CreatePolygon(newLinearRing, null);
            //##layerEditor.UpdateCurvePointInserted(index, newPolygon, vertices.Count - 1);
            //((FeatureProvider)layerEditor.VectorLayer.DataSource).UpdateGeometry(index, newPolygon);
            ((Feature)FeatureProvider.Features[index]).Geometry = newPolygon;
            Layer.RenderRequired = true;
            // do not remove see newline MapControl.SelectTool.Select((VectorLayer)Layer, newPolygon, -1);
        }

 /// <summary>
 /// 
 /// </summary>
 /// <param name="coordinate"></param>
 /// <param name="writer"></param>        
 protected void Write(ICoordinate coordinate, XmlTextWriter writer)
 {
     writer.WriteStartElement(GMLElements.gmlPrefix, "coord", GMLElements.gmlNS);
     writer.WriteElementString(GMLElements.gmlPrefix, "X", GMLElements.gmlNS, coordinate.X.ToString("g", NumberFormatter));
     writer.WriteElementString(GMLElements.gmlPrefix, "Y", GMLElements.gmlNS, coordinate.Y.ToString("g", NumberFormatter));
     writer.WriteEndElement();
 }

 public override void OnMouseDown(ICoordinate worldPosition, MouseEventArgs e)
 {
     zooming = true;
     startDragPoint = e.Location;
     endDragPoint = e.Location;
     previewImage = (Bitmap)Map.Image.Clone();
 }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="p"></param>
        /// <param name="seg"></param>
        private void TestLineSegment(ICoordinate p, LineSegment seg) 
        {
            double xInt;  // x intersection of segment with ray
            double x1;    // translated coordinates
            double y1;
            double x2;
            double y2;

            /*
            *  Test if segment crosses ray from test point in positive x direction.
            */
            ICoordinate p1 = seg.P0;
            ICoordinate p2 = seg.P1;
            x1 = p1.X - p.X;
            y1 = p1.Y - p.Y;
            x2 = p2.X - p.X;
            y2 = p2.Y - p.Y;

            if (((y1 > 0) && (y2 <= 0)) || ((y2 > 0) && (y1 <= 0))) 
            {
                /*
                *  segment straddles x axis, so compute intersection.
                */
                xInt = RobustDeterminant.SignOfDet2x2(x1, y1, x2, y2) / (y2 - y1);
                
                /*
                *  crosses ray if strictly positive intersection.
                */
                if (0.0 < xInt) 
                    crossings++;            
            }
        }

        private Matrix getAffineTransformMatrix(ICoordinate p01, ICoordinate p02, ICoordinate p03,
                                                 ICoordinate p11, ICoordinate p12, ICoordinate p13)
        {
            Matrix a = new Matrix(new double[,] {
                                  { p02.X - p01.X, p02.Y - p01.Y, 0 },
                                  { p03.X - p01.X, p03.Y - p01.Y, 0 },
                                  { p01.X,         p01.Y,         1 }
            });

            Matrix b = new Matrix(new double[,] {
                                  { p12.X - p11.X, p12.Y - p11.Y, 0 },
                                  { p13.X - p11.X, p13.Y - p11.Y, 0 },
                                  { p11.X, p11.Y,                 1 }
            });

            if (!a.IsInvertible)
                return null;

            a = a.GetInverseMatrix();

            a = a.Multiply(b);
            a[0, 2] = 0;
            a[1, 2] = 0;
            a[2, 2] = 1;

            return a;
        }

        public void Start(INode node, AddRelatedFeature addRelatedFeature, int level)
        {
            lastFeature = node;
            lastRelatedFeatureGeometries.Clear();
            lastRelatedFeatures = new List<IFeature>();
            lastRelatedNewFeatures = new List<IFeature>();

            lastCoordinate = (ICoordinate)node.Geometry.Coordinates[0].Clone();
            foreach (IBranch branch in node.IncomingBranches)
            {
                lastRelatedFeatures.Add(branch);
                var clone = (IBranch)branch.Clone();
                lastRelatedNewFeatures.Add(clone);
                lastRelatedFeatureGeometries.Add((IGeometry)clone.Geometry.Clone());

                if (null != addRelatedFeature)
                {
                    activeInRules.Add(new List<IFeatureRelationInteractor>());
                    addRelatedFeature(activeInRules[activeInRules.Count - 1], branch, clone, level);
                }
            }
            foreach (var branch in node.OutgoingBranches)
            {
                lastRelatedFeatures.Add(branch);
                var clone = (IBranch) branch.Clone();
                lastRelatedNewFeatures.Add(clone);
                lastRelatedFeatureGeometries.Add((IGeometry)clone.Geometry.Clone());
                if (null != addRelatedFeature)
                {
                    activeOutRules.Add(new List<IFeatureRelationInteractor>());
                    addRelatedFeature(activeOutRules[activeOutRules.Count - 1], branch, clone, level);
                }
            }
        }