source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/CryptoLineView.cs @ 1926

Last change on this file since 1926 was 1926, checked in by matkovic, 11 years ago

-Pathfinding algorithm optimized

File size: 20.4 KB
Line 
1using System;
2using System.ComponentModel;
3using System.Windows;
4using System.Windows.Media;
5using System.Windows.Input;
6using System.Windows.Controls;
7using System.Windows.Shapes;
8using System.Reflection;
9using System.Windows.Threading;
10using WorkspaceManager.View.Interface;
11using WorkspaceManager.Model;
12using System.Windows.Documents;
13using System.Collections.Generic;
14using System.Threading;
15using WorkspaceManager.View.Container;
16using System.Collections;
17
18namespace WorkspaceManager.View.VisualComponents
19{
20        public sealed class CryptoLineView : Shape, IConnection, IUpdateableView
21    {
22        #region Variables
23
24        private IntersectPoint intersectPoint;
25        private List<FromTo> pointList = new List<FromTo>();
26        public HashSet<CryptoLineView> UpdateList = new HashSet<CryptoLineView>();
27
28        private ConnectionModel model;
29        public ConnectionModel Model
30        {
31            get { return model; }
32            private set { model = value; }
33        }
34        private static double offset = 6;
35
36        #endregion
37
38        #region Dependency Properties
39
40        public static readonly DependencyProperty StartPointProperty = DependencyProperty.Register("StartPoint", typeof(Point), typeof(CryptoLineView), new FrameworkPropertyMetadata(new Point(0, 0), FrameworkPropertyMetadataOptions.AffectsRender | FrameworkPropertyMetadataOptions.AffectsMeasure));
41        public static readonly DependencyProperty EndPointProperty = DependencyProperty.Register("EndPoint", typeof(Point), typeof(CryptoLineView), new FrameworkPropertyMetadata(new Point(0, 0), FrameworkPropertyMetadataOptions.AffectsRender | FrameworkPropertyMetadataOptions.AffectsMeasure));
42
43                #endregion
44
45                #region CLR Properties
46
47        public Point StartPoint
48        {
49            get { return (Point)GetValue(StartPointProperty); }
50            set 
51            {
52                SetValue(StartPointProperty, value);
53            }
54        }
55
56        public Point EndPoint
57        {
58            get { return (Point)GetValue(EndPointProperty); }
59            set 
60            {
61                SetValue(EndPointProperty, value);
62            }
63        }
64
65                #endregion
66
67        public CryptoLineView()
68        {
69            Stroke = Brushes.Black;
70            StrokeThickness = 2;
71        }
72
73        protected override void OnPropertyChanged(DependencyPropertyChangedEventArgs e)
74        {
75            base.OnPropertyChanged(e);
76            foreach (CryptoLineView line in UpdateList)
77            {
78                line.InvalidateVisual();
79            }
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            }
89        }
90
91        protected override void OnMouseDown(MouseButtonEventArgs args)
92        {
93            if (args.RightButton == MouseButtonState.Pressed)
94            {
95                if (this.model != null && !this.model.WorkspaceModel.WorkspaceManagerEditor.isExecuting())
96                {
97                    this.model.WorkspaceModel.deleteConnectionModel(this.model);
98                }
99            }           
100        }
101
102        public CryptoLineView(ConnectionModel connectionModel) : this()
103        {
104            this.Model = connectionModel;
105            Color color = ColorHelper.GetColor(connectionModel.ConnectionType);
106            Stroke = new SolidColorBrush(color);
107            StrokeThickness = 2;
108        }
109
110                #region Overrides
111
112                protected override Geometry DefiningGeometry
113                {
114                        get
115                        {
116                                StreamGeometry geometry = new StreamGeometry();
117                                geometry.FillRule = FillRule.EvenOdd;
118
119                                using (StreamGeometryContext context = geometry.Open())
120                                {
121                    internalGeometryDraw(context);
122                                }
123
124                                geometry.Freeze();
125                                return geometry;
126                        }
127                }               
128
129                #endregion
130
131                #region Privates
132        private bool isBetween(double min, double max, double between)
133        {
134            return min <= between && between <= max;
135        }
136
137        private bool findIntersection(Point StartPoint, Point EndPoint, Point StartPointSec, Point EndPointSec)
138        {
139            if (StartPoint.X != EndPoint.X &&
140                StartPoint.Y != EndPoint.Y)
141            {
142                return false;
143            }
144            if (StartPointSec.X != EndPointSec.X &&
145                StartPointSec.Y != EndPointSec.Y)
146            {
147                return false;
148            }
149
150            // parallel, also overlapping case
151            if (StartPoint.X == EndPoint.X && StartPointSec.X == EndPointSec.X ||
152                StartPoint.Y == EndPoint.Y && StartPointSec.Y == EndPointSec.Y)
153            {
154                return false;
155            }
156            else
157            {
158                // orthogonal but maybe not intersected
159                Point up, down, left, right;
160                if (StartPoint.X == EndPoint.X)
161                {
162                    up = StartPoint;
163                    down = EndPoint;
164                    left = StartPointSec;
165                    right = EndPointSec;
166                }
167                else
168                {
169                    up = StartPointSec;
170                    down = EndPointSec;
171                    left = StartPoint;
172                    right = EndPoint;
173                }
174
175                if (up.Y < down.Y)
176                {
177                    double swap = up.Y;
178                    up.Y = down.Y;
179                    down.Y = swap;
180                }
181
182                if (left.X > right.X)
183                {
184                    double swap = left.X;
185                    left.X = right.X;
186                    right.X = swap;
187                }
188                 //check if is intersected at all
189                if(isBetween(down.Y, up.Y, left.Y) && isBetween(left.X, right.X, up.X))
190                {
191                    if (up.Y == left.Y ||
192                        down.Y == left.Y ||
193                        left.X == up.X || right.X == up.X)
194                    {
195                        intersectPoint = new IntersectPoint(new Point(up.X, left.Y), IntersectPointMode.InnerIntersect);
196                    }
197                    else
198                    {
199                        intersectPoint = new IntersectPoint(new Point(up.X, left.Y), IntersectPointMode.NormalIntersect);
200                    }
201                    return true;
202                }
203                return false;
204            }
205        }
206
207                private void internalGeometryDraw(StreamGeometryContext context)
208                {
209            makeOrthogonalPoints();
210            foreach (var element in (Parent as Panel).Children)
211            {
212                if (element is CryptoLineView && !element.Equals(this))
213                {
214                    CryptoLineView result = element as CryptoLineView;
215                    foreach (FromTo fromTo in pointList)
216                    {
217                        foreach (FromTo resultFromTo in result.pointList)
218                        {
219                            if (findIntersection(fromTo.From, fromTo.To, resultFromTo.From, resultFromTo.To))
220                            {
221                                fromTo.Intersection.Add(intersectPoint);
222
223                                if (fromTo.DirSort == DirSort.Y_ASC || fromTo.DirSort == DirSort.Y_DESC)
224                                    this.UpdateList.Add(result);
225                            }
226                        }
227                    }
228                }
229            }
230
231            context.BeginFigure(StartPoint, true, false);
232
233            foreach (FromTo fromTo in pointList)
234            {
235                if (fromTo.Intersection.Count > 0)
236                {
237                    foreach (IntersectPoint interPoint in fromTo.Intersection)
238                    {
239                        switch (fromTo.DirSort)
240                        {
241                            case DirSort.X_ASC:
242                                if (interPoint.Mode == IntersectPointMode.NormalIntersect)
243                                {
244                                    context.LineTo(new Point(interPoint.Point.X - offset, interPoint.Point.Y), true, true);
245                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y - offset), new Point(interPoint.Point.X + offset, interPoint.Point.Y), true, true);
246                                }
247                                else if (interPoint.Mode == IntersectPointMode.InnerIntersect)
248                                {
249                                    context.LineTo(new Point(interPoint.Point.X - 4, interPoint.Point.Y), true, true);
250                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y - 5), new Point(interPoint.Point.X + 4, interPoint.Point.Y), true, true);
251                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y + 5), new Point(interPoint.Point.X - 4, interPoint.Point.Y), true, true);
252                                }
253                                break;
254                            case DirSort.X_DESC:
255                                if (interPoint.Mode == IntersectPointMode.NormalIntersect)
256                                {
257                                    context.LineTo(new Point(interPoint.Point.X + offset, interPoint.Point.Y), true, true);
258                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y - offset), new Point(interPoint.Point.X - offset, interPoint.Point.Y), true, true);
259                                }
260                                else if (interPoint.Mode == IntersectPointMode.InnerIntersect)
261                                {
262                                    context.LineTo(new Point(interPoint.Point.X + 4, interPoint.Point.Y), true, true);
263                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y - 5), new Point(interPoint.Point.X - 4, interPoint.Point.Y), true, true);
264                                    context.QuadraticBezierTo(new Point(interPoint.Point.X, interPoint.Point.Y + 5), new Point(interPoint.Point.X + 4, interPoint.Point.Y), true, true);
265                                }
266                                break;
267                            //case DirSort.Y_ASC:
268                            //    context.LineTo(new Point(interPoint.X, interPoint.Y - offset), true, true);
269                            //    context.QuadraticBezierTo(new Point(interPoint.X + offset, interPoint.Y), new Point(interPoint.X, interPoint.Y + offset), true, true);
270                            //    break;
271                            //case DirSort.Y_DESC:
272                            //    context.LineTo(new Point(interPoint.X, interPoint.Y + offset), true, true);
273                            //    context.QuadraticBezierTo(new Point(interPoint.X + offset, interPoint.Y), new Point(interPoint.X, interPoint.Y - offset), true, true);
274                            //    break;
275                        }
276                    }
277                    context.LineTo(fromTo.To, true, true);
278                }
279                else
280                {
281                    context.LineTo(fromTo.To, true, true);
282                }
283            }
284        }
285
286
287     
288        private bool isConnectionPossible(Point p1, Point p2)
289        {
290            if (p1.X != p2.X && p1.Y != p2.Y)
291                throw new ArgumentException("only 90° allowed");
292
293            if (p1.Y != p2.Y)
294            {
295                Point up = p2.Y < p1.Y ? p2 : p1;
296                Point down = p2.Y < p1.Y?p1 : p2;
297
298                Panel parent = (Parent as Panel);
299                foreach (var element in parent.Children)
300                {
301                    PluginContainerView plug1 = element as PluginContainerView;
302                    if (plug1 == null)
303                        continue;
304                    Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
305
306                    if (!isBetween(pos.X, pos.X + plug1.ActualWidth, up.X))
307                        continue;
308
309                    // case 1: one point is inside the plugin
310                    if (isBetween(pos.Y, pos.Y + plug1.ActualHeight, up.Y) ||
311                        isBetween(pos.Y, pos.Y + plug1.ActualHeight, down.Y))
312                    {
313                        return false;
314                    }
315
316                    // case 2: goes through
317                    if (pos.Y > up.Y && pos.Y + plug1.ActualHeight < down.Y)
318                    {
319                        return false;
320                    }
321                }
322            }
323            else
324            {
325                Point left = p2.X < p1.X ? p2 : p1;
326                Point right = p2.X < p1.X ? p1 : p2; 
327
328                Panel parent = (Parent as Panel);
329                foreach (var element in parent.Children)
330                {
331                    PluginContainerView plug1 = element as PluginContainerView;
332                    if (plug1 == null)
333                        continue;
334                    Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
335
336                    if (!isBetween(pos.Y, pos.Y + plug1.ActualHeight, left.Y))
337                        continue;
338
339                    // case 1: one point is inside the plugin
340                    if(isBetween(pos.X, pos.X + plug1.ActualWidth, left.X) ||
341                        isBetween(pos.X, pos.X + plug1.ActualWidth, right.X))
342                    {
343                        return false;
344                    }
345
346                    // case 2: goes through
347                    if(pos.X > left.X && pos.X + plug1.ActualWidth < right.X)
348                    {
349                        return false;
350                    }
351                }
352            }
353
354            return true;
355        }
356
357        internal class Node : StackFrameDijkstra.Node<Node>
358        {
359            public Point Point { get; set; }
360            public HashSet<Node> Vertices { get; private set; }
361            public Node()
362            {
363                Vertices = new HashSet<Node>();
364            }
365
366            public double traverseCost(Node dest)
367            {
368                if (!Vertices.Contains(dest))
369                    return Double.PositiveInfinity;
370
371                if (dest.Point.X == Point.X)
372                    return Math.Abs(dest.Point.Y - Point.Y);
373                return Math.Abs(dest.Point.X - Point.X);
374            }
375
376            public IEnumerable<Node> neighbors()
377            {
378                return Vertices;
379            }
380        }
381
382        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList)
383        {
384            if (isConnectionPossible(n1.Point, p2) && isConnectionPossible(p2, n3.Point))
385            {
386                Node n2 = new Node() { Point = p2 };
387                n1.Vertices.Add(n2);
388
389                n2.Vertices.Add(n1);
390                n2.Vertices.Add(n3);
391
392                n3.Vertices.Add(n2);
393
394                nodeList.Add(n2);
395                return true;
396            }
397            return false;
398        }
399
400        private void performOrthogonalPointConnection(Node p1, Node p2)
401        {
402            if (isConnectionPossible(p1.Point, p2.Point))
403            {
404                p1.Vertices.Add(p2);
405                p2.Vertices.Add(p1);
406            }
407        }
408
409        private void makeOrthogonalPoints()
410        {
411            List<Node> nodeList = new List<Node>();
412            Panel parent = (Parent as Panel);
413
414            // add start and end. Index will be 0 and 1
415            Node startNode = new Node() { Point = StartPoint },
416                endNode = new Node() { Point = EndPoint };
417            nodeList.Add(startNode);
418            nodeList.Add(endNode);
419
420            foreach (var element in parent.Children)
421            {
422                if (element is PluginContainerView)
423                {
424                    PluginContainerView p1 = element as PluginContainerView;
425                    foreach (var routPoint in p1.RoutingPoints)
426                    {
427                        nodeList.Add(new Node() { Point = routPoint });
428                    }
429                }
430            }
431           
432            // connect points
433            int loopCount = nodeList.Count;
434            const int performanceTradeoffAt = 10;
435
436            LinkedList<Node> path = null;
437
438            for(int i=0; i<loopCount; ++i)
439            {
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
451                var p1 = nodeList[i];
452                // TODO: inner loop restriction! n²-n!
453                // is k=i instead of k=0 correct?
454                for(int k=i; k<loopCount; ++k)
455                {
456                   
457
458                    var p2 = nodeList[k];
459                    if (p1 == p2)
460                        continue;
461                    if (p1.Vertices.Contains(p2))
462                        continue;
463
464                    // no helping point required?
465                    if (p1.Point.X == p2.Point.X ||
466                        p1.Point.Y == p2.Point.Y)
467                    {
468                        performOrthogonalPointConnection(p1, p2);
469                    }
470                    else
471                    {
472                        Point help = new Point(p1.Point.X, p2.Point.Y);
473
474                        if (!performOrthogonalPointConnection(p1, help, p2, nodeList))
475                        {
476                            help = new Point(p2.Point.X, p1.Point.Y);
477                            if (!performOrthogonalPointConnection(p1, help, p2, nodeList))
478                            {
479                                // optional todo: double edge helping routes
480                            }
481                        }
482                       
483                    }
484                }
485            }
486
487            if (path == null)
488            {
489                StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
490                path = dijkstra.findPath(nodeList, startNode, endNode);
491            }
492
493            if (path != null)
494            {
495                pointList.Clear();
496                Point prevPoint = StartPoint;
497
498                foreach (var i in path)
499                {
500                    Point thisPoint = i.Point;
501                    this.pointList.Add(new FromTo(prevPoint, thisPoint));
502                    prevPoint = thisPoint;
503                }
504            }
505                //Failsafe
506            else if (StartPoint.X < EndPoint.X)
507            {
508                pointList.Clear();
509                pointList.Add(new FromTo(StartPoint, new Point((EndPoint.X + StartPoint.X) / 2, StartPoint.Y)));
510                pointList.Add(new FromTo(new Point((EndPoint.X + StartPoint.X) / 2, StartPoint.Y), new Point((EndPoint.X + StartPoint.X) / 2, EndPoint.Y)));
511                pointList.Add(new FromTo(new Point((EndPoint.X + StartPoint.X) / 2, EndPoint.Y), EndPoint));
512            }
513            else
514            {
515                if (StartPoint.X > EndPoint.X)
516                {
517                    pointList.Clear();
518                    pointList.Add(new FromTo(StartPoint, new Point((StartPoint.X + EndPoint.X) / 2, StartPoint.Y)));
519                    pointList.Add(new FromTo(new Point((StartPoint.X + EndPoint.X) / 2, StartPoint.Y), new Point((StartPoint.X + EndPoint.X) / 2, EndPoint.Y)));
520                    pointList.Add(new FromTo(new Point((StartPoint.X + EndPoint.X) / 2, EndPoint.Y), EndPoint));
521                }
522            }
523        }
524               
525                #endregion
526
527        #region IUpdateableView Members
528
529        public void update()
530        {
531            Stroke = Brushes.Green;
532        }
533
534        #endregion
535
536        internal void Reset()
537        {
538            Color color = ColorHelper.GetColor(Model.ConnectionType);
539            Stroke = new SolidColorBrush(color);
540        }
541    }
542}
Note: See TracBrowser for help on using the repository browser.