--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2013 Association for Decentralized Information Management in\r
+ * Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.diagram.connection.segments;\r
+\r
+import gnu.trove.map.TObjectIntMap;\r
+import gnu.trove.map.hash.THashMap;\r
+import gnu.trove.map.hash.TObjectIntHashMap;\r
+import gnu.trove.procedure.TObjectIntProcedure;\r
+import gnu.trove.set.hash.THashSet;\r
+\r
+import java.awt.geom.Point2D;\r
+import java.util.ArrayList;\r
+import java.util.Collection;\r
+import java.util.List;\r
+import java.util.Map;\r
+import java.util.Set;\r
+\r
+import org.simantics.diagram.connection.RoutePoint;\r
+\r
+/**\r
+ * @author Hannu Niemistö\r
+ * @author Tuukka Lehtonen <tuukka.lehtonen@semantum.fi>\r
+ */\r
+public class GeometricSegment {\r
+ public final double x1;\r
+ public final double y1;\r
+ public final boolean isBranching1;\r
+\r
+ public final double x2;\r
+ public final double y2;\r
+ public final boolean isBranching2;\r
+\r
+ public GeometricSegment(double x1, double y1, boolean isBranching1,\r
+ double x2, double y2, boolean isBranching2) {\r
+ this.x1 = x1;\r
+ this.y1 = y1;\r
+ this.isBranching1 = isBranching1;\r
+ this.x2 = x2;\r
+ this.y2 = y2;\r
+ this.isBranching2 = isBranching2;\r
+ }\r
+\r
+ public boolean isOnSegment(double x, double y) {\r
+ double dist = distanceFrom(x1, y1, x2, y2, x, y);\r
+ //System.out.println("distance(" + this + ", " + x + ", " + y + "): " + dist);\r
+ return dist == 0;\r
+ }\r
+\r
+ public static List<GeometricSegment> convert(Collection<Segment> segments) {\r
+ // Compute point counts\r
+ TObjectIntHashMap<RoutePoint> pointCounts = new TObjectIntHashMap<RoutePoint>(); \r
+ for(Segment segment : segments) {\r
+ pointCounts.adjustOrPutValue(segment.p1, 1, 1);\r
+ pointCounts.adjustOrPutValue(segment.p2, 1, 1);\r
+ }\r
+\r
+ // Propagate point counts thru degenerated points\r
+ // This code is not perfect: it may fail if there are multiple\r
+ // degenerated segments connected to the same point.\r
+ for(Segment segment : segments) {\r
+ if(segment.isDegenerated()) {\r
+ int count = pointCounts.get(segment.p1) + \r
+ pointCounts.get(segment.p2) - 2;\r
+ pointCounts.put(segment.p1, count);\r
+ pointCounts.put(segment.p2, count);\r
+ }\r
+ }\r
+\r
+ // Generate geometric segments\r
+ ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>();\r
+ for(Segment segment : segments) {\r
+ if(!segment.isDegenerated()) {\r
+ result.add(new GeometricSegment(\r
+ segment.p1.getX(), segment.p1.getY(), \r
+ pointCounts.get(segment.p1) > 2, \r
+ segment.p2.getX(), segment.p2.getY(), \r
+ pointCounts.get(segment.p2) > 2\r
+ ));\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+\r
+ /**\r
+ * Removes unnecessary points from the specified set of segments. Returns a\r
+ * set of segments that no longer specify these unnecessary points.\r
+ * \r
+ * Definition: point P is unnecessary iff\r
+ * 1. P connects only two other points P1 and P2 together (P1 != P && P2 != P)\r
+ * 2. P lies on the line segment formed by points (P1, P2)\r
+ * \r
+ * @param segments unoptimized set of line segments\r
+ * @return optimized set of line segments\r
+ */\r
+ public static List<GeometricSegment> optimize(List<GeometricSegment> segments) {\r
+ if (segments.size() == 1)\r
+ return segments;\r
+\r
+ TObjectIntMap<Point2D> degree = new TObjectIntHashMap<Point2D>();\r
+ final TObjectIntMap<Point2D> branched = new TObjectIntHashMap<Point2D>();\r
+ final Map<Point2D, List<GeometricSegment>> segmentsOfPoint = new THashMap<Point2D, List<GeometricSegment>>();\r
+\r
+ for (GeometricSegment seg : segments) {\r
+ Point2D p1 = new Point2D.Double(seg.x1, seg.y1);\r
+ Point2D p2 = new Point2D.Double(seg.x2, seg.y2);\r
+ degree.adjustOrPutValue(p1, 1, 1);\r
+ degree.adjustOrPutValue(p2, 1, 1);\r
+ int bi1 = seg.isBranching1 ? 1 : 0;\r
+ int bi2 = seg.isBranching2 ? 1 : 0;\r
+ branched.adjustOrPutValue(p1, bi1, bi1);\r
+ branched.adjustOrPutValue(p2, bi2, bi2);\r
+ addSegmentToPoint(p1, seg, segmentsOfPoint);\r
+ addSegmentToPoint(p2, seg, segmentsOfPoint);\r
+ }\r
+\r
+ final List<Point2D> unnecessaryPoints = new ArrayList<Point2D>(segments.size());\r
+ degree.forEachEntry(new TObjectIntProcedure<Point2D>() {\r
+ @Override\r
+ public boolean execute(Point2D a, int branchCount) {\r
+ if (branchCount == 2 && branched.get(a) == 0) {\r
+ // Is the point on the same line formed by the\r
+ // join of the two segments if a is removed from\r
+ // between them?\r
+ List<GeometricSegment> segs = segmentsOfPoint.get(a);\r
+ assert segs.size() == 2;\r
+ GeometricSegment seg = join(a, segs.get(0), segs.get(1));\r
+ if (seg.isOnSegment(a.getX(), a.getY())) {\r
+ // a is a degenerate route point that can be removed\r
+ unnecessaryPoints.add(a);\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+ });\r
+\r
+ if (unnecessaryPoints.isEmpty())\r
+ return segments;\r
+\r
+ // Remove all unnecessary points from \r
+ Point2D p = new Point2D.Double();\r
+ for (Point2D dp : unnecessaryPoints) {\r
+ //System.out.println("Removing unnecessary point: " + dp);\r
+ List<GeometricSegment> segs = segmentsOfPoint.remove(dp);\r
+ assert segs.size() == 2;\r
+\r
+ GeometricSegment joined = join(dp, segs.get(0), segs.get(1));\r
+\r
+ GeometricSegment a = segs.get(0);\r
+ a.otherEnd(dp, p);\r
+ removeSegmentFromPoint(p, a, segmentsOfPoint);\r
+ addSegmentToPoint(p, joined, segmentsOfPoint);\r
+\r
+ GeometricSegment b = segs.get(1);\r
+ b.otherEnd(dp, p);\r
+ removeSegmentFromPoint(p, b, segmentsOfPoint);\r
+ addSegmentToPoint(p, joined, segmentsOfPoint);\r
+ }\r
+\r
+ ArrayList<GeometricSegment> result = new ArrayList<GeometricSegment>(segments.size());\r
+ Set<GeometricSegment> processed = new THashSet<GeometricSegment>();\r
+ for (List<GeometricSegment> segs : segmentsOfPoint.values()) {\r
+ for (GeometricSegment seg : segs) {\r
+ if (processed.add(seg)) {\r
+ result.add(seg);\r
+ }\r
+ }\r
+ }\r
+\r
+ return result;\r
+ }\r
+\r
+ /**\r
+ * Internal utility for {@link #optimize(List)}.\r
+ * @param seg\r
+ * @param oneEnd\r
+ * @param otherEnd\r
+ * @return\r
+ */\r
+ private Point2D otherEnd(Point2D oneEnd, Point2D otherEnd) {\r
+ double x = oneEnd.getX();\r
+ double y = oneEnd.getY();\r
+ double rx = x1;\r
+ double ry = y1;\r
+ if (x == x1 && y == y1) {\r
+ rx = x2;\r
+ ry = y2;\r
+ }\r
+ otherEnd.setLocation(rx, ry);\r
+ return otherEnd;\r
+ }\r
+\r
+ /**\r
+ * Internal utility for {@link #optimize(List)}.\r
+ * \r
+ * @param at\r
+ * @param s1\r
+ * @param s2\r
+ * @return\r
+ */\r
+ private static GeometricSegment join(Point2D at, GeometricSegment s1, GeometricSegment s2) {\r
+ double x = at.getX();\r
+ double y = at.getY();\r
+\r
+ double x1 = s1.x1;\r
+ double y1 = s1.y1;\r
+ boolean b1 = s1.isBranching1;\r
+ if (x == s1.x1 && y == s1.y1) {\r
+ x1 = s1.x2;\r
+ y1 = s1.y2;\r
+ b1 = s1.isBranching2;\r
+ }\r
+\r
+ double x2 = s2.x1;\r
+ double y2 = s2.y1;\r
+ boolean b2 = s2.isBranching1;\r
+ if (x == s2.x1 && y == s2.y1) {\r
+ x2 = s2.x2;\r
+ y2 = s2.y2;\r
+ b1 = s2.isBranching2;\r
+ }\r
+\r
+ return new GeometricSegment(x1, y1, b1, x2, y2, b2);\r
+ }\r
+\r
+ /**\r
+ * Internal utility for {@link #optimize(List)}.\r
+ * \r
+ * @param p\r
+ * @param seg\r
+ * @param segmentsOfPoint\r
+ */\r
+ private static void addSegmentToPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {\r
+ List<GeometricSegment> l = segmentsOfPoint.get(p);\r
+ if (l == null)\r
+ segmentsOfPoint.put(p, l = new ArrayList<GeometricSegment>(4));\r
+ l.add(seg);\r
+ }\r
+\r
+ /**\r
+ * Internal utility for {@link #optimize(List)}.\r
+ * \r
+ * @param p\r
+ * @param seg\r
+ * @param segmentsOfPoint\r
+ * @return\r
+ */\r
+ private static boolean removeSegmentFromPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {\r
+ List<GeometricSegment> l = segmentsOfPoint.get(p);\r
+ return l != null ? l.remove(seg) : false;\r
+ }\r
+\r
+ /**\r
+ * @param x1 line segment end 1 x\r
+ * @param y1 line segment end 1 y\r
+ * @param x2 line segment end 2 x\r
+ * @param y2 line segment end 2 y\r
+ * @param px point x\r
+ * @param py point y\r
+ * @return distance of (px,py) from line ((x1,y1), (x2,y2))\r
+ */\r
+ private static double distanceFrom(double x1, double y1, double x2, double y2, double px, double py) {\r
+ // Adjust vectors relative to x1,y1\r
+ // x2,y2 becomes relative vector from x1,y1 to end of segment\r
+ x2 -= x1;\r
+ y2 -= y1;\r
+ // px,py becomes relative vector from x1,y1 to test point\r
+ px -= x1;\r
+ py -= y1;\r
+ double dotprod = px * x2 + py * y2;\r
+ // dotprod is the length of the px,py vector\r
+ // projected on the x1,y1=>x2,y2 vector times the\r
+ // length of the x1,y1=>x2,y2 vector\r
+ double lineLenSq = x2 * x2 + y2 * y2;\r
+ double lineLen = Math.sqrt(lineLenSq);\r
+ double projLen = dotprod / lineLen;\r
+\r
+ // Check whether the projection of (px,py) is outside the specified line.\r
+ if (projLen < 0) {\r
+ return Math.sqrt(px * px + py * py);\r
+ } else if (projLen > lineLen) {\r
+ double dx = px - x2;\r
+ double dy = py - y2;\r
+ return Math.sqrt(dx * dx + dy * dy);\r
+ }\r
+ return Math.sqrt(px * px + py * py - projLen * projLen);\r
+ }\r
+\r
+ @Override\r
+ public String toString() {\r
+ return getClass().getSimpleName() + "[(" + x1 + ", " + y1 + ", " + isBranching1\r
+ + ") <-> (" + x2 + ", " + y2 + ", " + isBranching2 + ")]";\r
+ }\r
+}\r
Code Review / simantics / platform.git / blobdiff