Ignore:
Timestamp:
Sep 19, 2010, 1:52:32 AM (11 years ago)
Author:
matkovic
Message:

-Pathfinding algorithm optimized

File:
1 edited

Legend:

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

    r1924 r1926  
    7878                line.InvalidateVisual();
    7979            }
     80
     81            Panel p = (this.Parent as Panel);
     82            if (p == null)
     83                return;
     84            foreach (UIElement shape in p.Children)
     85            {
     86                if (shape is CryptoLineView)
     87                    shape.InvalidateVisual();
     88            }
    8089        }
    8190
     
    139148            }
    140149
    141             // parallel
     150            // parallel, also overlapping case
    142151            if (StartPoint.X == EndPoint.X && StartPointSec.X == EndPointSec.X ||
    143152                StartPoint.Y == EndPoint.Y && StartPointSec.Y == EndPointSec.Y)
     
    147156            else
    148157            {
    149                 // orthonogal
     158                // orthogonal but maybe not intersected
    150159                Point up, down, left, right;
    151160                if (StartPoint.X == EndPoint.X)
     
    276285
    277286
    278         private bool isConnectionPossibleDebugWrapper(Point p1, Point p2)
    279         {
    280             bool a = isConnectionPossible(p1, p2);
    281             bool b = isConnectionPossible(p2, p1);
    282             if (a != b)
    283             {
    284                 throw new Exception("State pew!");
    285             }
    286             return a;
    287         }
     287     
    288288        private bool isConnectionPossible(Point p1, Point p2)
    289289        {
     
    382382        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList)
    383383        {
    384             if (isConnectionPossibleDebugWrapper(n1.Point, p2) && isConnectionPossibleDebugWrapper(p2, n3.Point))
     384            if (isConnectionPossible(n1.Point, p2) && isConnectionPossible(p2, n3.Point))
    385385            {
    386386                Node n2 = new Node() { Point = p2 };
     
    400400        private void performOrthogonalPointConnection(Node p1, Node p2)
    401401        {
    402             if (isConnectionPossibleDebugWrapper(p1.Point, p2.Point))
     402            if (isConnectionPossible(p1.Point, p2.Point))
    403403            {
    404404                p1.Vertices.Add(p2);
     
    432432            // connect points
    433433            int loopCount = nodeList.Count;
     434            const int performanceTradeoffAt = 10;
     435
     436            LinkedList<Node> path = null;
     437
    434438            for(int i=0; i<loopCount; ++i)
    435439            {
     440                if (performanceTradeoffAt != 0 &&
     441                       i == performanceTradeoffAt)
     442                {
     443                    StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
     444                    path = dijkstra.findPath(nodeList, startNode, endNode);
     445                    if (path != null)
     446                    {
     447                        break;
     448                    }
     449                }
     450
    436451                var p1 = nodeList[i];
    437452                // TODO: inner loop restriction! n²-n!
     
    439454                for(int k=i; k<loopCount; ++k)
    440455                {
     456                   
     457
    441458                    var p2 = nodeList[k];
    442459                    if (p1 == p2)
     
    468485            }
    469486
    470             StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
    471             var path = dijkstra.findPath(nodeList, startNode, endNode);
     487            if (path == null)
     488            {
     489                StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
     490                path = dijkstra.findPath(nodeList, startNode, endNode);
     491            }
    472492
    473493            if (path != null)
Note: See TracChangeset for help on using the changeset viewer.