Ignore:
Timestamp:
Sep 18, 2010, 7:06:00 PM (11 years ago)
Author:
matkovic
Message:

-Added Pathfinding (experimental)
-Dijkstra algorithm added

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/CryptoLineView.cs

    r1834 r1923  
    1313using System.Collections.Generic;
    1414using System.Threading;
     15using WorkspaceManager.View.Container;
     16using System.Collections;
    1517
    1618namespace WorkspaceManager.View.VisualComponents
     
    273275        }
    274276
     277       
     278
     279        private bool isConnectionPossible(Point p1, Point p2)
     280        {
     281            if (p1.X != p2.X && p1.Y != p2.Y)
     282                throw new ArgumentException("only 90° allowed");
     283
     284            if (p1.Y != p2.Y)
     285            {
     286                Point up = p2.Y < p1.Y ? p1 : p2;
     287                Point down = p2.Y < p1.Y?p2 : p1;
     288
     289                Panel parent = (Parent as Panel);
     290                foreach (var element in parent.Children)
     291                {
     292                    PluginContainerView plug1 = element as PluginContainerView;
     293                    if (plug1 == null)
     294                        continue;
     295                    Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
     296
     297                    if (!isBetween(pos.X, pos.X + plug1.ActualWidth, up.X))
     298                        continue;
     299
     300                    // case 1: one point is inside the plugion
     301                    if (isBetween(pos.Y, pos.Y + plug1.ActualHeight, up.Y) ||
     302                        isBetween(pos.Y, pos.Y + plug1.ActualHeight, down.Y))
     303                    {
     304                        return false;
     305                    }
     306
     307                    // case 2: goes through
     308                    if (pos.Y > up.Y && pos.Y + plug1.ActualHeight < down.Y)
     309                    {
     310                        return false;
     311                    }
     312                }
     313            }
     314            else
     315            {
     316                Point left = p2.X < p1.X ? p2 : p1;
     317                Point right = p2.X < p1.X ? p1 : p2;
     318
     319                Panel parent = (Parent as Panel);
     320                foreach (var element in parent.Children)
     321                {
     322                    PluginContainerView plug1 = element as PluginContainerView;
     323                    if (plug1 == null)
     324                        continue;
     325                    Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
     326
     327                    if (!isBetween(pos.Y, pos.Y + plug1.ActualHeight, left.Y))
     328                        continue;
     329
     330                    // case 1: one point is inside the plugion
     331                    if(isBetween(pos.X, pos.X + plug1.ActualWidth, left.X) ||
     332                        isBetween(pos.X, pos.X + plug1.ActualWidth, right.X))
     333                    {
     334                        return false;
     335                    }
     336
     337                    // case 2: goes through
     338                    if(pos.X > left.X && pos.X + plug1.ActualWidth < right.X)
     339                    {
     340                        return false;
     341                    }
     342                }
     343            }
     344
     345            return true;
     346        }
     347
     348        internal class Node : StackFrameDijkstra.Node<Node>
     349        {
     350            public Point Point { get; set; }
     351            public HashSet<Node> Vertices { get; private set; }
     352            public Node()
     353            {
     354                Vertices = new HashSet<Node>();
     355            }
     356
     357            public double pathCostEstimate(Node goal)
     358            {
     359                return 0;
     360            }
     361
     362            public double traverseCost(Node dest)
     363            {
     364                if (!Vertices.Contains(dest))
     365                    return Double.PositiveInfinity;
     366
     367                if (dest.Point.X == Point.X)
     368                    return Math.Abs(dest.Point.Y - Point.Y);
     369                return Math.Abs(dest.Point.X - Point.X);
     370            }
     371
     372            public IEnumerable<Node> neighbors()
     373            {
     374                return Vertices;
     375            }
     376        }
     377
     378        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList)
     379        {
     380            if (isConnectionPossible(n1.Point, p2) && isConnectionPossible(p2, n3.Point))
     381            {
     382                Node n2 = new Node() { Point = p2 };
     383                n1.Vertices.Add(n2);
     384
     385                n2.Vertices.Add(n1);
     386                n2.Vertices.Add(n3);
     387
     388                n3.Vertices.Add(n2);
     389
     390                nodeList.Add(n2);
     391                return true;
     392            }
     393            return false;
     394        }
     395
     396        private void performOrthogonalPointConnection(Node p1, Node p2)
     397        {
     398            if (isConnectionPossible(p1.Point, p2.Point))
     399            {
     400                p1.Vertices.Add(p2);
     401                p2.Vertices.Add(p1);
     402            }
     403        }
     404
    275405        private void makeOrthogonalPoints()
    276406        {
    277             if (StartPoint.X < EndPoint.X)
     407            List<Node> nodeList = new List<Node>();
     408            Panel parent = (Parent as Panel);
     409
     410            // add start and end. Index will be 0 and 1
     411            Node startNode = new Node() { Point = StartPoint },
     412                endNode = new Node() { Point = EndPoint };
     413            nodeList.Add(startNode);
     414            nodeList.Add(endNode);
     415
     416            foreach (var element in parent.Children)
     417            {
     418                if (element is PluginContainerView)
     419                {
     420                    PluginContainerView p1 = element as PluginContainerView;
     421                    foreach (var routPoint in p1.RoutingPoints)
     422                    {
     423                        nodeList.Add(new Node() { Point = routPoint });
     424                    }
     425                }
     426            }
     427           
     428            // connect points
     429            int loopCount = nodeList.Count;
     430            for(int i=0; i<loopCount; ++i)
     431            {
     432                var p1 = nodeList[i];
     433                // TODO: inner loop restriction! n²-n!
     434                // is k=i instead of k=0 correct?
     435                for(int k=0; k<loopCount; ++k)
     436                {
     437                    var p2 = nodeList[k];
     438                    if (p1 == p2)
     439                        continue;
     440                    if (p1.Vertices.Contains(p2))
     441                        continue;
     442
     443                    // no helping point required?
     444                    if (p1.Point.X == p2.Point.X ||
     445                        p1.Point.Y == p2.Point.Y)
     446                    {
     447                        performOrthogonalPointConnection(p1, p2);
     448                    }
     449                    else
     450                    {
     451                        Point help1 = new Point(p1.Point.X, p2.Point.Y);
     452
     453                        if (!performOrthogonalPointConnection(p1, help1, p2, nodeList))
     454                        {
     455                            Point help2 = new Point(p2.Point.X, p1.Point.Y);
     456                            performOrthogonalPointConnection(p1, help2, p2, nodeList);
     457                            // optinal TODO: other possible helping points
     458                        }
     459                       
     460                    }
     461                }
     462            }
     463
     464            StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
     465            var path = dijkstra.findPath(nodeList, startNode, endNode);
     466
     467            if (path != null)
     468            {
     469                pointList.Clear();
     470                Point prevPoint = StartPoint;
     471
     472                foreach (var i in path)
     473                {
     474                    Point thisPoint = i.Point;
     475                    this.pointList.Add(new FromTo(prevPoint, thisPoint));
     476                    prevPoint = thisPoint;
     477                }
     478            }
     479                //Failsafe
     480            else if (StartPoint.X < EndPoint.X)
    278481            {
    279482                pointList.Clear();
Note: See TracChangeset for help on using the changeset viewer.