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