bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/segments/GeometricSegment.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2013 Association for Decentralized Information Management in\r
   3  * 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.diagram.connection.segments;\r
  13 \r
  14 import gnu.trove.map.TObjectIntMap;\r
  15 import gnu.trove.map.hash.THashMap;\r
  16 import gnu.trove.map.hash.TObjectIntHashMap;\r
  17 import gnu.trove.procedure.TObjectIntProcedure;\r
  18 import gnu.trove.set.hash.THashSet;\r
  19 \r
  20 import java.awt.geom.Point2D;\r
  21 import java.util.ArrayList;\r
  22 import java.util.Collection;\r
  23 import java.util.List;\r
  24 import java.util.Map;\r
  25 import java.util.Set;\r
  26 \r
  27 import org.simantics.diagram.connection.RoutePoint;\r
  28 \r
  29 /**\r
  30  * @author Hannu Niemist&ouml;\r
  31  * @author Tuukka Lehtonen <tuukka.lehtonen@semantum.fi>\r
  32  */\r
  33 public class GeometricSegment {\r
  34     public final double x1;\r
  35     public final double y1;\r
  36     public final boolean isBranching1;\r
  37 \r
  38     public final double x2;\r
  39     public final double y2;\r
  40     public final boolean isBranching2;\r
  41 \r
  42     public GeometricSegment(double x1, double y1, boolean isBranching1,\r
  43             double x2, double y2, boolean isBranching2) {\r
  44         this.x1 = x1;\r
  45         this.y1 = y1;\r
  46         this.isBranching1 = isBranching1;\r
  47         this.x2 = x2;\r
  48         this.y2 = y2;\r
  49         this.isBranching2 = isBranching2;\r
  50     }\r
  51 \r
  52     public boolean isOnSegment(double x, double y) {\r
  53         double dist = distanceFrom(x1, y1, x2, y2, x, y);\r
  54         //System.out.println("distance(" + this + ", " + x + ", " + y + "): " + dist);\r
  55         return dist == 0;\r
  56     }\r
  57 \r
  58     public static List<GeometricSegment> convert(Collection<Segment> segments) {\r
  59         // Compute point counts\r
  60         TObjectIntHashMap<RoutePoint> pointCounts = new TObjectIntHashMap<RoutePoint>(); \r
  61         for(Segment segment : segments) {\r
  62             pointCounts.adjustOrPutValue(segment.p1, 1, 1);\r
  63             pointCounts.adjustOrPutValue(segment.p2, 1, 1);\r
  64         }\r
  65 \r
  66         // Propagate point counts thru degenerated points\r
  67         // This code is not perfect: it may fail if there are multiple\r
  68         // degenerated segments connected to the same point.\r
  69         for(Segment segment : segments) {\r
  70             if(segment.isDegenerated()) {\r
  71                 int count = pointCounts.get(segment.p1) +  \r
  72                         pointCounts.get(segment.p2) - 2;\r
  73                 pointCounts.put(segment.p1, count);\r
  74                 pointCounts.put(segment.p2, count);\r
  75             }\r
  76         }\r
  77 \r
  78         // Generate geometric segments\r
  79         ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>();\r
  80         for(Segment segment : segments) {\r
  81             if(!segment.isDegenerated()) {\r
  82                 result.add(new GeometricSegment(\r
  83                         segment.p1.getX(), segment.p1.getY(), \r
  84                         pointCounts.get(segment.p1) > 2, \r
  85                         segment.p2.getX(), segment.p2.getY(), \r
  86                         pointCounts.get(segment.p2) > 2\r
  87                         ));\r
  88             }\r
  89         }\r
  90         return result;\r
  91     }\r
  92 \r
  93     /**\r
  94      * Removes unnecessary points from the specified set of segments. Returns a\r
  95      * set of segments that no longer specify these unnecessary points.\r
  96      * \r
  97      * Definition: point P is unnecessary iff\r
  98      * 1. P connects only two other points P1 and P2 together (P1 != P && P2 != P)\r
  99      * 2. P lies on the line segment formed by points (P1, P2)\r
 100      * \r
 101      * @param segments unoptimized set of line segments\r
 102      * @return optimized set of line segments\r
 103      */\r
 104     public static List<GeometricSegment> optimize(List<GeometricSegment> segments) {\r
 105         if (segments.size() == 1)\r
 106             return segments;\r
 107 \r
 108         TObjectIntMap<Point2D> degree = new TObjectIntHashMap<Point2D>();\r
 109         final TObjectIntMap<Point2D> branched = new TObjectIntHashMap<Point2D>();\r
 110         final Map<Point2D, List<GeometricSegment>> segmentsOfPoint = new THashMap<Point2D, List<GeometricSegment>>();\r
 111 \r
 112         for (GeometricSegment seg : segments) {\r
 113             Point2D p1 = new Point2D.Double(seg.x1, seg.y1);\r
 114             Point2D p2 = new Point2D.Double(seg.x2, seg.y2);\r
 115             degree.adjustOrPutValue(p1, 1, 1);\r
 116             degree.adjustOrPutValue(p2, 1, 1);\r
 117             int bi1 = seg.isBranching1 ? 1 : 0;\r
 118             int bi2 = seg.isBranching2 ? 1 : 0;\r
 119             branched.adjustOrPutValue(p1, bi1, bi1);\r
 120             branched.adjustOrPutValue(p2, bi2, bi2);\r
 121             addSegmentToPoint(p1, seg, segmentsOfPoint);\r
 122             addSegmentToPoint(p2, seg, segmentsOfPoint);\r
 123         }\r
 124 \r
 125         final List<Point2D> unnecessaryPoints = new ArrayList<Point2D>(segments.size());\r
 126         degree.forEachEntry(new TObjectIntProcedure<Point2D>() {\r
 127             @Override\r
 128             public boolean execute(Point2D a, int branchCount) {\r
 129                 if (branchCount == 2 && branched.get(a) == 0) {\r
 130                     // Is the point on the same line formed by the\r
 131                     // join of the two segments if a is removed from\r
 132                     // between them?\r
 133                     List<GeometricSegment> segs = segmentsOfPoint.get(a);\r
 134                     assert segs.size() == 2;\r
 135                     GeometricSegment seg = join(a, segs.get(0), segs.get(1));\r
 136                     if (seg.isOnSegment(a.getX(), a.getY())) {\r
 137                         // a is a degenerate route point that can be removed\r
 138                         unnecessaryPoints.add(a);\r
 139                     }\r
 140                 }\r
 141                 return true;\r
 142             }\r
 143         });\r
 144 \r
 145         if (unnecessaryPoints.isEmpty())\r
 146             return segments;\r
 147 \r
 148         // Remove all unnecessary points from \r
 149         Point2D p = new Point2D.Double();\r
 150         for (Point2D dp : unnecessaryPoints) {\r
 151             //System.out.println("Removing unnecessary point: " + dp);\r
 152             List<GeometricSegment> segs = segmentsOfPoint.remove(dp);\r
 153             assert segs.size() == 2;\r
 154 \r
 155             GeometricSegment joined = join(dp, segs.get(0), segs.get(1));\r
 156 \r
 157             GeometricSegment a = segs.get(0);\r
 158             a.otherEnd(dp, p);\r
 159             removeSegmentFromPoint(p, a, segmentsOfPoint);\r
 160             addSegmentToPoint(p, joined, segmentsOfPoint);\r
 161 \r
 162             GeometricSegment b = segs.get(1);\r
 163             b.otherEnd(dp, p);\r
 164             removeSegmentFromPoint(p, b, segmentsOfPoint);\r
 165             addSegmentToPoint(p, joined, segmentsOfPoint);\r
 166         }\r
 167 \r
 168         ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>(segments.size());\r
 169         Set<GeometricSegment> processed = new THashSet<GeometricSegment>();\r
 170         for (List<GeometricSegment> segs : segmentsOfPoint.values()) {\r
 171             for (GeometricSegment seg : segs) {\r
 172                 if (processed.add(seg)) {\r
 173                     result.add(seg);\r
 174                 }\r
 175             }\r
 176         }\r
 177 \r
 178         return result;\r
 179     }\r
 180 \r
 181     /**\r
 182      * Internal utility for {@link #optimize(List)}.\r
 183      * @param seg\r
 184      * @param oneEnd\r
 185      * @param otherEnd\r
 186      * @return\r
 187      */\r
 188     private Point2D otherEnd(Point2D oneEnd, Point2D otherEnd) {\r
 189         double x = oneEnd.getX();\r
 190         double y = oneEnd.getY();\r
 191         double rx = x1;\r
 192         double ry = y1;\r
 193         if (x == x1 && y == y1) {\r
 194             rx = x2;\r
 195             ry = y2;\r
 196         }\r
 197         otherEnd.setLocation(rx, ry);\r
 198         return otherEnd;\r
 199     }\r
 200 \r
 201     /**\r
 202      * Internal utility for {@link #optimize(List)}.\r
 203      * \r
 204      * @param at\r
 205      * @param s1\r
 206      * @param s2\r
 207      * @return\r
 208      */\r
 209     private static GeometricSegment join(Point2D at, GeometricSegment s1, GeometricSegment s2) {\r
 210         double x = at.getX();\r
 211         double y = at.getY();\r
 212 \r
 213         double x1 = s1.x1;\r
 214         double y1 = s1.y1;\r
 215         boolean b1 = s1.isBranching1;\r
 216         if (x == s1.x1 && y == s1.y1) {\r
 217             x1 = s1.x2;\r
 218             y1 = s1.y2;\r
 219             b1 = s1.isBranching2;\r
 220         }\r
 221 \r
 222         double x2 = s2.x1;\r
 223         double y2 = s2.y1;\r
 224         boolean b2 = s2.isBranching1;\r
 225         if (x == s2.x1 && y == s2.y1) {\r
 226             x2 = s2.x2;\r
 227             y2 = s2.y2;\r
 228             b1 = s2.isBranching2;\r
 229         }\r
 230 \r
 231         return new GeometricSegment(x1, y1, b1, x2, y2, b2);\r
 232     }\r
 233 \r
 234     /**\r
 235      * Internal utility for {@link #optimize(List)}.\r
 236      * \r
 237      * @param p\r
 238      * @param seg\r
 239      * @param segmentsOfPoint\r
 240      */\r
 241     private static void addSegmentToPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {\r
 242         List<GeometricSegment> l = segmentsOfPoint.get(p);\r
 243         if (l == null)\r
 244             segmentsOfPoint.put(p, l = new ArrayList<GeometricSegment>(4));\r
 245         l.add(seg);\r
 246     }\r
 247 \r
 248     /**\r
 249      * Internal utility for {@link #optimize(List)}.\r
 250      * \r
 251      * @param p\r
 252      * @param seg\r
 253      * @param segmentsOfPoint\r
 254      * @return\r
 255      */\r
 256     private static boolean removeSegmentFromPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {\r
 257         List<GeometricSegment> l = segmentsOfPoint.get(p);\r
 258         return l != null ? l.remove(seg) : false;\r
 259     }\r
 260 \r
 261     /**\r
 262      * @param x1 line segment end 1 x\r
 263      * @param y1 line segment end 1 y\r
 264      * @param x2 line segment end 2 x\r
 265      * @param y2 line segment end 2 y\r
 266      * @param px point x\r
 267      * @param py point y\r
 268      * @return distance of (px,py) from line ((x1,y1), (x2,y2))\r
 269      */\r
 270     private static double distanceFrom(double x1, double y1, double x2, double y2, double px, double py) {\r
 271         // Adjust vectors relative to x1,y1\r
 272         // x2,y2 becomes relative vector from x1,y1 to end of segment\r
 273         x2 -= x1;\r
 274         y2 -= y1;\r
 275         // px,py becomes relative vector from x1,y1 to test point\r
 276         px -= x1;\r
 277         py -= y1;\r
 278         double dotprod = px * x2 + py * y2;\r
 279         // dotprod is the length of the px,py vector\r
 280         // projected on the x1,y1=>x2,y2 vector times the\r
 281         // length of the x1,y1=>x2,y2 vector\r
 282         double lineLenSq = x2 * x2 + y2 * y2;\r
 283         double lineLen = Math.sqrt(lineLenSq);\r
 284         double projLen = dotprod / lineLen;\r
 285 \r
 286         // Check whether the projection of (px,py) is outside the specified line.\r
 287         if (projLen < 0) {\r
 288             return Math.sqrt(px * px + py * py);\r
 289         } else if (projLen > lineLen) {\r
 290             double dx = px - x2;\r
 291             double dy = py - y2;\r
 292             return Math.sqrt(dx * dx + dy * dy);\r
 293         }\r
 294         return Math.sqrt(px * px + py * py - projLen * projLen);\r
 295     }\r
 296 \r
 297     @Override\r
 298     public String toString() {\r
 299         return getClass().getSimpleName() + "[(" + x1 + ", " + y1 + ", " + isBranching1\r
 300                 + ") <-> (" + x2 + ", " + y2 + ", " + isBranching2 + ")]";\r
 301     }\r
 302 }\r