1 /*******************************************************************************
2 * Copyright (c) 2013 Association for Decentralized Information Management in
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.diagram.connection.segments;
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;
20 import java.awt.geom.Point2D;
21 import java.util.ArrayList;
22 import java.util.Collection;
23 import java.util.List;
27 import org.simantics.diagram.connection.RoutePoint;
30 * @author Hannu Niemistö
31 * @author Tuukka Lehtonen <tuukka.lehtonen@semantum.fi>
33 public class GeometricSegment {
34 public final double x1;
35 public final double y1;
36 public final boolean isBranching1;
38 public final double x2;
39 public final double y2;
40 public final boolean isBranching2;
42 public GeometricSegment(double x1, double y1, boolean isBranching1,
43 double x2, double y2, boolean isBranching2) {
46 this.isBranching1 = isBranching1;
49 this.isBranching2 = isBranching2;
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);
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);
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);
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
94 * Removes unnecessary points from the specified set of segments. Returns a
95 * set of segments that no longer specify these unnecessary points.
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)
101 * @param segments unoptimized set of line segments
102 * @return optimized set of line segments
104 public static List<GeometricSegment> optimize(List<GeometricSegment> segments) {
105 if (segments.size() == 1)
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>>();
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);
125 final List<Point2D> unnecessaryPoints = new ArrayList<Point2D>(segments.size());
126 degree.forEachEntry(new TObjectIntProcedure<Point2D>() {
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
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);
145 if (unnecessaryPoints.isEmpty())
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;
155 GeometricSegment joined = join(dp, segs.get(0), segs.get(1));
157 GeometricSegment a = segs.get(0);
159 removeSegmentFromPoint(p, a, segmentsOfPoint);
160 addSegmentToPoint(p, joined, segmentsOfPoint);
162 GeometricSegment b = segs.get(1);
164 removeSegmentFromPoint(p, b, segmentsOfPoint);
165 addSegmentToPoint(p, joined, segmentsOfPoint);
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)) {
182 * Internal utility for {@link #optimize(List)}.
188 private Point2D otherEnd(Point2D oneEnd, Point2D otherEnd) {
189 double x = oneEnd.getX();
190 double y = oneEnd.getY();
193 if (x == x1 && y == y1) {
197 otherEnd.setLocation(rx, ry);
202 * Internal utility for {@link #optimize(List)}.
209 private static GeometricSegment join(Point2D at, GeometricSegment s1, GeometricSegment s2) {
210 double x = at.getX();
211 double y = at.getY();
215 boolean b1 = s1.isBranching1;
216 if (x == s1.x1 && y == s1.y1) {
219 b1 = s1.isBranching2;
224 boolean b2 = s2.isBranching1;
225 if (x == s2.x1 && y == s2.y1) {
228 b1 = s2.isBranching2;
231 return new GeometricSegment(x1, y1, b1, x2, y2, b2);
235 * Internal utility for {@link #optimize(List)}.
239 * @param segmentsOfPoint
241 private static void addSegmentToPoint(Point2D p, GeometricSegment seg, Map<Point2D, List<GeometricSegment>> segmentsOfPoint) {
242 List<GeometricSegment> l = segmentsOfPoint.get(p);
244 segmentsOfPoint.put(p, l = new ArrayList<GeometricSegment>(4));
249 * Internal utility for {@link #optimize(List)}.
253 * @param segmentsOfPoint
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;
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
268 * @return distance of (px,py) from line ((x1,y1), (x2,y2))
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
275 // px,py becomes relative vector from x1,y1 to test point
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;
286 // Check whether the projection of (px,py) is outside the specified line.
288 return Math.sqrt(px * px + py * py);
289 } else if (projLen > lineLen) {
292 return Math.sqrt(dx * dx + dy * dy);
294 return Math.sqrt(px * px + py * py - projLen * projLen);
298 public String toString() {
299 return getClass().getSimpleName() + "[(" + x1 + ", " + y1 + ", " + isBranching1
300 + ") <-> (" + x2 + ", " + y2 + ", " + isBranching2 + ")]";