Imported Upstream version 8024

author: Andrew Shadura <andrew@shadura.me> 2015-07-21 14:52:03 +0200
committer: Andrew Shadura <andrew@shadura.me> 2015-07-21 14:52:03 +0200
commit: 26b872bb194ec7622997914bba53309a94b64d20 (patch)
tree: a79b966bf55dd61702b900b8ba40be4d2b3403db /src/net/sourceforge/plantuml/graph2
18 files changed, 2341 insertions, 0 deletions
diff --git a/src/net/sourceforge/plantuml/graph2/CubicCurveFactory.java b/src/net/sourceforge/plantuml/graph2/CubicCurveFactory.java
new file mode 100644
index 0000000..875adfb
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/CubicCurveFactory.java
@@ -0,0 +1,96 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.CubicCurve2D;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+public class CubicCurveFactory {
+
+	private final Point2D.Double start;
+	private final Point2D.Double end;
+	private final RectanglesCollection forbiddenRect = new RectanglesCollection();
+	private final List<MyCurve> forbiddenCurves = new ArrayList<MyCurve>();
+
+	public CubicCurveFactory(Point2D start, Point2D end) {
+		this.start = new Point2D.Double(start.getX(), start.getY());
+		this.end = new Point2D.Double(end.getX(), end.getY());
+	}
+
+	public void addForbidden(Rectangle2D.Double rect) {
+		forbiddenRect.add(rect);
+	}
+
+	public void addForbidden(MyCurve curve) {
+		forbiddenCurves.add(curve);
+	}
+
+	public MyCurve getCubicCurve2D() {
+		MyCurve result = new MyCurve(new CubicCurve2D.Double(start.getX(), start.getY(), start.getX(), start.getY(),
+				end.getX(), end.getY(), end.getX(), end.getY()));
+		if (result.intersects(forbiddenRect) || result.intersects(forbiddenCurves)) {
+			final Set<Point2D.Double> all = new HashSet<Point2D.Double>();
+			all.addAll(MagicPointsFactory.get(start, end));
+			for (Rectangle2D.Double rect : forbiddenRect) {
+				all.addAll(MagicPointsFactory.get(rect));
+			}
+// Log.println("s1 " + all.size());
+//			final long t1 = System.currentTimeMillis();
+			double min = Double.MAX_VALUE;
+			for (Point2D.Double p1 : all) {
+				for (Point2D.Double p2 : all) {
+					final MyCurve me = new MyCurve(new CubicCurve2D.Double(start.getX(), start.getY(), p1.getX(), p1
+							.getY(), p2.getX(), p2.getY(), end.getX(), end.getY()));
+					if (me.getLenght() < min && me.intersects(forbiddenRect) == false
+							&& me.intersects(forbiddenCurves) == false) {
+						result = me;
+						min = me.getLenght();
+					}
+				}
+			}
+//			final long t2 = System.currentTimeMillis() - t1;
+// Log.println("s2 = " + t2);
+// Log.println("TPS1 = " + RectanglesCollection.TPS1);
+// Log.println("TPS2 = " + RectanglesCollection.TPS2);
+		}
+		return result;
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Dijkstra.java b/src/net/sourceforge/plantuml/graph2/Dijkstra.java
new file mode 100644
index 0000000..38b9da3
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Dijkstra.java
@@ -0,0 +1,155 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+/*
+ * Copyright (c) 2009 the authors listed at the following URL, and/or the
+ * authors of referenced articles or incorporated external code:
+ * http://en.literateprograms.org/Dijkstra's_algorithm_(Java)?action=history&offset=20081113161332
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ * 
+ * Retrieved from:
+ * http://en.literateprograms.org/Dijkstra's_algorithm_(Java)?oldid=15444
+ */
+
+// http://www.google.fr/search?hl=fr&source=hp&q=A+star+java&btnG=Recherche+Google&meta=&aq=f&oq=
+// http://www.edenwaith.com/products/pige/tutorials/a-star.php
+import java.util.ArrayList;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class Dijkstra {
+
+	static class Vertex implements Comparable<Vertex> {
+		private final Object data;
+		private final List<Edge> adjacencies = new ArrayList<Edge>();
+		private double minDistance = Double.POSITIVE_INFINITY;
+		private Vertex previous;
+
+		Vertex(Object data) {
+			this.data = data;
+		}
+
+		public void addAdjacencies(Vertex target, double dist) {
+			if (target == null) {
+				throw new IllegalArgumentException();
+			}
+			adjacencies.add(new Edge(target, dist));
+		}
+
+		public String toString() {
+			return "[ " + data.toString() + " (" + minDistance + ") ] ";
+		}
+
+		public int compareTo(Vertex other) {
+			return Double.compare(minDistance, other.minDistance);
+		}
+
+		public final Object getData() {
+			return data;
+		}
+
+	}
+
+	static class Edge {
+		private final Vertex target;
+		private final double weight;
+
+		Edge(Vertex argTarget, double argWeight) {
+			target = argTarget;
+			weight = argWeight;
+		}
+	}
+
+	private final List<Vertex> vertices = new ArrayList<Vertex>();
+
+	public Vertex addVertex(Object data) {
+		final Vertex v = new Vertex(data);
+		vertices.add(v);
+		return v;
+	}
+
+	private void computePaths(Vertex source) {
+		source.minDistance = 0.;
+		final PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
+		vertexQueue.add(source);
+
+		while (vertexQueue.isEmpty() == false) {
+			final Vertex u = vertexQueue.poll();
+
+			// Visit each edge exiting u
+			for (Edge e : u.adjacencies) {
+				final Vertex v = e.target;
+				final double weight = e.weight;
+				final double distanceThroughU = u.minDistance + weight;
+				if (distanceThroughU < v.minDistance) {
+					vertexQueue.remove(v);
+
+					v.minDistance = distanceThroughU;
+					v.previous = u;
+					vertexQueue.add(v);
+				}
+			}
+		}
+	}
+
+	public List<Vertex> getShortestPathTo(Vertex source, Vertex target) {
+		computePaths(source);
+		final List<Vertex> path = new ArrayList<Vertex>();
+		for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
+			path.add(0, vertex);
+		}
+
+		return path;
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/GeomUtils.java b/src/net/sourceforge/plantuml/graph2/GeomUtils.java
new file mode 100644
index 0000000..676f6d2
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/GeomUtils.java
@@ -0,0 +1,156 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.Graphics2D;
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+
+public class GeomUtils {
+
+	public static Point2D translate(Point2D pt, double deltaX, double deltaY) {
+		return new Point2D.Double(pt.getX() + deltaX, pt.getY() + deltaY);
+	}
+
+	static public boolean isHorizontal(Line2D.Double seg) {
+		return seg.getP1().getY() == seg.getP2().getY();
+	}
+
+	static public boolean isVertical(Line2D.Double seg) {
+		return seg.getP1().getX() == seg.getP2().getX();
+	}
+
+	static public double getMinX(Line2D.Double seg) {
+		return Math.min(seg.x1, seg.x2);
+	}
+
+	static public double getMaxX(Line2D.Double seg) {
+		return Math.max(seg.x1, seg.x2);
+	}
+
+	static public double getMinY(Line2D.Double seg) {
+		return Math.min(seg.y1, seg.y2);
+	}
+
+	static public double getMaxY(Line2D.Double seg) {
+		return Math.max(seg.y1, seg.y2);
+	}
+
+	static public Point2D.Double getPoint2D(Line2D.Double line, double u) {
+		final double x = line.x1 + u * (line.x2 - line.x1);
+		final double y = line.y1 + u * (line.y2 - line.y1);
+		return new Point2D.Double(x, y);
+	}
+
+	private static boolean isBetween(double value, double v1, double v2) {
+		if (v1 < v2) {
+			return value >= v1 && value <= v2;
+		}
+		assert v2 <= v1;
+		return value >= v2 && value <= v1;
+
+	}
+
+	static boolean isBetween(Point2D toTest, Point2D pos1, Point2D pos2) {
+		return isBetween(toTest.getX(), pos1.getX(), pos2.getX()) && isBetween(toTest.getY(), pos1.getY(), pos2.getY());
+	}
+
+	static private double getIntersectionVertical(Line2D.Double line, double xOther) {
+		final double coef = line.x2 - line.x1;
+		if (coef == 0) {
+			return java.lang.Double.NaN;
+		}
+		return (xOther - line.x1) / coef;
+	}
+
+	static private double getIntersectionHorizontal(Line2D.Double line, double yOther) {
+		final double coef = line.y2 - line.y1;
+		if (coef == 0) {
+			return java.lang.Double.NaN;
+		}
+		return (yOther - line.y1) / coef;
+	}
+
+	static public Point2D.Double getSegIntersection(Line2D.Double line1, Line2D.Double line2) {
+		final double u;
+		if (isVertical(line2)) {
+			u = getIntersectionVertical(line1, line2.getP1().getX());
+		} else if (isHorizontal(line2)) {
+			u = getIntersectionHorizontal(line1, line2.getP1().getY());
+		} else {
+			throw new UnsupportedOperationException();
+		}
+		if (java.lang.Double.isNaN(u) || u < 0 || u > 1) {
+			return null;
+		}
+		final Point2D.Double result = getPoint2D(line1, u);
+		if (isBetween(result, line2.getP1(), line2.getP2())) {
+			return result;
+		}
+		return null;
+	}
+
+	public static String toString(Line2D line) {
+		// return line.getP1() + "-" + line.getP2();
+		return toString(line.getP1()) + "-" + toString(line.getP2());
+	}
+
+	public static String toString(Point2D pt) {
+		return "[" + pt.getX() + "," + pt.getY() + "]";
+	}
+
+	public static Point2D.Double getCenter(Line2D.Double l) {
+		final double x = (l.getX1() + l.getX2()) / 2;
+		final double y = (l.getY1() + l.getY2()) / 2;
+		return new Point2D.Double(x, y);
+	}
+
+	public static void fillPoint2D(Graphics2D g2d, Point2D pt) {
+		final int x = (int) pt.getX() - 1;
+		final int y = (int) pt.getY() - 1;
+		g2d.fillOval(x, y, 3, 3);
+	}
+	
+	public static double getOrthoDistance(Line2D.Double seg, Point2D pt) {
+		if (isHorizontal(seg)) {
+			return Math.abs(seg.getP1().getY() - pt.getY());
+		}
+		if (isVertical(seg)) {
+			return Math.abs(seg.getP1().getX() - pt.getX());
+		}
+		throw new IllegalArgumentException();
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/IInflationTransform.java b/src/net/sourceforge/plantuml/graph2/IInflationTransform.java
new file mode 100644
index 0000000..50668c8
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/IInflationTransform.java
@@ -0,0 +1,56 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.Collection;
+import java.util.List;
+
+public interface IInflationTransform {
+
+	void addInflationX(double xpos, double inflation);
+
+	void addInflationY(double ypos, double inflation);
+
+	double getTotalInflationX();
+
+	double getTotalInflationY();
+
+	Point2D inflatePoint2D(Point2D point);
+
+	List<Line2D.Double> inflate(Collection<Line2D.Double> segments);
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/IdentityInflationTransform.java b/src/net/sourceforge/plantuml/graph2/IdentityInflationTransform.java
new file mode 100644
index 0000000..b375f63
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/IdentityInflationTransform.java
@@ -0,0 +1,69 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+public class IdentityInflationTransform implements IInflationTransform {
+
+	public void addInflationX(double xpos, double inflation) {
+
+	}
+
+	public void addInflationY(double ypos, double inflation) {
+
+	}
+
+	public double getTotalInflationX() {
+		return 0;
+	}
+
+	public double getTotalInflationY() {
+		return 0;
+	}
+
+	public Point2D inflatePoint2D(Point2D point) {
+		return point;
+	}
+
+	public List<Line2D.Double> inflate(Collection<Line2D.Double> segments) {
+		return new ArrayList<Line2D.Double>(segments);
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/InflateData2.java b/src/net/sourceforge/plantuml/graph2/InflateData2.java
new file mode 100644
index 0000000..485c618
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/InflateData2.java
@@ -0,0 +1,125 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+public class InflateData2 implements Comparable<InflateData2> {
+
+	private final double pos;
+	private final double inflation;
+
+	public InflateData2(double pos, double inflation) {
+		this.pos = pos;
+		this.inflation = inflation;
+	}
+
+	public final double getPos() {
+		return pos;
+	}
+
+	public final double getInflation() {
+		return inflation;
+	}
+
+	public int compareTo(InflateData2 other) {
+		return -Double.compare(this.pos, other.pos);
+	}
+
+	// public Point2D inflateX(Point2D pt) {
+	// if (pt.getX() < pos) {
+	// return pt;
+	// }
+	// if (pt.getX() == pos) {
+	// return GeomUtils.translate(pt, inflation / 2, 0);
+	// }
+	// return GeomUtils.translate(pt, inflation, 0);
+	// }
+	//
+	public double inflateAt(double v) {
+		if (v == pos) {
+			return inflation / 2;
+		}
+
+		if (v < pos) {
+			return 0;
+		}
+		return inflation;
+	}
+
+	// public Line2D.Double inflateXAlpha(Line2D.Double line) {
+	//
+	// if (GeomUtils.isHorizontal(line)) {
+	// return new Line2D.Double(inflateX(line.getP1()), inflateX(line.getP2()));
+	// }
+	// if (line.x1 == pos && line.x2 == pos) {
+	// return new Line2D.Double(GeomUtils.translate(line.getP1(), inflation / 2,
+	// 0), GeomUtils.translate(line
+	// .getP2(), inflation / 2, 0));
+	// }
+	// if (line.x1 <= pos && line.x2 <= pos) {
+	// return line;
+	// }
+	// if (line.x1 >= pos && line.x2 >= pos) {
+	// return new Line2D.Double(GeomUtils.translate(line.getP1(), inflation, 0),
+	// GeomUtils.translate(line.getP2(),
+	// inflation, 0));
+	// }
+	// throw new UnsupportedOperationException();
+	// }
+	//
+	// public Line2D.Double inflateYAlpha(Line2D.Double line) {
+	// if (GeomUtils.isVertical(line)) {
+	// return new Line2D.Double(inflateY(line.getP1()), inflateY(line.getP2()));
+	// }
+	// if (line.y1 == pos && line.y2 == pos) {
+	// return new Line2D.Double(GeomUtils.translate(line.getP1(), 0, inflation /
+	// 2), GeomUtils.translate(line
+	// .getP2(), 0, inflation / 2));
+	// }
+	// if (line.y1 <= pos && line.y2 <= pos) {
+	// return line;
+	// }
+	// if (line.y1 >= pos && line.y2 >= pos) {
+	// return new Line2D.Double(GeomUtils.translate(line.getP1(), 0, inflation),
+	// GeomUtils.translate(line.getP2(),
+	// 0, inflation));
+	// }
+	// throw new UnsupportedOperationException();
+	// }
+
+	@Override
+	public String toString() {
+		return "" + pos + " (" + inflation + ")";
+	}
+}
diff --git a/src/net/sourceforge/plantuml/graph2/InflationTransform2.java b/src/net/sourceforge/plantuml/graph2/InflationTransform2.java
new file mode 100644
index 0000000..5837011
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/InflationTransform2.java
@@ -0,0 +1,239 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.AffineTransform;
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+class Point2DComparatorDistance implements Comparator<Point2D> {
+
+	private final Point2D center;
+
+	public Point2DComparatorDistance(Point2D center) {
+		this.center = center;
+	}
+
+	public int compare(Point2D p1, Point2D p2) {
+		return Double.compare(p1.distance(center), p2.distance(center));
+	}
+
+}
+
+public class InflationTransform2 implements IInflationTransform {
+
+	private final List<InflateData2> inflateX = new ArrayList<InflateData2>();
+	private final List<InflateData2> inflateY = new ArrayList<InflateData2>();
+
+	public void addInflationX(double xpos, double inflation) {
+		add(inflateX, xpos, inflation);
+	}
+
+	@Override
+	public String toString() {
+		return "inflateX = " + inflateX + " inflateY = " + inflateY;
+	}
+
+	public void addInflationY(double ypos, double inflation) {
+		add(inflateY, ypos, inflation);
+	}
+
+	public double getTotalInflationX() {
+		return sumInflation(inflateX);
+	}
+
+	public double getTotalInflationY() {
+		return sumInflation(inflateY);
+	}
+
+	static private double sumInflation(List<InflateData2> list) {
+		double result = 0;
+		for (InflateData2 data : list) {
+			result += data.getInflation();
+		}
+		return result;
+	}
+
+	static private void add(List<InflateData2> list, double ypos, double inflation) {
+		for (final ListIterator<InflateData2> it = list.listIterator(); it.hasNext();) {
+			final InflateData2 cur = it.next();
+			if (cur.getPos() == ypos) {
+				it.set(new InflateData2(ypos, Math.max(inflation, cur.getInflation())));
+				return;
+			}
+		}
+		list.add(new InflateData2(ypos, inflation));
+		Collections.sort(list);
+	}
+
+	Collection<Point2D.Double> cutPoints(Line2D.Double original) {
+
+		final SortedSet<Point2D.Double> result = new TreeSet<Point2D.Double>(new Point2DComparatorDistance(original
+				.getP1()));
+
+		if (GeomUtils.isHorizontal(original) == false) {
+			for (InflateData2 x : inflateX) {
+				final Line2D.Double vertical = new Line2D.Double(x.getPos(), GeomUtils.getMinY(original), x.getPos(),
+						GeomUtils.getMaxY(original));
+				final Point2D.Double inter = GeomUtils.getSegIntersection(original, vertical);
+				if (inter != null) {
+					result.add(inter);
+				}
+			}
+		}
+		if (GeomUtils.isVertical(original) == false) {
+			for (InflateData2 y : inflateY) {
+				final Line2D.Double horizontal = new Line2D.Double(GeomUtils.getMinX(original), y.getPos(), GeomUtils
+						.getMaxX(original), y.getPos());
+				final Point2D.Double inter = GeomUtils.getSegIntersection(original, horizontal);
+				if (inter != null) {
+					result.add(inter);
+				}
+			}
+		}
+		return result;
+	}
+
+	Collection<Line2D.Double> cutSegments(Line2D.Double original) {
+		final List<Line2D.Double> result = new ArrayList<Line2D.Double>();
+		Point2D.Double cur = (Point2D.Double) original.getP1();
+		final Collection<Point2D.Double> cutPoints = cutPoints(original);
+		for (Point2D.Double inter : cutPoints) {
+			if (cur.equals(inter)) {
+				continue;
+			}
+			result.add(new Line2D.Double(cur, inter));
+			cur = inter;
+		}
+		if (cur.equals(original.getP2()) == false) {
+			result.add(new Line2D.Double(cur, original.getP2()));
+		}
+		return result;
+	}
+
+	Collection<Line2D.Double> cutSegments(Collection<Line2D.Double> segments) {
+		final List<Line2D.Double> result = new ArrayList<Line2D.Double>();
+		for (Line2D.Double seg : segments) {
+			result.addAll(cutSegments(seg));
+		}
+		return result;
+	}
+
+	// private Line2D.Double inflateSegment(Line2D.Double seg) {
+	// // if (isOnGrid(seg.getP1()) && isOnGrid(seg.getP2())) {
+	// // return new Line2D.Double(inflatePoint2D(seg.getP1()),
+	// inflatePoint2D(seg.getP2()));
+	// // }
+	// // for (InflateData2 x : inflateX) {
+	// // seg = x.inflateXAlpha(seg);
+	// // }
+	// // for (InflateData2 y : inflateY) {
+	// // seg = y.inflateYAlpha(seg);
+	// // }
+	// // return seg;
+	// return new Line2D.Double(inflatePoint2D(seg.getP1()),
+	// inflatePoint2D(seg.getP2()));
+	// }
+
+	// private boolean isOnGrid(Point2D point) {
+	// boolean onGrid = false;
+	// for (InflateData2 x : inflateX) {
+	// if (point.getX() == x.getPos()) {
+	// onGrid = true;
+	// }
+	// }
+	// if (onGrid == false) {
+	// return false;
+	// }
+	// for (InflateData2 y : inflateY) {
+	// if (point.getY() == y.getPos()) {
+	// return true;
+	// }
+	// }
+	// return false;
+	//
+	// }
+
+	public Point2D inflatePoint2D(Point2D point) {
+		return getAffineTransformAt(point).transform(point, null);
+	}
+
+	AffineTransform getAffineTransformAt(Point2D point) {
+		double deltaX = 0;
+		for (InflateData2 x : inflateX) {
+			deltaX += x.inflateAt(point.getX());
+		}
+		double deltaY = 0;
+		for (InflateData2 y : inflateY) {
+			deltaY += y.inflateAt(point.getY());
+		}
+		return AffineTransform.getTranslateInstance(deltaX, deltaY);
+	}
+
+	List<Line2D.Double> inflateSegmentCollection(Collection<Line2D.Double> segments) {
+		final List<Line2D.Double> result = new ArrayList<Line2D.Double>();
+		for (Line2D.Double seg : segments) {
+			final AffineTransform at = getAffineTransformAt(new Point2D.Double((seg.x1 + seg.x2) / 2,
+					(seg.y1 + seg.y2) / 2));
+			result.add(new Line2D.Double(at.transform(seg.getP1(), null), at.transform(seg.getP2(), null)));
+		}
+		return result;
+	}
+
+	public List<Line2D.Double> inflate(Collection<Line2D.Double> segments) {
+		final Collection<Line2D.Double> cutSegments = cutSegments(segments);
+		Line2D.Double last = null;
+		final List<Line2D.Double> inflated = inflateSegmentCollection(cutSegments);
+		final List<Line2D.Double> result = new ArrayList<Line2D.Double>();
+		for (Line2D.Double seg : inflated) {
+			if (last != null && last.getP2().equals(seg.getP1()) == false) {
+				result.add(new Line2D.Double(last.getP2(), seg.getP1()));
+			}
+			result.add(seg);
+			last = seg;
+
+		}
+		return result;
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/MagicPointsFactory.java b/src/net/sourceforge/plantuml/graph2/MagicPointsFactory.java
new file mode 100644
index 0000000..545ed25
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/MagicPointsFactory.java
@@ -0,0 +1,74 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
+import java.util.List;
+
+public class MagicPointsFactory {
+
+	private MagicPointsFactory() {
+
+	}
+
+	public static List<Point2D.Double> get(Rectangle2D.Double rect) {
+		final List<Point2D.Double> result = new ArrayList<Point2D.Double>();
+		result.add(new Point2D.Double(rect.x - rect.width, rect.y - rect.height));
+		result.add(new Point2D.Double(rect.x, rect.y - rect.height));
+		result.add(new Point2D.Double(rect.x + rect.width, rect.y - rect.height));
+		result.add(new Point2D.Double(rect.x + 2 * rect.width, rect.y - rect.height));
+
+		result.add(new Point2D.Double(rect.x - rect.width, rect.y));
+		result.add(new Point2D.Double(rect.x + 2 * rect.width, rect.y));
+
+		result.add(new Point2D.Double(rect.x - rect.width, rect.y + rect.height));
+		result.add(new Point2D.Double(rect.x + 2 * rect.width, rect.y + rect.height));
+
+		result.add(new Point2D.Double(rect.x - rect.width, rect.y + 2 * rect.height));
+		result.add(new Point2D.Double(rect.x, rect.y + 2 * rect.height));
+		result.add(new Point2D.Double(rect.x + rect.width, rect.y + 2 * rect.height));
+		result.add(new Point2D.Double(rect.x + 2 * rect.width, rect.y + 2 * rect.height));
+		return result;
+	}
+
+	public static List<Point2D.Double> get(Point2D.Double p1, Point2D.Double p2) {
+		final List<Point2D.Double> result = new ArrayList<Point2D.Double>();
+		result.add(new Point2D.Double(p1.x, p2.y));
+		result.add(new Point2D.Double(p2.x, p1.y));
+		return result;
+	}
+}
diff --git a/src/net/sourceforge/plantuml/graph2/MagicPointsFactory2.java b/src/net/sourceforge/plantuml/graph2/MagicPointsFactory2.java
new file mode 100644
index 0000000..2a954d0
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/MagicPointsFactory2.java
@@ -0,0 +1,72 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.AffineTransform;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.List;
+
+public class MagicPointsFactory2 {
+
+	private final Point2D.Double p1;
+	private final Point2D.Double p2;
+
+	private final List<Point2D.Double> result = new ArrayList<Point2D.Double>();
+
+	public MagicPointsFactory2(Point2D.Double p1, Point2D.Double p2) {
+		this.p1 = p1;
+		this.p2 = p2;
+		final double dx = p2.x - p1.x;
+		final double dy = p2.y - p1.y;
+
+		final int interv = 5;
+		final int intervAngle = 10;
+		final double theta = Math.PI * 2 / intervAngle;
+		for (int a = 0; a < 10; a++) {
+			final AffineTransform at = AffineTransform.getRotateInstance(theta * a, p1.x, p1.y);
+			for (int i = 0; i < interv * 2; i++) {
+				final Point2D.Double p = new Point2D.Double(p1.x + dx * i / interv, p1.y + dy * i / interv);
+				result.add((Point2D.Double) at.transform(p, null));
+			}
+		}
+
+	}
+
+	public List<Point2D.Double> get() {
+		return result;
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Measurer.java b/src/net/sourceforge/plantuml/graph2/Measurer.java
new file mode 100644
index 0000000..45ad6e0
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Measurer.java
@@ -0,0 +1,39 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+public interface Measurer<V> {
+	int getMeasure(V data);
+}
diff --git a/src/net/sourceforge/plantuml/graph2/MyCurve.java b/src/net/sourceforge/plantuml/graph2/MyCurve.java
new file mode 100644
index 0000000..5c546d7
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/MyCurve.java
@@ -0,0 +1,172 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.BasicStroke;
+import java.awt.Color;
+import java.awt.Graphics2D;
+import java.awt.geom.CubicCurve2D;
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
+import java.util.List;
+
+public class MyCurve {
+
+	private final CubicCurve2D.Double curve;
+	private final List<Line2D.Double> lines = new ArrayList<Line2D.Double>();
+	private final List<Line2D.Double> linesForInters = new ArrayList<Line2D.Double>();
+	private Color color = Color.GREEN;
+	private double lenght = 0;
+
+	public MyCurve(CubicCurve2D.Double curve) {
+		this.curve = curve;
+		addCurve(curve);
+		if (lenght <= 0) {
+			throw new IllegalStateException();
+		}
+		for (Line2D.Double line : lines) {
+			linesForInters.add(change(line, curve.getP1(), curve.getP2()));
+		}
+	}
+
+	private Line2D.Double change(Line2D.Double line, Point2D p1, Point2D p2) {
+		if (line.getP1().equals(p1) == false && line.getP2().equals(p2) == false) {
+			return line;
+		}
+		final double dx = line.x2 - line.x1;
+		final double dy = line.y2 - line.y1;
+		if (line.getP1().equals(p1)) {
+			p1 = new Point2D.Double(line.x1 + dx / 10, line.y1 + dy / 10);
+		} else {
+			p1 = line.getP1();
+		}
+		if (line.getP2().equals(p2)) {
+			p2 = new Point2D.Double(line.x2 - dx / 10, line.y2 - dy / 10);
+		} else {
+			p2 = line.getP2();
+		}
+		return new Line2D.Double(p1, p2);
+	}
+
+	public final double getLenght() {
+		return lenght;
+	}
+
+	private void addCurve(CubicCurve2D.Double peace) {
+		final Rectangle2D bounds = peace.getBounds2D();
+		final double flat = peace.getFlatness();
+		if (flat < 10) {
+			lines.add(new Line2D.Double(peace.getP1(), peace.getP2()));
+			lenght += Math.sqrt(bounds.getWidth() * bounds.getWidth() + bounds.getHeight() * bounds.getHeight());
+			return;
+		}
+		final CubicCurve2D.Double left = new CubicCurve2D.Double();
+		final CubicCurve2D.Double right = new CubicCurve2D.Double();
+		peace.subdivide(left, right);
+		addCurve(left);
+		addCurve(right);
+	}
+
+	public void drawDebug(Graphics2D g2d) {
+		for (Line2D r : linesForInters) {
+			g2d.setColor(color);
+			g2d.draw(r);
+		}
+		g2d.setColor(Color.BLACK);
+		// g2d.draw(curve);
+	}
+
+	public void draw(Graphics2D g2d) {
+		g2d.setStroke(new BasicStroke((float) 1.5));
+		g2d.draw(curve);
+		g2d.setStroke(new BasicStroke());
+	}
+
+	public final void setColor(Color color) {
+		this.color = color;
+	}
+
+	public boolean intersects(List<MyCurve> others) {
+		for (MyCurve other : others) {
+			if (this.intersects(other)) {
+				return true;
+			}
+		}
+		return false;
+	}
+
+	private boolean intersects(MyCurve other) {
+		for (Line2D.Double l1 : this.linesForInters) {
+			for (Line2D.Double l2 : other.linesForInters) {
+				if (l1.intersectsLine(l2)) {
+					return true;
+				}
+			}
+		}
+		return false;
+	}
+
+	public boolean intersects(RectanglesCollection forbidden) {
+		for (Rectangle2D.Double r : forbidden) {
+			for (Line2D.Double line : lines) {
+				if (r.intersectsLine(line)) {
+					return true;
+				}
+			}
+		}
+		return false;
+	}
+	// public static long TPS6;
+	//
+	// public RectanglesCollection unrecoveredBy(RectanglesCollection allFrames)
+	// {
+	// final long start = System.currentTimeMillis();
+	// try {
+	// final RectanglesCollection result = new RectanglesCollection();
+	// for (Rectangle2D.Double r : areas) {
+	// if (allFrames.intersect(new RectanglesCollection(r)) == false) {
+	// result.add(r);
+	// }
+	// }
+	// return result;
+	// } finally {
+	// TPS6 += System.currentTimeMillis() - start;
+	// }
+	// }
+	//
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Neighborhood2.java b/src/net/sourceforge/plantuml/graph2/Neighborhood2.java
new file mode 100644
index 0000000..f9e1926
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Neighborhood2.java
@@ -0,0 +1,189 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+
+import net.sourceforge.plantuml.geom.Orientation;
+
+public class Neighborhood2 {
+
+	final private double angle1;
+	final private double angle2;
+	final private Point2D.Double center;
+
+	public Neighborhood2(Point2D.Double center) {
+		this(center, 0, 0);
+	}
+
+	public boolean is360() {
+		return angle1 == angle2;
+	}
+
+	public Neighborhood2(Point2D.Double center, double angle1, double angle2) {
+		this.center = center;
+		this.angle1 = angle1;
+		this.angle2 = angle2;
+	}
+
+	@Override
+	public boolean equals(Object obj) {
+		final Neighborhood2 other = (Neighborhood2) obj;
+		return angle1 == other.angle1 && angle2 == other.angle2 && center.equals(other.center);
+	}
+
+	@Override
+	public int hashCode() {
+		return center.hashCode() * 17 + new Point2D.Double(angle1, angle2).hashCode();
+	}
+
+	@Override
+	public String toString() {
+		final int a1 = (int) (angle1 * 180 / Math.PI);
+		final int a2 = (int) (angle2 * 180 / Math.PI);
+		return center + " " + a1 + " " + a2;
+	}
+
+	public final Point2D.Double getCenter() {
+		return center;
+	}
+
+	// private double getMiddle() {
+	// if (is360()) {
+	// return angle1 + 2 * Math.PI / 3;
+	// }
+	// double result = (angle1 + angle2) / 2;
+	// if (angle2 < angle1) {
+	// result += Math.PI;
+	// }
+	// return result;
+	// }
+	//
+	public Point2D.Double getPointInNeighborhood(double dist, Point2D p1, Point2D p2) {
+		if (p1 == null || p2 == null) {
+			throw new IllegalArgumentException();
+		}
+		if (dist <= 0) {
+			throw new IllegalArgumentException();
+		}
+		final double v1 = Singularity2.convertAngle(Singularity2.getAngle(new Line2D.Double(center, p1)) - angle1);
+		final double v2 = Singularity2.convertAngle(Singularity2.getAngle(new Line2D.Double(center, p2)) - angle1);
+		if (v1 < 0) {
+			throw new IllegalStateException();
+		}
+		if (v2 < 0) {
+			throw new IllegalStateException();
+		}
+		final double middle = (v1 + v2) / 2 + angle1;
+		return new Point2D.Double(center.x + dist * Math.cos(middle), center.y + dist * Math.sin(middle));
+	}
+
+	public boolean isInAngleStrict(double angle) {
+		if (angle < 0) {
+			throw new IllegalArgumentException();
+		}
+		if (angle2 > angle1) {
+			return angle > angle1 && angle < angle2;
+		}
+		return angle > angle1 || angle < angle2;
+	}
+
+	public boolean isInAngleLarge(double angle) {
+		if (angle < 0) {
+			throw new IllegalArgumentException();
+		}
+		if (angle2 > angle1) {
+			return angle >= angle1 && angle <= angle2;
+		}
+		return angle >= angle1 || angle <= angle2;
+	}
+
+	public boolean isAngleLimit(double angle) {
+		return angle == angle1 || angle == angle2;
+	}
+
+	public Orientation getOrientationFrom(double angle) {
+		if (angle1 == angle2) {
+			throw new IllegalStateException();
+		}
+		if (angle != angle1 && angle != angle2) {
+			throw new IllegalArgumentException("this=" + this + " angle=" + (int) (angle * 180 / Math.PI));
+		}
+		assert angle == angle1 || angle == angle2;
+
+		if (angle == angle1) {
+			return Orientation.MATH;
+		}
+		return Orientation.CLOCK;
+	}
+
+	public boolean isConnectable(Neighborhood2 other) {
+		assert isConnectableInternal(other) == other.isConnectableInternal(this);
+		return isConnectableInternal(other);
+
+	}
+
+	private boolean isConnectableInternal(Neighborhood2 other) {
+		if (getCenter().equals(other.getCenter())) {
+			throw new IllegalArgumentException("Same center");
+		}
+		final Line2D.Double seg1 = new Line2D.Double(getCenter(), other.getCenter());
+
+		final double angle1 = Singularity2.convertAngle(Singularity2.getAngle(seg1));
+		final double angle2 = Singularity2.convertAngle(Singularity2.getOppositeAngle(seg1));
+		assert angle2 == Singularity2.convertAngle(Singularity2.getAngle(new Line2D.Double(other.getCenter(),
+				getCenter())));
+		if (isInAngleStrict(angle1) && other.isInAngleStrict(angle2)) {
+			return true;
+		}
+		if (isInAngleStrict(angle1) && other.isInAngleLarge(angle2)) {
+			return true;
+		}
+		if (isInAngleLarge(angle1) && other.isInAngleStrict(angle2)) {
+			return true;
+		}
+		if (isAngleLimit(angle1) && other.isAngleLimit(angle2)) {
+			if (is360() || other.is360()) {
+				return true;
+			}
+			final Orientation o1 = getOrientationFrom(angle1);
+			final Orientation o2 = other.getOrientationFrom(angle2);
+			return o1 != o2;
+		}
+		return false;
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Plan.java b/src/net/sourceforge/plantuml/graph2/Plan.java
new file mode 100644
index 0000000..f3699b6
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Plan.java
@@ -0,0 +1,254 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import net.sourceforge.plantuml.Log;
+import net.sourceforge.plantuml.graph2.Dijkstra.Vertex;
+
+public class Plan {
+
+	private final Map<Point2D.Double, Singularity2> points = new LinkedHashMap<Point2D.Double, Singularity2>();
+	private final Collection<Line2D.Double> lines = new ArrayList<Line2D.Double>();
+
+	public void addPoint2D(Point2D.Double point) {
+		if (points.containsKey(point)) {
+			throw new IllegalArgumentException();
+		}
+		points.put(point, new Singularity2(point));
+	}
+
+	public void debugPrint() {
+		Log.println("PLAN PRINT");
+		for (Singularity2 s : points.values()) {
+			Log.println("s="+s);
+		}
+		for (Line2D.Double l : lines) {
+			Log.println(GeomUtils.toString(l));
+		}
+	}
+
+	public void createLink(Point2D p1, Point2D p2) {
+		final Singularity2 s1 = points.get(p1);
+		final Singularity2 s2 = points.get(p2);
+		if (s1 == null || s2 == null) {
+			throw new IllegalArgumentException();
+		}
+		final Line2D.Double line = new Line2D.Double(p1, p2);
+
+		s1.addLineSegment(line);
+		s2.addLineSegment(line);
+		lines.add(line);
+	}
+
+	Singularity2 getSingularity(Point2D pt) {
+		final Singularity2 result = points.get(pt);
+		if (result == null) {
+			throw new IllegalArgumentException();
+		}
+		return result;
+	}
+
+	List<Neighborhood2> getShortestPathToInternal(Point2D start, Point2D end) {
+		final Dijkstra dijkstra = new Dijkstra();
+		if (points.containsKey(start) == false || points.containsKey(end) == false) {
+			throw new IllegalArgumentException();
+		}
+		final Vertex vStart = dijkstra.addVertex(start);
+		final Vertex vEnd = dijkstra.addVertex(end);
+		final Map<Neighborhood2, Vertex> vertexes = new LinkedHashMap<Neighborhood2, Vertex>();
+		for (Singularity2 s : points.values()) {
+			for (Neighborhood2 n : s.getNeighborhoods()) {
+				final Vertex v = dijkstra.addVertex(n);
+				vertexes.put(n, v);
+				if (n.getCenter().equals(start)) {
+					vStart.addAdjacencies(v, 0.01);
+				}
+				if (n.getCenter().equals(end)) {
+					v.addAdjacencies(vEnd, 0.01);
+				}
+			}
+		}
+
+		for (Vertex v1 : vertexes.values()) {
+			for (Vertex v2 : vertexes.values()) {
+				final Neighborhood2 n1 = (Neighborhood2) v1.getData();
+				final Neighborhood2 n2 = (Neighborhood2) v2.getData();
+				if (n1.getCenter().equals(n2.getCenter())) {
+					continue;
+				}
+				final Line2D.Double line = new Line2D.Double(n1.getCenter(), n2.getCenter());
+				if (isStrictCrossing(line)) {
+					continue;
+				}
+				if (n1.isConnectable(n2) == false) {
+					continue;
+				}
+				final double dist = n1.getCenter().distance(n2.getCenter());
+				v1.addAdjacencies(v2, dist);
+				v2.addAdjacencies(v1, dist);
+				// Log.println("=(" + n1 + ") (" + n2 + ") " + dist);
+			}
+		}
+
+		final List<Vertex> list = dijkstra.getShortestPathTo(vStart, vEnd);
+		if (list.size() < 2) {
+			throw new IllegalStateException("list=" + list);
+		}
+		final List<Neighborhood2> result = new ArrayList<Neighborhood2>();
+		for (Vertex v : list.subList(1, list.size() - 1)) {
+			result.add((Neighborhood2) v.getData());
+		}
+		return result;
+	}
+
+	public List<Point2D.Double> getIntermediatePoints(Point2D start, Point2D end) {
+		// Log.println("start=" + start + " end=" + end);
+		final List<Point2D.Double> result = new ArrayList<Point2D.Double>();
+		final List<Neighborhood2> list = getShortestPathToInternal(start, end);
+		// Log.println("Neighborhood2 = " + list);
+		for (int i = 1; i < list.size() - 1; i++) {
+			final Neighborhood2 n = list.get(i);
+			final Point2D.Double before = list.get(i - 1).getCenter();
+			final Point2D.Double after = list.get(i + 1).getCenter();
+			// Log.println("before="+before);
+			// Log.println("after="+after);
+			// Log.println("n.getCenter()="+n.getCenter());
+			// Log.println("getMindist(n.getCenter())="+getMindist(n.getCenter()));
+			final Point2D.Double pointInNeighborhood = n.getPointInNeighborhood(getMindist(n.getCenter()) / 2, before,
+					after);
+			// Log.println("pointInNeighborhood="+pointInNeighborhood);
+			result.add(pointInNeighborhood);
+		}
+		return result;
+
+	}
+
+	private boolean isStrictCrossing(Line2D.Double line) {
+		for (Line2D.Double l : lines) {
+			if (intersectsLineStrict(l, line)) {
+				return true;
+			}
+		}
+		return false;
+	}
+
+	public static boolean intersectsLineStrict(Line2D.Double l1, Line2D.Double l2) {
+		assert intersectsLineStrictInternal(l1, l2) == intersectsLineStrictInternal(l2, l1);
+		assert intersectsLineStrictInternal(l1, l2) == intersectsLineStrictInternal(inverse(l1), l2);
+		assert intersectsLineStrictInternal(l1, l2) == intersectsLineStrictInternal(l1, inverse(l2));
+		assert intersectsLineStrictInternal(l1, l2) == intersectsLineStrictInternal(inverse(l1), inverse(l2));
+		return intersectsLineStrictInternal(l1, l2);
+	}
+
+	private static Line2D.Double inverse(Line2D.Double line) {
+		return new Line2D.Double(line.getP2(), line.getP1());
+	}
+
+	private static boolean intersectsLineStrictInternal(Line2D.Double l1, Line2D.Double l2) {
+		if (l1.intersectsLine(l2) == false) {
+			return false;
+		}
+		assert l1.intersectsLine(l2);
+
+		Point2D.Double l1a = (Point2D.Double) l1.getP1();
+		Point2D.Double l1b = (Point2D.Double) l1.getP2();
+		Point2D.Double l2a = (Point2D.Double) l2.getP1();
+		Point2D.Double l2b = (Point2D.Double) l2.getP2();
+
+		if (l1a.equals(l2a) == false && l1a.equals(l2b) == false && l1b.equals(l2a) == false
+				&& l1b.equals(l2b) == false) {
+			return true;
+		}
+
+		if (l1a.equals(l2b)) {
+			final Point2D.Double tmp = l2a;
+			l2a = l2b;
+			l2b = tmp;
+		} else if (l2a.equals(l1b)) {
+			final Point2D.Double tmp = l1a;
+			l1a = l1b;
+			l1b = tmp;
+		} else if (l1b.equals(l2b)) {
+			Point2D.Double tmp = l2a;
+			l2a = l2b;
+			l2b = tmp;
+			tmp = l1a;
+			l1a = l1b;
+			l1b = tmp;
+		}
+
+		assert l1a.equals(l2a);
+
+		return false;
+
+	}
+
+	final double getMindist(Point2D.Double pt) {
+		double result = Double.MAX_VALUE;
+		for (Point2D p : points.keySet()) {
+			if (pt.equals(p)) {
+				continue;
+			}
+			final double v = p.distance(pt);
+			if (v < 1E-4) {
+				throw new IllegalStateException();
+			}
+			result = Math.min(result, v);
+		}
+		for (Line2D line : lines) {
+			if (line.getP1().equals(pt) || line.getP2().equals(pt)) {
+				continue;
+			}
+			final double v = line.ptSegDist(pt);
+			if (result < 1E-4) {
+				throw new IllegalStateException("pt=" + pt + " line=" + GeomUtils.toString(line));
+			}
+			result = Math.min(result, v);
+		}
+		if (result == 0) {
+			throw new IllegalStateException();
+		}
+		// Log.println("getMindist=" + result);
+		return result;
+	}
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Polyline2.java b/src/net/sourceforge/plantuml/graph2/Polyline2.java
new file mode 100644
index 0000000..b510b17
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Polyline2.java
@@ -0,0 +1,110 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.Color;
+import java.awt.Graphics2D;
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.awt.geom.QuadCurve2D;
+import java.util.ArrayList;
+import java.util.List;
+
+public class Polyline2 {
+
+	private final List<Line2D.Double> lines = new ArrayList<Line2D.Double>();
+	private Point2D lastCurrent;
+	private final Point2D end;
+
+	public Polyline2(Point2D start, Point2D end) {
+		lastCurrent = start;
+		this.end = end;
+	}
+
+	public void addLine(Line2D.Double newLine) {
+		// Log.println("# Polyline2::addLine " +
+		// GeomUtils.toString(newLine));
+		if (lastCurrent.equals(newLine.getP1()) == false) {
+			lines.add(new Line2D.Double(lastCurrent, newLine.getP1()));
+		}
+		lines.add(newLine);
+		lastCurrent = newLine.getP2();
+	}
+
+	private boolean debug = false;
+
+	public void draw(Graphics2D g2d) {
+		close();
+		if (debug) {
+			g2d.setColor(Color.GREEN);
+			drawDebug(g2d);
+		}
+		g2d.setColor(Color.BLUE);
+		final List<Point2D.Double> centers = new ArrayList<Point2D.Double>();
+		for (Line2D.Double l : lines) {
+			centers.add(GeomUtils.getCenter(l));
+		}
+		g2d.draw(new Line2D.Double(lines.get(0).getP1(), centers.get(0)));
+		g2d.draw(new Line2D.Double(centers.get(centers.size() - 1), end));
+		for (int i = 0; i < lines.size() - 1; i++) {
+			final Point2D c1 = centers.get(i);
+			final Point2D c2 = centers.get(i + 1);
+			final Point2D ctrl = lines.get(i).getP2();
+			assert ctrl.equals(lines.get(i + 1).getP1());
+			final QuadCurve2D.Double quad = new QuadCurve2D.Double(c1.getX(), c1.getY(), ctrl.getX(), ctrl.getY(), c2
+					.getX(), c2.getY());
+			g2d.draw(quad);
+		}
+		if (debug) {
+			for (Point2D.Double c : centers) {
+				GeomUtils.fillPoint2D(g2d, c);
+			}
+		}
+	}
+
+	private void drawDebug(Graphics2D g2d) {
+		for (Line2D.Double l : lines) {
+			g2d.draw(l);
+			GeomUtils.fillPoint2D(g2d, l.getP1());
+			GeomUtils.fillPoint2D(g2d, l.getP2());
+		}
+	}
+
+	private void close() {
+		if (lastCurrent.equals(end) == false) {
+			lines.add(new Line2D.Double(lastCurrent, end));
+		}
+	}
+}
diff --git a/src/net/sourceforge/plantuml/graph2/RectanglesCollection.java b/src/net/sourceforge/plantuml/graph2/RectanglesCollection.java
new file mode 100644
index 0000000..824e2d4
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/RectanglesCollection.java
@@ -0,0 +1,199 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Rectangle2D;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+public class RectanglesCollection implements Iterable<Rectangle2D.Double> {
+
+	private final List<Rectangle2D.Double> areas = new ArrayList<Rectangle2D.Double>();
+	private final SortedListImpl<Rectangle2D.Double> sortedX1;
+	private final SortedListImpl<Rectangle2D.Double> sortedX2;
+	private final SortedListImpl<Rectangle2D.Double> sortedY1;
+	private final SortedListImpl<Rectangle2D.Double> sortedY2;
+
+	private Rectangle2D.Double max = null;
+
+	public RectanglesCollection() {
+		sortedX1 = new SortedListImpl<Rectangle2D.Double>(new Measurer<Rectangle2D.Double>() {
+			public int getMeasure(Rectangle2D.Double data) {
+				return (int) data.x;
+			}
+		});
+		sortedX2 = new SortedListImpl<Rectangle2D.Double>(new Measurer<Rectangle2D.Double>() {
+			public int getMeasure(Rectangle2D.Double data) {
+				return (int) (data.x + data.width);
+			}
+		});
+		sortedY1 = new SortedListImpl<Rectangle2D.Double>(new Measurer<Rectangle2D.Double>() {
+			public int getMeasure(Rectangle2D.Double data) {
+				return (int) data.y;
+			}
+		});
+		sortedY2 = new SortedListImpl<Rectangle2D.Double>(new Measurer<Rectangle2D.Double>() {
+			public int getMeasure(Rectangle2D.Double data) {
+				return (int) (data.y + data.height);
+			}
+		});
+	}
+
+	public RectanglesCollection(Rectangle2D.Double rect) {
+		this();
+		add(rect);
+	}
+
+	public double getSurf() {
+		if (max == null) {
+			return 0;
+		}
+		return max.getWidth() * max.getHeight();
+	}
+
+	public void add(Rectangle2D.Double rect) {
+		areas.add(rect);
+		// sortedX1.add(rect);
+		// sortedX2.add(rect);
+		// sortedY1.add(rect);
+		// sortedY2.add(rect);
+		if (max == null) {
+			max = rect;
+		} else {
+			max = (Rectangle2D.Double) max.createUnion(rect);
+		}
+	}
+
+	public Iterator<Rectangle2D.Double> iterator() {
+		return areas.iterator();
+	}
+
+	public boolean intersect(RectanglesCollection other) {
+		if (this.size() > other.size()) {
+			return intersectSeveral(this, other);
+		}
+		return intersectSeveral(other, this);
+	}
+
+	static private long TPS1;
+	static private long TPS2;
+
+	private static boolean intersectSeveral(RectanglesCollection large, RectanglesCollection compact) {
+		assert large.size() >= compact.size();
+		final long start = System.currentTimeMillis();
+		try {
+			for (Rectangle2D.Double r : compact) {
+				if (large.intersectSimple(r)) {
+					return true;
+				}
+			}
+			return false;
+		} finally {
+			TPS2 += System.currentTimeMillis() - start;
+		}
+	}
+
+	private boolean intersectSimple(Rectangle2D.Double rect) {
+		final long start = System.currentTimeMillis();
+		try {
+			if (max == null || max.intersects(rect) == false) {
+				return false;
+			}
+			for (Rectangle2D.Double r : areas) {
+				if (rect.intersects(r)) {
+					return true;
+				}
+			}
+			return false;
+		} finally {
+			TPS1 += System.currentTimeMillis() - start;
+		}
+	}
+
+	private boolean intersectSimpleOld(Rectangle2D.Double rect) {
+		final long start = System.currentTimeMillis();
+		try {
+			if (max == null || max.intersects(rect) == false) {
+				return false;
+			}
+			final List<Rectangle2D.Double> lX1 = sortedX1.lesserOrEquals((int) (rect.x + rect.width));
+			List<Rectangle2D.Double> lmin = lX1;
+			if (lX1.size() == 0) {
+				return false;
+			}
+			final List<Rectangle2D.Double> lX2 = sortedX2.biggerOrEquals((int) rect.x);
+			if (lX2.size() == 0) {
+				return false;
+			}
+			if (lX2.size() < lmin.size()) {
+				lmin = lX2;
+			}
+			final List<Rectangle2D.Double> lY1 = sortedY1.lesserOrEquals((int) (rect.y + rect.height));
+			if (lY1.size() == 0) {
+				return false;
+			}
+			if (lY1.size() < lmin.size()) {
+				lmin = lY1;
+			}
+			final List<Rectangle2D.Double> lY2 = sortedY2.biggerOrEquals((int) rect.y);
+			if (lY2.size() == 0) {
+				return false;
+			}
+			if (lY2.size() < lmin.size()) {
+				lmin = lY2;
+			}
+			for (Rectangle2D.Double r : lmin) {
+				if (rect.intersects(r)) {
+					return true;
+				}
+			}
+			return false;
+		} finally {
+			TPS1 += System.currentTimeMillis() - start;
+		}
+	}
+
+	public int size() {
+		return areas.size();
+	}
+
+	public void addAll(RectanglesCollection other) {
+		for (Rectangle2D.Double r : other.areas) {
+			this.add(r);
+		}
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/Singularity2.java b/src/net/sourceforge/plantuml/graph2/Singularity2.java
new file mode 100644
index 0000000..58459fd
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/Singularity2.java
@@ -0,0 +1,163 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.TreeSet;
+
+public class Singularity2 {
+
+	private final TreeSet<Double> angles = new TreeSet<Double>();
+
+	final private Point2D.Double center;
+
+	public Singularity2(Point2D.Double center) {
+		this.center = center;
+	}
+
+	@Override
+	public String toString() {
+		final StringBuilder sb = new StringBuilder(center.toString());
+		for (Double a : angles) {
+			final int degree = (int) (a * 180 / Math.PI);
+			sb.append(' ');
+			sb.append(degree);
+		}
+		return sb.toString();
+	}
+
+	public void addLineSegment(Line2D.Double seg) {
+		if (seg.getP1().equals(center)) {
+			angles.add(convertAngle(getAngle(seg)));
+		} else if (seg.getP2().equals(center)) {
+			angles.add(convertAngle(getOppositeAngle(seg)));
+		} else {
+			throw new IllegalArgumentException();
+		}
+		assert betweenZeroAndTwoPi();
+
+	}
+
+	static final double getAngle(Line2D.Double line) {
+		if (line.getP1().equals(line.getP2())) {
+			throw new IllegalArgumentException();
+		}
+		return Math.atan2(line.getP2().getY() - line.getP1().getY(), line.getP2().getX() - line.getP1().getX());
+	}
+
+	static final double getOppositeAngle(Line2D.Double line) {
+		return Math.atan2(line.getP1().getY() - line.getP2().getY(), line.getP1().getX() - line.getP2().getX());
+	}
+
+	static double convertAngle(double a) {
+		while (a < 0) {
+			a += 2 * Math.PI;
+		}
+		return a;
+	}
+
+	private boolean betweenZeroAndTwoPi() {
+		for (Double d : angles) {
+			assert d >= 0;
+			assert d < 2 * Math.PI;
+		}
+		return true;
+	}
+
+	List<Double> getAngles() {
+		return new ArrayList<Double>(angles);
+	}
+
+	public boolean crossing(Point2D.Double direction1, Point2D.Double direction2) {
+		final boolean result = crossingInternal(direction1, direction2);
+		assert result == crossingInternal(direction2, direction1);
+		return result;
+	}
+
+	private boolean crossingInternal(Point2D.Double direction1, Point2D.Double direction2) {
+		if (angles.size() < 2) {
+			return false;
+		}
+		final double angle1 = convertAngle(getAngle(new Line2D.Double(center, direction1)));
+		final double angle2 = convertAngle(getAngle(new Line2D.Double(center, direction2)));
+
+		Double last = null;
+		for (Double current : angles) {
+			if (last != null) {
+				assert last < current;
+				if (isBetween(angle1, last, current) && isBetween(angle2, last, current)) {
+					return false;
+				}
+			}
+			last = current;
+		}
+		final double first = angles.first();
+		if ((angle1 <= first || angle1 >= last) && (angle2 <= first || angle2 >= last)) {
+			return false;
+		}
+		return true;
+	}
+
+	private boolean isBetween(double test, double v1, double v2) {
+		assert v1 < v2;
+		return test >= v1 && test <= v2;
+	}
+
+	protected final Point2D.Double getCenter() {
+		return center;
+	}
+
+	public void merge(Singularity2 other) {
+		this.angles.addAll(other.angles);
+	}
+
+	public List<Neighborhood2> getNeighborhoods() {
+		if (angles.size() == 0) {
+			return Collections.singletonList(new Neighborhood2(center));
+		}
+		final List<Neighborhood2> result = new ArrayList<Neighborhood2>();
+		double last = angles.last();
+		for (Double currentAngle : angles) {
+			result.add(new Neighborhood2(center, last, currentAngle));
+			last = currentAngle;
+		}
+		return Collections.unmodifiableList(result);
+	}
+
+}
diff --git a/src/net/sourceforge/plantuml/graph2/SortedList.java b/src/net/sourceforge/plantuml/graph2/SortedList.java
new file mode 100644
index 0000000..f095062
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/SortedList.java
@@ -0,0 +1,45 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.util.List;
+
+public interface SortedList<V> extends Iterable<V> {
+	public void add(V data);
+
+	public List<V> lesserOrEquals(int v);
+
+	public List<V> biggerOrEquals(int v);
+}
diff --git a/src/net/sourceforge/plantuml/graph2/SortedListImpl.java b/src/net/sourceforge/plantuml/graph2/SortedListImpl.java
new file mode 100644
index 0000000..bbef49a
--- /dev/null
+++ b/src/net/sourceforge/plantuml/graph2/SortedListImpl.java
@@ -0,0 +1,128 @@
+/* ========================================================================
+ * PlantUML : a free UML diagram generator
+ * ========================================================================
+ *
+ * (C) Copyright 2009-2014, Arnaud Roques
+ *
+ * Project Info:  http://plantuml.sourceforge.net
+ * 
+ * This file is part of PlantUML.
+ *
+ * Licensed under The MIT License (Massachusetts Institute of Technology License)
+ * 
+ * See http://opensource.org/licenses/MIT
+ * 
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+ * IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ * 
+ *
+ * Original Author:  Arnaud Roques
+ */
+package net.sourceforge.plantuml.graph2;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+
+public class SortedListImpl<V> implements SortedList<V> {
+
+	static class NullableAndEvenMeasurer<V> implements Measurer<V> {
+		private final Measurer<V> wrapped;
+		private final int valueForNull;
+
+		NullableAndEvenMeasurer(Measurer<V> wrapped, int valueForNull, boolean plus) {
+			this.wrapped = wrapped;
+			if (plus) {
+				this.valueForNull = valueForNull * 2 + 1;
+			} else {
+				this.valueForNull = valueForNull * 2 - 1;
+			}
+		}
+
+		public int getMeasure(V data) {
+			if (data == null) {
+				return valueForNull;
+			}
+			return wrapped.getMeasure(data) * 2;
+		}
+	}
+
+	private final Measurer<V> measurer;
+	private final List<V> all = new ArrayList<V>();
+	private final Comparator<V> comparator;
+
+	public SortedListImpl(Measurer<V> m) {
+		this.measurer = m;
+		this.comparator = new Comparator<V>() {
+			public int compare(V o1, V o2) {
+				final int v1 = measurer.getMeasure(o1);
+				final int v2 = measurer.getMeasure(o2);
+				return v1 - v2;
+			}
+		};
+	}
+
+	public void add(V data) {
+		final int pos = Collections.binarySearch(all, data, comparator);
+		if (pos >= 0) {
+			all.add(pos, data);
+		} else {
+			all.add(-pos - 1, data);
+		}
+		assert isSorted();
+	}
+
+	private int getPos(int v, boolean plus) {
+		final Measurer<V> m = new NullableAndEvenMeasurer<V>(measurer, v, plus);
+		final Comparator<V> myComp = new Comparator<V>() {
+			public int compare(V o1, V o2) {
+				final int v1 = m.getMeasure(o1);
+				final int v2 = m.getMeasure(o2);
+				return v1 - v2;
+			}
+		};
+		final int pos = Collections.binarySearch(all, null, myComp);
+		assert pos < 0;
+		return -pos - 1;
+	}
+
+	public List<V> lesserOrEquals(int v) {
+		return all.subList(0, getPos(v, true));
+	}
+
+	public List<V> biggerOrEquals(int v) {
+		return all.subList(getPos(v, false), all.size());
+	}
+
+	private boolean isSorted() {
+		for (int i = 0; i < all.size() - 1; i++) {
+			final int v1 = measurer.getMeasure(all.get(i));
+			final int v2 = measurer.getMeasure(all.get(i + 1));
+			if (v1 > v2) {
+				return false;
+			}
+		}
+		return true;
+	}
+
+	public Iterator<V> iterator() {
+		return all.iterator();
+	}
+
+}
author	Andrew Shadura <andrew@shadura.me>	2015-07-21 14:52:03 +0200
committer	Andrew Shadura <andrew@shadura.me>	2015-07-21 14:52:03 +0200
commit	26b872bb194ec7622997914bba53309a94b64d20 (patch)
tree	a79b966bf55dd61702b900b8ba40be4d2b3403db /src/net/sourceforge/plantuml/graph2