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

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