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

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