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=23aa147844144e2b00b2cb92f76efda8a8b42ed3;hp=0000000000000000000000000000000000000000;hb=969bd23cab98a79ca9101af33334000879fb60c5;hpb=866dba5cd5a3929bbeae85991796acb212338a08 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 new file mode 100644 index 000000000..23aa14784 --- /dev/null +++ b/bundles/org.simantics.diagram.connection/src/org/simantics/diagram/connection/segments/GeometricSegment.java @@ -0,0 +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 + ")]"; + } +}