bundles/org.simantics.g2d/src/org/simantics/g2d/elementclass/connection/ConnectionValidator.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.g2d.elementclass.connection;\r
  13 \r
  14 import java.awt.geom.AffineTransform;\r
  15 import java.awt.geom.Path2D;\r
  16 import java.awt.geom.PathIterator;\r
  17 import java.awt.geom.Point2D;\r
  18 import java.awt.geom.Rectangle2D;\r
  19 import java.util.ArrayList;\r
  20 import java.util.Collection;\r
  21 import java.util.HashSet;\r
  22 import java.util.Iterator;\r
  23 import java.util.LinkedList;\r
  24 import java.util.List;\r
  25 import java.util.Set;\r
  26 \r
  27 import org.simantics.g2d.canvas.ICanvasContext;\r
  28 import org.simantics.g2d.diagram.IDiagram;\r
  29 import org.simantics.g2d.diagram.handler.Topology;\r
  30 import org.simantics.g2d.diagram.handler.Validator;\r
  31 import org.simantics.g2d.diagram.handler.Topology.Connection;\r
  32 import org.simantics.g2d.diagram.handler.impl.DiagramIssue;\r
  33 import org.simantics.g2d.diagram.participant.pointertool.TerminalUtil;\r
  34 import org.simantics.g2d.element.ElementUtils;\r
  35 import org.simantics.g2d.element.IElement;\r
  36 import org.simantics.g2d.element.handler.BendsHandler;\r
  37 import org.simantics.g2d.element.handler.EdgeVisuals;\r
  38 import org.simantics.g2d.element.handler.BendsHandler.AngleType;\r
  39 import org.simantics.g2d.element.handler.BendsHandler.Bend;\r
  40 import org.simantics.g2d.element.handler.EdgeVisuals.EdgeEnd;\r
  41 import org.simantics.g2d.routing.algorithm1.Rectangle;\r
  42 import org.simantics.g2d.utils.GeometryUtils;\r
  43 import org.simantics.g2d.utils.PathUtils;\r
  44 import org.simantics.g2d.utils.geom.DirectionSet;\r
  45 import org.simantics.utils.datastructures.TreeProblem;\r
  46 import org.simantics.utils.datastructures.TreeProblem.ProblemNode;\r
  47 \r
  48 /**\r
  49  * Checks whether Topology meets geometry  \r
  50  * \r
  51  * @author Toni Kalajainen\r
  52  */\r
  53 public class ConnectionValidator implements Validator {\r
  54 \r
  55 \r
  56 \r
  57         public static final ConnectionValidator INSTANCE = new ConnectionValidator(); \r
  58         private static final double TOLERANCE = 0.001;\r
  59         \r
  60         private static final Suggestion DISCONNECT_EDGES = new Suggestion() {\r
  61                 @Override\r
  62                 public boolean fix(IDiagram d, ICanvasContext ctx) {                    \r
  63                         return false;\r
  64                 }\r
  65                 @Override\r
  66                 public String getMessage() {\r
  67                         return "Disconnect edges";\r
  68                 }\r
  69         };\r
  70         \r
  71         public static final double OBSTACLE_MARGINAL = 10.0; \r
  72         \r
  73         static Collection<Rectangle> createObstacles(IDiagram d) {\r
  74                 ArrayList<Rectangle> obstacles = new ArrayList<Rectangle>();\r
  75                 for(IElement e : d.getElements())\r
  76                 {\r
  77                         if (e.getElementClass().containsClass(EdgeVisuals.class)) continue;\r
  78                         Rectangle2D rect = ElementUtils.getElementBounds(e);\r
  79                         obstacles.add(new Rectangle(\r
  80                                 rect.getMinX()-OBSTACLE_MARGINAL,\r
  81                                 rect.getMinY()-OBSTACLE_MARGINAL,\r
  82                                 rect.getMaxX()+OBSTACLE_MARGINAL,\r
  83                                 rect.getMaxY()+OBSTACLE_MARGINAL\r
  84                         ));\r
  85                 }\r
  86                 return obstacles;\r
  87         }\r
  88         \r
  89         // Force path to follow its path requirements \r
  90         private static final Suggestion FORCE_PATH_TO_REQUIREMENTS = new Suggestion() {\r
  91                 @Override\r
  92                 public boolean fix(IDiagram d, ICanvasContext ctx) {\r
  93                         \r
  94                         // Get all edges\r
  95                         ArrayList<PathRequirement> reqs = new ArrayList<PathRequirement>();                     \r
  96                         for (IElement e : d.getElements())\r
  97                         {\r
  98                                 BendsHandler bends = e.getElementClass().getAtMostOneItemOfClass(BendsHandler.class);\r
  99                                 if (bends==null) continue;\r
 100                                 Path2D path = bends.getPath(e);\r
 101                                 assert(path!=null);\r
 102                                 reqs.clear();\r
 103                                 createPathRequirement(e, reqs);                 \r
 104                                 if (reqs.isEmpty()) continue;\r
 105                                 if (pathFollowsRequirements(path, reqs)) continue;\r
 106                                 \r
 107                                 AngleType at = bends.getAngleType(e);\r
 108                                 if (at==AngleType.Linear) {\r
 109                                         path = createPathLinear(reqs);\r
 110                                 } else if (at==AngleType.RightAngled) {\r
 111                                         path = createPathRightAngled(reqs);                                     \r
 112                                 } else if (at==AngleType.Quadratic) {\r
 113                                         path = createPathQuadratic(reqs);\r
 114                                 } else if (at==AngleType.Line) {\r
 115                                         path = createPathLine(reqs);\r
 116                                 } else assert(false);\r
 117                                 \r
 118                                 // Make up something!\r
 119                                 if (path==null)\r
 120                                         path = createPathLine(reqs);\r
 121 \r
 122                                 AffineTransform elementToDiagramAt = ElementUtils.getInvTransform(e);\r
 123                                 path.transform(elementToDiagramAt);\r
 124                                 \r
 125                                 bends.setPath(e, path);\r
 126                         }                       \r
 127                         return false;\r
 128                 }\r
 129                 @Override\r
 130                 public String getMessage() {\r
 131                         return "Update path";\r
 132                 }\r
 133         };\r
 134         private static final Issue PATH_IS_BROKEN = \r
 135                 new DiagramIssue("Path does not follow its requirements (connects and bends)", FORCE_PATH_TO_REQUIREMENTS, DISCONNECT_EDGES);\r
 136         \r
 137         @Override\r
 138         public void validate(IDiagram d, ICanvasContext ctx, Collection<Issue> lst) {\r
 139                 if (!validateDiagramOk(d, ctx, lst))\r
 140                 {\r
 141                         lst.add(PATH_IS_BROKEN);\r
 142                 }\r
 143         }\r
 144         \r
 145         /**\r
 146          * Return true if connections of a diagram are ok.\r
 147          * @param d\r
 148          * @param ctx\r
 149          * @param lst\r
 150          * @return\r
 151          */\r
 152         boolean validateDiagramOk(IDiagram d, ICanvasContext ctx, Collection<Issue> lst)\r
 153         {\r
 154                 // Get all edges\r
 155                 ArrayList<PathRequirement> reqs = new ArrayList<PathRequirement>();\r
 156                 for (IElement e : d.getElements())\r
 157                 {\r
 158                         BendsHandler bends = e.getElementClass().getAtMostOneItemOfClass(BendsHandler.class);\r
 159                         if (bends==null) continue;\r
 160                         Path2D path = bends.getPath(e);\r
 161 \r
 162                         reqs.clear();\r
 163                         createPathRequirement(e, reqs);                 \r
 164                         if (reqs.isEmpty()) continue;\r
 165                         if (pathFollowsRequirements(path, reqs)) continue;\r
 166                         return false;\r
 167                 }\r
 168                 return true;\r
 169         }\r
 170         \r
 171         /**\r
 172          * Forces the path to follow path requirements.\r
 173          *  \r
 174          * @param e\r
 175          * @param reqs path requirements.\r
 176          * @return true if path matches requirements\r
 177          */\r
 178         public static boolean pathFollowsRequirements(Path2D path, List<PathRequirement> reqs)\r
 179         {\r
 180                 if (reqs.size()==0) return true;\r
 181                 // To validate path we need to make sure that \r
 182                 // 1) path goes thru control points             \r
 183                 // 2) The tangent of the path at control points is in direction set\r
 184                 int                             reqIndex        = 0;\r
 185                 PathRequirement                 req                     = reqs.get(reqIndex++); \r
 186                 PathIterator            pi                      = path.getPathIterator(null);\r
 187                 Iterator<double[]>      lsi                     = PathUtils.toLineIterator(pi);\r
 188                 if (!lsi.hasNext()) return false;\r
 189                 \r
 190                 // check begin\r
 191                 double[]                        seg                     = lsi.next();\r
 192                 Point2D                         pos                     = PathUtils.getLinePos(seg, 0);\r
 193                 Rectangle2D                     rect            = new Rectangle2D.Double(pos.getX()-TOLERANCE, pos.getY()-TOLERANCE, 2*TOLERANCE, 2*TOLERANCE);\r
 194                 \r
 195                 // Check pos\r
 196                 if (!rect.contains(pos)) return false;\r
 197                 // Check tangent\r
 198                 Point2D                         tang            = PathUtils.getLineTangent(seg, 0);\r
 199                 double                          dir                     = GeometryUtils.getCompassDirection(tang);\r
 200                 Double                          closestDir      = req.set.getClosestDirection(dir, 0.1);\r
 201                 if (closestDir == null) return false; \r
 202                 \r
 203                 while (lsi.hasNext()) {\r
 204                         seg                             = lsi.next();\r
 205                         pos                             = PathUtils.getLinePos(seg, 1);\r
 206                         rect                    = new Rectangle2D.Double(pos.getX()-TOLERANCE, pos.getY()-TOLERANCE, 2*TOLERANCE, 2*TOLERANCE);\r
 207                         \r
 208                         if (rect.contains(pos)) {\r
 209                                 // check tangent\r
 210                                 tang                    = PathUtils.getLineTangent(seg, 1);\r
 211                                 dir                             = GeometryUtils.getCompassDirection(tang);\r
 212                                 closestDir              = req.set.getClosestDirection(dir, 0.1);\r
 213                                 if (closestDir != null) \r
 214                                 {\r
 215                                         // next requirement\r
 216                                         req = reqs.get(reqIndex++);\r
 217                                 }\r
 218                         }                       \r
 219                 }\r
 220                 return reqIndex==reqs.size();\r
 221         }\r
 222 \r
 223         static class LinearEdgeSolutionNode implements ProblemNode {\r
 224                 List<PathRequirement> reqs;\r
 225                 LinearEdgeSolutionNode prevBranch;\r
 226                 int index;\r
 227                 double cost;\r
 228                 Point2D p0, cp, p1;\r
 229                 Point2D v0, v1, v1o; // v0=direction vector from p0, v1=direction vector to p1\r
 230                 // v1o = opposite of v1o\r
 231                 @Override\r
 232                 public void branch(Collection<ProblemNode> list) {\r
 233                         PathRequirement r0 = reqs.get(index  );\r
 234                         PathRequirement r1 = reqs.get(index+1);\r
 235                         Point2D         p0 = r0.pos;\r
 236                         Point2D         p1 = r1.pos;\r
 237                         Point2D         cp1 = new Point2D.Double();\r
 238                         Point2D         cp2 = new Point2D.Double();\r
 239                         Set<Object> controlPoints = new HashSet<Object>();\r
 240                         for (Point2D v0 : r0.set.getUnitVectors())\r
 241                                 for (Point2D v1 : r1.set.getUnitVectors())\r
 242                                 {\r
 243                                         Point2D i       = PathUtils.findIntersection(p0, v0, p1, v1);\r
 244                                         if (i!=null) {\r
 245                                                 controlPoints.add(i);\r
 246                                                 \r
 247                                         } else {\r
 248                                                 // Impossible requirements\r
 249                                                 int flags = PathUtils.findNearestPoints(p0, v0, p1, v1, cp1, cp2); \r
 250                                                 if ((flags & 1) == 1) \r
 251                                                         controlPoints.add(cp1);\r
 252                                                 if ((flags & 2) == 2)\r
 253                                                         controlPoints.add(cp2);\r
 254                                                 \r
 255                                         }\r
 256                                 }\r
 257                         if (controlPoints.isEmpty()) {\r
 258                                 Point2D i = new Point2D.Double(\r
 259                                                 (p0.getX() + p1.getX())/2,\r
 260                                                 (p0.getY() + p1.getY())/2);\r
 261                                 controlPoints.add(i);\r
 262                         }\r
 263                         for (Object dada : controlPoints) {\r
 264                                 Point2D c0 = (Point2D) dada;\r
 265                                 double price = p0.distance(c0)+c0.distance(p1);\r
 266                                 price -= p0.distance(p1);\r
 267                                 \r
 268                                 LinearEdgeSolutionNode s = new LinearEdgeSolutionNode();                                        \r
 269                                 s.cost = cost + price;\r
 270                                 s.prevBranch = this;\r
 271                                 s.reqs = reqs;\r
 272                                 s.index = index+1;\r
 273                                 s.p0 = p0;\r
 274                                 s.p1 = p1;\r
 275                                 if (!c0.equals(p0) && !c0.equals(p1)) \r
 276                                         s.cp = c0;\r
 277                                 \r
 278                                 Point2D np = s.cp == null ? p1 : c0;\r
 279                                 double dist = p0.distance(np);\r
 280                                 s.v0 = new Point2D.Double( (p0.getX() - np.getX())/dist, (p0.getY() - np.getY())/dist);\r
 281 \r
 282                                 np = s.cp == null ? p0 : c0;\r
 283                                 dist = p1.distance(np);\r
 284                                 s.v1 = new Point2D.Double( (p1.getX() - np.getX())/dist, (p1.getY() - np.getY())/dist);\r
 285                                 s.v1o = new Point2D.Double( (np.getX() - p1.getX())/dist, (np.getY() - p1.getY())/dist); \r
 286 \r
 287                                 // Penalty for changing direction \r
 288                                 if (v1!=null && !s.v0.equals(v1)) \r
 289                                         s.cost += 1;\r
 290                                 // Penalty for going back\r
 291                                 if (v1o!=null && v1o.equals(s.v0)) \r
 292                                         s.cost += 2;\r
 293                                 \r
 294                                 list.add(s);\r
 295                         }\r
 296                 }\r
 297                 @Override\r
 298                 public double getCost() {\r
 299                         return cost;\r
 300                 }\r
 301                 @Override\r
 302                 public boolean isComplete() {\r
 303                         return index>=reqs.size()-1;\r
 304                 }\r
 305                 /**\r
 306                  * Create path from root to this node\r
 307                  * @return\r
 308                  */\r
 309                 public List<LinearEdgeSolutionNode> toList() {\r
 310                         LinkedList<LinearEdgeSolutionNode> res = new LinkedList<LinearEdgeSolutionNode>();\r
 311                         LinearEdgeSolutionNode branch = this;\r
 312                         while (branch!=null) {\r
 313                                 res.addFirst(branch);\r
 314                                 branch = branch.prevBranch;\r
 315                         }\r
 316                         return res;\r
 317                 }\r
 318                 public Path2D toPath() {\r
 319                         Path2D p = new Path2D.Double();                 \r
 320                         for (LinearEdgeSolutionNode s : toList()) \r
 321                         {\r
 322                                 if (s.p0==null) continue;\r
 323                                 Point2D cur = p.getCurrentPoint();\r
 324                                 if (cur==null) \r
 325                                         p.moveTo(s.p0.getX(), s.p0.getY());\r
 326                                 \r
 327                                 cur = p.getCurrentPoint();\r
 328                                 if ((s.cp!=null)&&(cur==null || !cur.equals(s.cp))) \r
 329                                         p.lineTo(s.cp.getX(), s.cp.getY());                             \r
 330                                 \r
 331                                 cur = p.getCurrentPoint();\r
 332                                 if (cur==null || !cur.equals(s.p1)) \r
 333                                         p.lineTo(s.p1.getX(), s.p1.getY());                             \r
 334                         }\r
 335                         \r
 336                         return p;\r
 337                 }\r
 338         }\r
 339         \r
 340         /**\r
 341          * Create a linear path that follows path requirements\r
 342          * @param reqs requirements\r
 343          * @return path\r
 344          */\r
 345         public static Path2D createPathLinear(final List<PathRequirement> reqs)\r
 346         {\r
 347                 LinearEdgeSolutionNode s = new LinearEdgeSolutionNode();\r
 348                 s.reqs = reqs;\r
 349                 LinearEdgeSolutionNode solution = (LinearEdgeSolutionNode) TreeProblem.findSolution(s, 2);\r
 350                 if (solution==null) return null;                \r
 351                 return solution.toPath();               \r
 352         }\r
 353         \r
 354         /**\r
 355          * Create a line that follows path requirements\r
 356          * @param reqs\r
 357          * @return\r
 358          */\r
 359         public static Path2D createPathLine(final List<PathRequirement> reqs)\r
 360         {\r
 361                 Path2D result = new Path2D.Double();\r
 362                 int index = 0;\r
 363                 for (PathRequirement r : reqs) {\r
 364                         if (index++==0)\r
 365                                 result.moveTo(r.pos.getX(), r.pos.getY());\r
 366                         else\r
 367                                 result.lineTo(r.pos.getX(), r.pos.getY());\r
 368                 }\r
 369                 return result;\r
 370         }\r
 371         \r
 372 \r
 373         /**\r
 374          * Create a right-angled (90 deg angles) path that follows requirements \r
 375          * @param reqs requirements\r
 376          * @return path\r
 377          */\r
 378         public static Path2D createPathRightAngled(List<PathRequirement> reqs)\r
 379         {\r
 380                 Path2D res = new Path2D.Double();\r
 381 //              int i = 0;\r
 382 //              for (PathRequirement r : reqs)\r
 383 //              {\r
 384 //                              \r
 385 //              }                       \r
 386                 \r
 387                 return res;\r
 388         }\r
 389         \r
 390         /**\r
 391          * Create a path that follows requirements\r
 392          * @param reqs requirements\r
 393          * @return path\r
 394          */\r
 395         public static Path2D createPathQuadratic(List<PathRequirement> reqs)\r
 396         {\r
 397                 Path2D res = new Path2D.Double();\r
 398 //              int i = 0;\r
 399 //              for (PathRequirement r : reqs)\r
 400 //              {\r
 401 //                      \r
 402 //              }                       \r
 403                 \r
 404                 return res;\r
 405         }\r
 406         \r
 407         \r
 408         /**\r
 409          * Path Requirement is a point thru which the path must "travel".\r
 410          */\r
 411         static class PathRequirement {\r
 412                 Point2D pos;  // Position on diagram\r
 413                 DirectionSet set; // Allowed directions\r
 414                 boolean isBegin, isEnd;\r
 415         }\r
 416         \r
 417         /**\r
 418          * Takes a look at an edge and creates a path travel plan (requiremetn).\r
 419          * Beginning of e must point to (possibly) connected terminal.\r
 420          * End of e must point to (possibly) connected terminal.\r
 421          * \r
 422          * @param e\r
 423          * @param pathRequirement Path requirements\r
 424          */\r
 425         public static void createPathRequirement(IElement e, List<PathRequirement> pathRequirement)\r
 426         {\r
 427                 Topology t = ElementUtils.getDiagram(e).getDiagramClass().getSingleItem(Topology.class);\r
 428                 pathRequirement.clear();\r
 429                 if (t==null) return;\r
 430                 \r
 431                 // Add begin\r
 432                 Connection c1 = t.getConnection(e, EdgeEnd.Begin);\r
 433                 if (c1!=null) {\r
 434                         PathRequirement req = new PathRequirement();\r
 435                         AffineTransform at = TerminalUtil.getTerminalPosOnDiagram(c1.node, c1.terminal);                        \r
 436                         req.pos = new Point2D.Double( at.getTranslateX(), at.getTranslateY() );\r
 437                         req.set = ElementUtils.getTerminalDirection(c1.node, c1.terminal);\r
 438                         req.isBegin = true;\r
 439                         pathRequirement.add(req);\r
 440                 } \r
 441                 \r
 442                 // Add control points\r
 443                 AffineTransform elementTransform = ElementUtils.getTransform(e);\r
 444                 BendsHandler bends = e.getElementClass().getSingleItem(BendsHandler.class);             \r
 445                 ArrayList<Bend> controlPoints = new ArrayList<Bend>();\r
 446                 bends.getBends(e, controlPoints);\r
 447                 for (Bend cp : controlPoints) \r
 448                 {\r
 449                         Point2D pos = new Point2D.Double();\r
 450                         bends.getBendPosition(e, cp, pos);\r
 451                         elementTransform.transform(pos, pos);\r
 452                         PathRequirement req = new PathRequirement();\r
 453                         req.set = DirectionSet.NESW;\r
 454                         req.pos = pos;\r
 455                         pathRequirement.add(req);\r
 456                 }\r
 457         \r
 458                 // TODO lisää transformit\r
 459                 \r
 460                 \r
 461                 // Add end\r
 462                 Connection c2 = t.getConnection(e, EdgeEnd.End);\r
 463                 if (c2!=null) {\r
 464                         PathRequirement req = new PathRequirement();\r
 465                         AffineTransform at = TerminalUtil.getTerminalPosOnDiagram(c2.node, c2.terminal);                        \r
 466                         req.pos = new Point2D.Double( at.getTranslateX(), at.getTranslateY() );\r
 467                         req.set                                 = ElementUtils.getTerminalDirection(c2.node, c2.terminal);\r
 468                         req.set                                 = req.set.createInverse();\r
 469                         req.isEnd                               = true;\r
 470                         pathRequirement.add(req);\r
 471                 }               \r
 472                 \r
 473         }\r
 474 \r
 475 }\r