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