public void MinimumSizeIsRespected()
        {
            // Setup
            string filePath = Path.Combine(this.TestContext.TestDir, "Out\\Dots", "chat.dot");
            GeometryGraph graph = this.LoadGraph(filePath);

            const double DesiredHeight = 100000;
            const double DesiredWidth = 100000;

            SugiyamaLayoutSettings settings = new SugiyamaLayoutSettings();
            settings.MinimalHeight = DesiredHeight;
            settings.MinimalWidth = DesiredWidth;
            
            // Execute
            LayeredLayout layeredLayout = new LayeredLayout(graph, settings);
            layeredLayout.Run();

            // Verify the graph is the correct size
            Assert.IsTrue(DesiredHeight < graph.Height, "Graph height should be the minimal height.");
            Assert.IsTrue(DesiredWidth < graph.Width, "Graph width should be the minimal width.");

            // Verify the nodes were spread apart to fill the space
            Rectangle nodeBounds = new Rectangle(graph.Nodes.Select(n => n.BoundingBox));
            Assert.IsTrue(DesiredWidth < nodeBounds.Height, "The graph nodes weren't scaled vertically to fill the space.");
            Assert.IsTrue(DesiredWidth < nodeBounds.Width, "The graph nodes weren't scaled horizontally to fill the space.");
        }

 internal PreGraph(EdgeGeometry[] egs, Set<ICurve> nodeBoundaries) {
     edgeGeometries = new List<EdgeGeometry>(egs);
     this.nodeBoundaries = new Set<ICurve>(nodeBoundaries);
     boundingBox = Rectangle.CreateAnEmptyBox();
     foreach (var curve in nodeBoundaries)
         boundingBox.Add(curve.BoundingBox);
 }

 internal void AddToAdjacentVertex(TransientGraphUtility transUtil
             , VisibilityVertex targetVertex, Directions dirToExtend, Rectangle limitRect) {
     if (!PointComparer.Equal(this.Point, targetVertex.Point)) {
         transUtil.FindOrAddEdge(this.Vertex, targetVertex, InitialWeight);
     }
     ExtendEdgeChain(transUtil, targetVertex, dirToExtend, limitRect);
 }

 private bool InteriorEdgeCrossesObstacle(ObstacleTree obstacleTree) {
     // File Test: Nudger_Overlap4
     // Use the VisibilityBoundingBox for groups because those are what the tree consists of.
     var rect = new Rectangle(this.UnpaddedBorderIntersect, this.VisibilityBorderIntersect);
     return InteriorEdgeCrossesObstacle(rect, obs => obs.VisibilityPolyline,
             obstacleTree.Root.GetLeafRectangleNodesIntersectingRectangle(rect)
                 .Where(node => !node.UserData.IsGroup && (node.UserData != this.Obstacle)).Select(node => node.UserData));
 }

 public GridTraversal(Rectangle boundingBox, int iLevel)
 {
     _boundingBox = boundingBox;
     _iLevel = iLevel;
     _numberOfTilesOnSide = (ulong)Math.Pow(2, iLevel);
     TileWidth = boundingBox.Width / _numberOfTilesOnSide;
     TileHeight = boundingBox.Height / _numberOfTilesOnSide;
 }

 static double CommonArea(ref Rectangle a, ref Rectangle b)
 {
     double l = Math.Min(a.Left, b.Left);
     double r = Math.Max(a.Right, b.Right);
     double t = Math.Max(a.Top, b.Top);
     double bt = Math.Min(a.Bottom, b.Bottom);
     return (r - l) * (t - bt);
 }

        internal bool IntersectsOnY(Rectangle r){
            if (r.Bottom > top + ApproximateComparer.DistanceEpsilon)
                return false;

            if (r.Top < bottom - ApproximateComparer.DistanceEpsilon)
                return false;

            return true;
            //return ApproximateComparer.Compare(r.bottom, top) <= 0 && ApproximateComparer.Compare(bottom, r.top) <= 0;
        }

        /// <summary>
        /// Additionally needed area of nodes compared to the optimal packing of the nodes.
        /// </summary>
        /// <param name="graphOriginal"></param>
        /// <param name="graphNew"></param>
        /// <returns></returns>
        public static Tuple<String, double> Area(GeometryGraph graph)
        {
            double minimalArea = graph.Nodes.Sum(v => v.BoundingBox.Area);

            Rectangle boundingBoxNew=new Rectangle(graph.Nodes.Select(v=>v.BoundingBox));
            double areaNew = boundingBoxNew.Area;

            double ratio = areaNew/minimalArea;
            //            return Tuple.Create("AreaIncreaseToMinPacking",ratio - 1);//we are interested in increase compared to optimal packing.
            return Tuple.Create("AreaAbsolute/(1E6)", areaNew / (1E6));//we are interested in increase compared to optimal packing.
        }

 public Rectangle GetInitialBoundingBox() {
     Rectangle bbox = new Rectangle();
     bbox.SetToEmpty();
     foreach (var rect in _fixedRectangles) {
         bbox.Add(rect);
     }
     foreach (var rect in _moveableRectangles) {
         bbox.Add(rect);
     }
     return bbox;
 }

        internal bool IntersectsOnX(Rectangle r){
            //return ApproximateComparer.Compare(r.left, right) <= 0 && ApproximateComparer.Compare(left, r.right) <= 0;
            if (r.Left > right + ApproximateComparer.DistanceEpsilon)
                return false;

            if (r.Right < left - ApproximateComparer.DistanceEpsilon)
                return false;

            return true;

            //return ApproximateComparer.Compare(r.left, right) <= 0 && ApproximateComparer.Compare(left, r.right) <= 0;
        }

 // Adds an edge from this.Vertex to a (possibly new) vertex at an intersection with an
 // existing Edge that adjoins the point.  We take 'dir' as an input parameter for edge
 // extension because we may be on the edge so can't calculate the direction.
 internal VisibilityVertex AddEdgeToAdjacentEdge(TransientGraphUtility transUtil
             , VisibilityEdge targetEdge, Directions dirToExtend, Rectangle limitRect) {
     Point targetIntersect = StaticGraphUtility.SegmentIntersection(targetEdge, this.Point);
     VisibilityVertex targetVertex = transUtil.VisGraph.FindVertex(targetIntersect);
     if (null != targetVertex) {
         AddToAdjacentVertex(transUtil, targetVertex, dirToExtend, limitRect);
     }
     else {
         targetVertex = transUtil.AddEdgeToTargetEdge(this.Vertex, targetEdge, targetIntersect);
     }
     ExtendEdgeChain(transUtil, targetVertex, dirToExtend, limitRect);
     return targetVertex;
 }

        public OverlapRemovalFixedSegmentsBitmap(Rectangle[] moveableRectangles, Rectangle[] fixedRectangles,
            SymmetricSegment[] fixedSegments) {
            _moveableRectangles = moveableRectangles;
            _fixedRectangles = fixedRectangles;
            _fixedSegments = fixedSegments;

            _bbox = GetInitialBoundingBox();
            _bbox.ScaleAroundCenter(1.25);

            InitBitmap();
            InitTransform();
            
            movedRectangles = new Rectangle[moveableRectangles.Length];
        }

 /// <summary>
 /// intersection (possibly empty) of rectangles
 /// </summary>
 /// <param name="rectangle"></param>
 /// <returns></returns>
 public Rectangle Intersection(Rectangle rectangle)
 {
     Rectangle intersection = new Rectangle();
     if (!Intersects(rectangle))
     {
         intersection.SetToEmpty();
         return intersection;
     }
     double l = Math.Max(Left, rectangle.Left);
     double r = Math.Min(Right, rectangle.Right);
     double b = Math.Max(Bottom, rectangle.Bottom);
     double t = Math.Min(Top, rectangle.Top);
     return new Rectangle(l,b,r,t);
 }

        public void PlaceNodesOnly(Rectangle bbox)
        {
            BoundingBox = bbox;
            int numInserted = 0;
            int level = 1;
            int iLevel = 0;

            while (numInserted < SortedLgNodeInfos.Count && level <= MaxLevel) {
                numInserted = DrawNodesOnlyOnLevel(level, numInserted);
                AddAllToNodeLevel(iLevel);
                level *= 2;
                iLevel++;
            }
        }

        void AddVoronoiCite(CdtTriangle triangle)
        {
            Point p;
            var goodTriangle = GetCenterOfDescribedCircle(triangle, out p);
            if (!goodTriangle)
                return;
            if (!BoundingBox.Contains(p))
                return;
            var rect=new Rectangle(p);
            rect.Pad(eps);
            if (voronoiSiteTree.GetAllIntersecting(rect).Count() > 0)
                return;

            voronoiSiteTree.Add(rect, p);
        }

        /// <summary>
        /// Verifies that the graph conforms to the correct aspect ratio.
        /// </summary>
        private static void VerifyAspectRatio(GeometryGraph graph, double aspectRatio)
        {
            double ratioTolerance = aspectRatio * 0.05;

            // Verify the graph is the correct size
            Assert.AreEqual(aspectRatio, (graph.Width-(graph.Margins*2)) / (graph.Height-(graph.Margins*2)), ratioTolerance, "The graph does not conform to the aspect ratio.");

            // Verify the nodes were spread apart to fill the space
            IEnumerable<Rectangle> nodeBoxes = graph.Nodes.Select(n => n.BoundingBox);
            IEnumerable<Rectangle> edgeBoxes = graph.Edges.Select(e => e.BoundingBox);
            IEnumerable<Rectangle> labelBoxes = graph.CollectAllLabels().Select(l => l.BoundingBox);
            
            Rectangle itemBounds = new Rectangle(nodeBoxes.Concat(edgeBoxes).Concat(labelBoxes));
            Assert.AreEqual(aspectRatio, itemBounds.Width / itemBounds.Height, ratioTolerance, "The graph's nodes do not conform to the aspect ratio.");
        }

        public static int GetOutCode(Rectangle rect, Point p) {
            int code = INSIDE;

            if (p.X < rect.Left)
                code |= LEFT;
            else if (p.X > rect.Right)
                code |= RIGHT;

            if (p.Y < rect.Bottom)
                code |= BOTTOM;
            else if (p.Y > rect.Top)
                code |= TOP;

            return code;
        }

        public static void RunTest2() {
            Point p1, p2;
            Rectangle rect1 = new Rectangle(1, 1, 4, 4);
            Point pc1, pc2;
            double a;


            p1 = new Point(-1, 0);
            p2 = new Point(2, 3);
            RectSegIntersection.ClipOnRect(rect1, p1, p2, out pc1, out pc2);

            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(1, 0);
            p2 = new Point(5, 4);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(0, 4);
            p2 = new Point(4, 0);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(0, 4);
            p2 = new Point(4, 0);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(1, 5);
            p2 = new Point(5, 1);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(0, 1);
            p2 = new Point(5, 4);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            p1 = new Point(-1, 3);
            p2 = new Point(2, 6);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);

            bool intersect;

            p1 = new Point(-1, 3);
            p2 = new Point(2, 6);
            intersect = RectSegIntersection.Intersect(rect1, p1, p2);

            p1 = new Point(1, 2);
            p2 = new Point(1, 3);
            intersect = RectSegIntersection.Intersect(rect1, p1, p2);
            a = RectSegIntersection.GetOverlapAmount(rect1, p1, p2);
        }

        internal static void PositionElement(FrameworkElement fe, Rectangle object_box, Rectangle bounding_box, double scale)
        {
            Microsoft.Msagl.Core.Geometry.Point origin = bounding_box.Center;
            double desiredH = object_box.Height * scale - fe.Margin.Top - fe.Margin.Bottom,
                   desiredW = object_box.Width * scale + fe.Margin.Left + fe.Margin.Right;

            if (bounding_box.Height < desiredH)
            {
                origin.Y += object_box.Center.Y * scale - fe.Margin.Top;
            }
            else
            {
                if (fe.VerticalAlignment == VerticalAlignment.Top)
                {
                    origin.Y = bounding_box.Top;
                }
                else if (fe.VerticalAlignment == VerticalAlignment.Bottom)
                {
                    origin.Y -= bounding_box.Height / 2 - object_box.Height * scale;
                }
                else
                {
                    origin.Y += object_box.Center.Y * scale;
                }
            }
            if (bounding_box.Width < desiredW)
            {
                origin.X -= object_box.Center.X * scale;
            }
            else
            {
                if (fe.HorizontalAlignment == HorizontalAlignment.Left)
                {
                    origin.X -= bounding_box.Width / 2 - fe.Margin.Left;
                }
                else if (fe.HorizontalAlignment == HorizontalAlignment.Right)
                {
                    origin.X -= bounding_box.Width / 2 - object_box.Width * scale;
                }
                else
                {
                    origin.X -= object_box.Center.X * scale;
                }
            }
            PositionElement(fe, origin, scale);
        }

        public static void RunTest1() {
            Rectangle rect1 = new Rectangle(0, 0, 2, 2);
            Rectangle rect2 = new Rectangle(3, 3, 4, 4);
            Rectangle rect3 = new Rectangle(4, 1, 5, 2);

            Rectangle[] moveableRectangles = {rect1, rect2, rect3};
            Rectangle[] fixedRectangles = {};
            SymmetricSegment[] fixedSegments = {};

            OverlapRemovalFixedSegmentsMst orfs = new OverlapRemovalFixedSegmentsMst(moveableRectangles, fixedRectangles,
                fixedSegments);
            orfs.InitCdt();

            double dist = orfs.GetDistance(rect1, rect2);

            var mstEdges = orfs.GetMstFromCdt();
        }