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

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

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 19.6 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, QuadTreeLib.QuadTree<FakeNode> quadTree)
289        {
290            if (p1.X != p2.X && p1.Y != p2.Y)
291                throw new ArgumentException("only 90° allowed");
292
293            System.Drawing.RectangleF queryRect;
294            if (p1.Y != p2.Y)
295            {
296                Point up = p2.Y < p1.Y ? p2 : p1;
297                Point down = p2.Y < p1.Y?p1 : p2;
298
299                queryRect = new System.Drawing.RectangleF((float)up.X, (float)up.Y, 1, (float)(down.Y - up.Y));
300            }
301            else
302            {
303                Point left = p2.X < p1.X ? p2 : p1;
304                Point right = p2.X < p1.X ? p1 : p2;
305
306                queryRect = new System.Drawing.RectangleF((float)left.X, (float)left.Y, (float)(right.X-left.X), 1);
307            }
308
309            return !quadTree.QueryAny(queryRect);
310        }
311
312        internal class Node : StackFrameDijkstra.Node<Node>
313        {
314            public Point Point { get; set; }
315            public HashSet<Node> Vertices { get; private set; }
316            public Node()
317            {
318                Vertices = new HashSet<Node>();
319            }
320
321            public double traverseCost(Node dest)
322            {
323                if (!Vertices.Contains(dest))
324                    return Double.PositiveInfinity;
325
326                if (dest.Point.X == Point.X)
327                    return Math.Abs(dest.Point.Y - Point.Y);
328                return Math.Abs(dest.Point.X - Point.X);
329            }
330
331            public IEnumerable<Node> neighbors()
332            {
333                return Vertices;
334            }
335        }
336
337        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList, QuadTreeLib.QuadTree<FakeNode> quadTree)
338        {
339            if (isConnectionPossible(n1.Point, p2, quadTree) && isConnectionPossible(p2, n3.Point, quadTree))
340            {
341                Node n2 = new Node() { Point = p2 };
342                n1.Vertices.Add(n2);
343
344                n2.Vertices.Add(n1);
345                n2.Vertices.Add(n3);
346
347                n3.Vertices.Add(n2);
348
349                nodeList.Add(n2);
350                return true;
351            }
352            return false;
353        }
354
355        private void performOrthogonalPointConnection(Node p1, Node p2, QuadTreeLib.QuadTree<FakeNode> quadTree)
356        {
357            if (isConnectionPossible(p1.Point, p2.Point, quadTree))
358            {
359                p1.Vertices.Add(p2);
360                p2.Vertices.Add(p1);
361            }
362        }
363        internal class FakeNode : QuadTreeLib.IHasRect
364        {
365            public System.Drawing.RectangleF Rectangle { get; set; }
366        }
367        private void makeOrthogonalPoints()
368        {
369            List<Node> nodeList = new List<Node>();
370            Panel parent = (Parent as Panel);
371
372            // add start and end. Index will be 0 and 1
373            Node startNode = new Node() { Point = StartPoint },
374                endNode = new Node() { Point = EndPoint };
375            nodeList.Add(startNode);
376            nodeList.Add(endNode);
377
378            QuadTreeLib.QuadTree<FakeNode> quadTree = new QuadTreeLib.QuadTree<FakeNode>(new System.Drawing.RectangleF(0,0,(float)parent.ActualWidth,(float) parent.ActualHeight));
379
380            foreach (var element in parent.Children)
381            {
382                if (element is PluginContainerView)
383                {
384                    PluginContainerView p1 = element as PluginContainerView;
385                    foreach (var routPoint in p1.RoutingPoints)
386                    {
387                        nodeList.Add(new Node() { Point = routPoint });
388                    }
389                    quadTree.Insert(new FakeNode() { Rectangle = new System.Drawing.RectangleF((float)(p1.RenderTransform as TranslateTransform).X,
390                                                                                                (float)(p1.RenderTransform as TranslateTransform).Y,
391                                                                                                (float)p1.ActualWidth,
392                                                                                                (float)p1.ActualHeight)});
393                }
394            }
395           
396            // connect points
397            int loopCount = nodeList.Count;
398            const int performanceTradeoffAt = 10;
399
400            LinkedList<Node> path = null;
401
402            for(int i=0; i<loopCount; ++i)
403            {
404                if (performanceTradeoffAt != 0 &&
405                       i == performanceTradeoffAt)
406                {
407                    StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
408                    path = dijkstra.findPath(nodeList, startNode, endNode);
409                    if (path != null)
410                    {
411                        break;
412                    }
413                }
414
415                var p1 = nodeList[i];
416                // TODO: inner loop restriction! n²-n!
417                // is k=i instead of k=0 correct?
418                for(int k=i; k<loopCount; ++k)
419                {
420                   
421
422                    var p2 = nodeList[k];
423                    if (p1 == p2)
424                        continue;
425                    if (p1.Vertices.Contains(p2))
426                        continue;
427
428                    // no helping point required?
429                    if (p1.Point.X == p2.Point.X ||
430                        p1.Point.Y == p2.Point.Y)
431                    {
432                        performOrthogonalPointConnection(p1, p2, quadTree);
433                    }
434                    else
435                    {
436                        Point help = new Point(p1.Point.X, p2.Point.Y);
437
438                        if (!performOrthogonalPointConnection(p1, help, p2, nodeList, quadTree ))
439                        {
440                            help = new Point(p2.Point.X, p1.Point.Y);
441                            if (!performOrthogonalPointConnection(p1, help, p2, nodeList, quadTree))
442                            {
443                                // optional todo: double edge helping routes
444                            }
445                        }
446                       
447                    }
448                }
449            }
450
451            if (path == null)
452            {
453                StackFrameDijkstra.Dijkstra<Node> dijkstra = new StackFrameDijkstra.Dijkstra<Node>();
454                path = dijkstra.findPath(nodeList, startNode, endNode);
455            }
456
457            if (path != null)
458            {
459                pointList.Clear();
460                Point prevPoint = StartPoint;
461
462                foreach (var i in path)
463                {
464                    Point thisPoint = i.Point;
465                    this.pointList.Add(new FromTo(prevPoint, thisPoint));
466                    prevPoint = thisPoint;
467                }
468            }
469                //Failsafe
470            else if (StartPoint.X < EndPoint.X)
471            {
472                pointList.Clear();
473                pointList.Add(new FromTo(StartPoint, new Point((EndPoint.X + StartPoint.X) / 2, StartPoint.Y)));
474                pointList.Add(new FromTo(new Point((EndPoint.X + StartPoint.X) / 2, StartPoint.Y), new Point((EndPoint.X + StartPoint.X) / 2, EndPoint.Y)));
475                pointList.Add(new FromTo(new Point((EndPoint.X + StartPoint.X) / 2, EndPoint.Y), EndPoint));
476            }
477            else
478            {
479                if (StartPoint.X > EndPoint.X)
480                {
481                    pointList.Clear();
482                    pointList.Add(new FromTo(StartPoint, new Point((StartPoint.X + EndPoint.X) / 2, StartPoint.Y)));
483                    pointList.Add(new FromTo(new Point((StartPoint.X + EndPoint.X) / 2, StartPoint.Y), new Point((StartPoint.X + EndPoint.X) / 2, EndPoint.Y)));
484                    pointList.Add(new FromTo(new Point((StartPoint.X + EndPoint.X) / 2, EndPoint.Y), EndPoint));
485                }
486            }
487        }
488               
489                #endregion
490
491        #region IUpdateableView Members
492
493        public void update()
494        {
495            Stroke = Brushes.Green;
496        }
497
498        #endregion
499
500        internal void Reset()
501        {
502            Color color = ColorHelper.GetColor(Model.ConnectionType);
503            Stroke = new SolidColorBrush(color);
504        }
505    }
506}
Note: See TracBrowser for help on using the repository browser.