X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.g2d%2Fsrc%2Forg%2Fsimantics%2Fg2d%2Futils%2FGeometryUtils.java;h=9f668983a34ed3af632d8337e9333c4d864fcdb1;hb=78d831a19c254d829e45d04c5ec6a3057680b7d7;hp=73d0f54146095d46420fc9847176be5197a110a5;hpb=969bd23cab98a79ca9101af33334000879fb60c5;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.g2d/src/org/simantics/g2d/utils/GeometryUtils.java b/bundles/org.simantics.g2d/src/org/simantics/g2d/utils/GeometryUtils.java
index 73d0f5414..9f668983a 100644
--- a/bundles/org.simantics.g2d/src/org/simantics/g2d/utils/GeometryUtils.java
+++ b/bundles/org.simantics.g2d/src/org/simantics/g2d/utils/GeometryUtils.java
@@ -1,529 +1,529 @@
-/*******************************************************************************
- * Copyright (c) 2007, 2010 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.g2d.utils;
-
-import java.awt.BasicStroke;
-import java.awt.Color;
-import java.awt.Polygon;
-import java.awt.Shape;
-import java.awt.Stroke;
-import java.awt.geom.AffineTransform;
-import java.awt.geom.Area;
-import java.awt.geom.Ellipse2D;
-import java.awt.geom.Path2D;
-import java.awt.geom.PathIterator;
-import java.awt.geom.Point2D;
-import java.awt.geom.Rectangle2D;
-import java.util.List;
-
-import org.simantics.scenegraph.utils.TransformedRectangle;
-
-/**
- * Geometry related Utilities
- *
- * @see PathUtils2 Path related utilities
- * 
- * @author Toni Kalajainen
- * @author Tuukka Lehtonen
- */
-public final class GeometryUtils {
-
-    //public static final double EPSILON = 1e-7;
-
-    public static final BasicStroke BASIC_STROKE = new BasicStroke();
-
-    public static BasicStroke scaleStroke(Stroke stroke, float factor)
-    {
-        BasicStroke s = (BasicStroke) stroke;
-        float[] dash = s.getDashArray();
-        if (dash!=null) {
-            assert(factor!=0);
-            dash = scaleArray(factor, dash, new float[dash.length]);
-        }
-        if (dash==null)
-            return new BasicStroke(
-                    s.getLineWidth() * factor,
-                    s.getEndCap(),
-                    s.getLineJoin(),
-                    s.getMiterLimit()
-            );
-        return new BasicStroke(
-                s.getLineWidth() * factor,
-                s.getEndCap(),
-                s.getLineJoin(),
-                s.getMiterLimit(),
-                dash,
-                s.getDashPhase() * factor
-        );
-    }
-
-
-
-    /**
-     * Scales every element in array
-     * @param array
-     * @param factor
-     * @return new scaled array
-     */
-    public static float[] scaleArray(float factor, float [] array, float [] targetArray)
-    {
-        assert(array!=null);
-        if (targetArray==null)
-            targetArray = new float[array.length];
-        for (int i=0; i<array.length; i++)
-        {
-            targetArray[i] = array[i] * factor;
-        }
-        return targetArray;
-    }
-
-    /**
-     * Get x/y scale of a transform
-     * @param at
-     * @param pt
-     * @return
-     */
-    public static Point2D getScaleXY(AffineTransform at, Point2D pt)
-    {
-        double m00 = at.getScaleX();
-        double m11 = at.getScaleY();
-        double m10 = at.getShearY();
-        double m01 = at.getShearX();
-        // Project unit vector to canvas
-        double sx = Math.sqrt( m00*m00+m10*m10 );
-        double sy = Math.sqrt( m01*m01+m11*m11 );
-        if (pt==null) pt = new Point2D.Double();
-        pt.setLocation(sx, sy);
-        return pt;
-    }
-
-    /**
-     * Get scale of a transform
-     * @param at
-     * @param pt
-     * @return
-     */
-    /*
-	public static double getScale(AffineTransform at)
-	{
-		double m00 = at.getScaleX();
-		double m11 = at.getScaleY();
-		double m10 = at.getShearY();
-		double m01 = at.getShearX();
-		// Project unit vector to canvas
-		double sx = Math.sqrt( m00*m00+m10*m10 );
-		double sy = Math.sqrt( m01*m01+m11*m11 );
-		return Math.sqrt(sx*sx+sy*sy);
-	}   */
-
-    /*
-	public static double getScale(AffineTransform at)
-	{
-		double m00 = at.getScaleX();
-		double m11 = at.getScaleY();
-		double m10 = at.getShearY();
-		double m01 = at.getShearX();
-
-		double a = m00 + m11;
-		double b = 4.0 * m10*m01 + (m00 - m11) * (m00 - m11);
-		if(b <= 0.0)
-			return 0.5 * Math.sqrt(a*a + b);
-		else
-			return 0.5 * (Math.abs(a) + Math.sqrt(b));
-	}*/
-
-    public static double getScale(AffineTransform at)
-    {
-        double m00 = at.getScaleX();
-        double m11 = at.getScaleY();
-        double m10 = at.getShearY();
-        double m01 = at.getShearX();
-
-        return Math.sqrt(Math.abs(m00*m11 - m10*m01));
-    }
-
-    /**
-     * Computes the greatest absolute value of the eigenvalues
-     * of the matrix.
-     */
-    public static double getMaxScale(AffineTransform at)
-    {
-        double m00 = at.getScaleX();
-        double m11 = at.getScaleY();
-        double m10 = at.getShearY();
-        double m01 = at.getShearX();
-
-        /*
-         * If a and b are the eigenvalues of the matrix,
-         * then
-         *   trace       = a + b
-         *   determinant = a*b
-         */
-        double trace = m00 + m11;
-        double determinant = m00*m11 - m10*m01;
-
-        double dd = trace*trace*0.25 - determinant;
-        if(dd >= 0.0) {
-            /*
-             * trace/2 +- sqrt(trace^2 / 4 - determinant)
-             * = (a+b)/2 +- sqrt((a+b)^2 / 4 - a b)
-             * = (a+b)/2 +- sqrt(a^2 / 4 + a b / 2 + b^2 / 4 - a b)
-             * = (a+b)/2 +- sqrt(a^2 / 4 - a b / 2 + b^2 / 4)
-             * = (a+b)/2 +- (a-b)/2
-             * = a or b
-             * 
-             * Thus the formula below calculates the greatest
-             * absolute value of the eigenvalues max(abs(a), abs(b))
-             */
-            return Math.abs(trace*0.5) + Math.sqrt(dd);
-        }
-        else {
-            /*
-             * If dd < 0, then the eigenvalues a and b are not real.
-             * Because both trace and determinant are real, a and b
-             * have form:
-             *   a = x + i y
-             *   b = x - i y
-             * 
-             * Then
-             *    sqrt(determinant)
-             *    = sqrt(a b)
-             *    = sqrt(x^2 + y^2),
-             * which is the absolute value of the eigenvalues.
-             */
-            return Math.sqrt(determinant);
-        }
-    }
-
-    /**
-     * Intersect test of two shapes
-     * @param s1
-     * @param s2
-     * @return
-     */
-    public static boolean intersects(Shape s1, Shape s2)
-    {
-        if (s1==s2) return true;
-        if (s1.equals(s2)) return true;
-        if (s1 instanceof Rectangle2D)
-            return s2.intersects((Rectangle2D) s1);
-        if (s2 instanceof Rectangle2D)
-            return s1.intersects((Rectangle2D) s2);
-        if (s1 instanceof TransformedRectangle)
-            return ((TransformedRectangle)s1).intersects(s2);
-        if (s2 instanceof TransformedRectangle)
-            return ((TransformedRectangle)s2).intersects(s1);
-
-        // VERY SLOW IMPLEMENTATION
-        // Convert shapes to areas and intersect them
-        Area a1 = new Area(s1);
-        Area a2 = new Area(s2);
-        a1.intersect(a2);
-        return !a1.isEmpty();
-    }
-
-    /**
-     * Contains test of two shapes
-     * @param s1
-     * @param s2
-     * @return <code>true</code> if s1 contains s2, else <code>false</code>
-     */
-    public static boolean contains(Shape s1, Shape s2)
-    {
-        if (s1==s2) return true;
-        if (s1.equals(s2)) return true;
-        if (s2 instanceof Rectangle2D)
-            return s1.contains((Rectangle2D) s2);
-        if (s1 instanceof Rectangle2D)
-            return contains((Rectangle2D)s1, s2);
-        if (s1 instanceof TransformedRectangle)
-            return ((TransformedRectangle)s1).contains(s2);
-
-        // VERY SLOW IMPLEMENTATION
-        // Convert shapes to areas and intersect them
-        Area a1 = new Area(s1);
-        Area a2 = new Area(s2);
-        a2.subtract(a1);
-        return a2.isEmpty();
-    }
-
-    /**
-     * Tests if rectangle contains a shape
-     * @param r rectangle
-     * @param s shape to be tested
-     * @return <code>true</code> if r contains s, else <code>false</code>
-     */
-    public static boolean contains(Rectangle2D r, Shape s)
-    {
-        // Rectangle contains a shape if
-        //  all points of the shape are contained in r
-        PathIterator pi = s.getPathIterator(null, Double.MAX_VALUE);
-        double coords[] = new double[6];
-        while (!pi.isDone()) {
-            int type = pi.currentSegment(coords);
-            if (type == PathIterator.SEG_MOVETO || type == PathIterator.SEG_LINETO)
-            {
-                if (!r.contains(coords[0], coords[1]))
-                    return false;
-            }
-            assert(type != PathIterator.SEG_CUBICTO && type != PathIterator.SEG_QUADTO);
-            pi.next();
-        }
-        return true;
-    }
-
-    /**
-     * Creates new transformed shape
-     * @param s shape to be transformed
-     * @param t transform
-     * @return new transformed shape
-     */
-    public static Shape transformShape(Shape s, AffineTransform t)
-    {
-        if (t.isIdentity()) return s;
-        if (s instanceof Rectangle2D) {
-            Rectangle2D rect = (Rectangle2D) s;
-            int type = t.getType();
-            if (type == AffineTransform.TYPE_IDENTITY) {
-                Rectangle2D r = new Rectangle2D.Double();
-                r.setFrame(rect);
-                return r;
-            }
-            if ((type & (AffineTransform.TYPE_GENERAL_ROTATION|AffineTransform.TYPE_GENERAL_TRANSFORM) ) != 0)
-                return new TransformedRectangle(rect, t);
-            return org.simantics.scenegraph.utils.GeometryUtils.transformRectangle(t, rect);
-        }
-        if (s instanceof TransformedRectangle)
-        {
-            TransformedRectangle tr = (TransformedRectangle) s;
-            TransformedRectangle result = new TransformedRectangle(tr);
-            result.concatenate(t);
-            return result;
-        }
-
-        //return t.createTransformedShape(s);
-        //return new Area(s).createTransformedArea(t);
-        Area result = new Area(s);
-        result.transform(t);
-        return result;
-    }
-
-    /**
-     * Get compass direction. 0 = north, clockwise
-     * @param pt
-     * @return
-     */
-    public static double getCompassDirection(Point2D pt) {
-        return getCompassDirection(pt.getX(), pt.getY());
-    }
-
-    /**
-     * Get compass direction for the vector p1&rarr;p2. 0 = north, clockwise
-     * 
-     * @param p1 the start of the vector
-     * @param p2 the end of the vector
-     * @return compass direction
-     */
-    public static double getCompassDirection(Point2D p1, Point2D p2) {
-        double dx = p2.getX() - p1.getX();
-        double dy = p2.getY() - p1.getY();
-        return getCompassDirection(dx, dy);
-    }
-
-    /**
-     * Get compass direction. 0 = north, clockwise
-     * @param pt
-     * @return
-     */
-    public static double getCompassDirection(double x, double y) {
-        double rad = Math.atan2(y, x);
-        double deg = rad*180.0 / Math.PI + 90.0;
-        if (deg<0) deg = 360+deg;
-        return deg;
-    }
-
-    /**
-     * Converts compass direction to unit vector
-     * @param deg compass direction
-     * @param uv
-     * @return
-     */
-    public static Point2D toUnitVector(double deg, Point2D uv)
-    {
-        if (uv==null) uv = new Point2D.Double();
-        double x=0, y=0;
-        if (deg==0) {
-            y=-1;
-        } else if (deg==90) {
-            x=1;
-        } else if (deg==180) {
-            y=1;
-        } else if (deg==270) {
-            x=-1;
-        } else {
-            double rad = (deg-90)*Math.PI/180.0;
-            y = Math.sin(rad);
-            x = Math.cos(rad);
-        }
-        uv.setLocation(x, y);
-        return uv;
-    }
-
-    /**
-     * Convert compass direction to radian presentation (0=right, CCW)
-     * @param deg
-     * @return radians
-     */
-    public static double compassToRad(double deg) {
-        double rad = (deg-90)*Math.PI/180.0;
-        return rad;
-
-    }
-
-    /**
-     * Interpolate between two colors
-     * @param c1
-     * @param c2
-     * @param phase 0..1 (0=c1, 1=c2)
-     * @return
-     */
-    public static Color interpolate(Color c1, Color c2, double phase)
-    {
-        float r = (c1.getRed()/255.0f)*(1-(float)phase) + (c2.getRed()/255.0f)*((float)phase);
-        float g = (c1.getGreen()/255.0f)*(1-(float)phase) + (c2.getGreen()/255.0f)*((float)phase);
-        float b = (c1.getBlue()/255.0f)*(1-(float)phase) + (c2.getBlue()/255.0f)*((float)phase);
-        float a = (c1.getAlpha()/255.0f)*(1-(float)phase) + (c2.getAlpha()/255.0f)*((float)phase);
-        return new Color(r, g, b, a);
-    }
-
-    public static Path2D buildPath(List<Point2D> positions)
-    {
-        Path2D result = new Path2D.Double();
-        if (positions.size()==0) return result;
-        Point2D pos = positions.get(0);
-        result.moveTo(pos.getX(), pos.getY());
-        for (int i=1; i<positions.size(); i++)
-        {
-            pos = positions.get(i);
-            result.lineTo(pos.getX(), pos.getY());
-        }
-        return result;
-    }
-
-    /**
-     * Get path positions
-     * 
-     * @param path path
-     * @param positions positions
-     */
-    public static void getPoints(Path2D path, List<Point2D> positions)
-    {
-        PathIterator pi = path.getPathIterator(null);
-        double mat[] = new double[6];
-        while (!pi.isDone()) {
-            pi.currentSegment(mat);
-            positions.add(new Point2D.Double(mat[0], mat[1]));
-            pi.next();
-        }
-    }
-
-    // Tests intersects and contains
-    public static void main(String[] args) {
-/*
-		System.out.println(toUnitVector(getCompassDirection(0, -1), null));
-		System.out.println(toUnitVector(getCompassDirection(1, -1), null));
-		System.out.println(toUnitVector(getCompassDirection(1,  0), null));
-		System.out.println(toUnitVector(getCompassDirection(1,  1), null));
-		System.out.println(toUnitVector(getCompassDirection(0,  1), null));
-		System.out.println(toUnitVector(getCompassDirection(-1, 1), null));
-		System.out.println(toUnitVector(getCompassDirection(-1, 0), null));
-		System.out.println(toUnitVector(getCompassDirection(-1,-1), null));
-
-		System.out.println(getCompassDirection(0, -1));
-		System.out.println(getCompassDirection(1, -1));
-		System.out.println(getCompassDirection(1,  0));
-		System.out.println(getCompassDirection(1,  1));
-		System.out.println(getCompassDirection(0,  1));
-		System.out.println(getCompassDirection(-1, 1));
-		System.out.println(getCompassDirection(-1, 0));
-		System.out.println(getCompassDirection(-1,-1));
-
-        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, -1)));
-        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(1, 0)));
-        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, 1)));
-        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(-1, 0)));
- */
-        Shape s1 = new Polygon(new int[]{10,10,0}, new int[]{0,10,10}, 3);
-        Shape s2 = new Ellipse2D.Double(0,0,5,5);
-        Shape s3 = new Ellipse2D.Double(8,8,4,4);
-        Shape s4 = new Rectangle2D.Double(-5, 3, 20, 2);
-        Shape s5 = new Rectangle2D.Double(-100, -100, 200, 200);
-        Shape s6 = new Ellipse2D.Double(-100, -100, 200, 200);
-
-        assert(!intersects(s1, s2) );
-        assert( intersects(s1, s3) );
-        assert( intersects(s1, s4) );
-        assert( intersects(s1, s5) );
-
-        assert(!intersects(s2, s1) );
-        assert(!intersects(s2, s3) );
-        assert( intersects(s2, s4) );
-        assert( intersects(s2, s5) );
-
-        assert( intersects(s3, s1) );
-        assert(!intersects(s3, s2) );
-        assert(!intersects(s3, s4) );
-        assert( intersects(s3, s5) );
-
-        assert( intersects(s4, s1) );
-        assert( intersects(s4, s2) );
-        assert(!intersects(s4, s3) );
-        assert( intersects(s4, s5) );
-
-        assert( intersects(s5, s1) );
-        assert( intersects(s5, s2) );
-        assert( intersects(s5, s3) );
-        assert( intersects(s5, s4) );
-
-        assert(!contains(s1, s2) );
-        assert(!contains(s1, s3) );
-        assert(!contains(s1, s4) );
-        assert(!contains(s1, s5) );
-
-        assert(!contains(s2, s1) );
-        assert(!contains(s2, s3) );
-        assert(!contains(s2, s4) );
-        assert(!contains(s2, s5) );
-
-        assert(!contains(s3, s1) );
-        assert(!contains(s3, s2) );
-        assert(!contains(s3, s4) );
-        assert(!contains(s3, s5) );
-
-        assert(!contains(s4, s1) );
-        assert(!contains(s4, s2) );
-        assert(!contains(s4, s3) );
-        assert(!contains(s4, s5) );
-
-        assert( contains(s5, s1) );
-        assert( contains(s5, s2) );
-        assert( contains(s5, s3) );
-        assert( contains(s5, s4) );
-
-        assert( contains(s6, s1) );
-        assert( contains(s6, s2) );
-        assert( contains(s6, s3) );
-        assert( contains(s6, s4) );
-
-    }
-
-}
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 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.g2d.utils;
+
+import java.awt.BasicStroke;
+import java.awt.Color;
+import java.awt.Polygon;
+import java.awt.Shape;
+import java.awt.Stroke;
+import java.awt.geom.AffineTransform;
+import java.awt.geom.Area;
+import java.awt.geom.Ellipse2D;
+import java.awt.geom.Path2D;
+import java.awt.geom.PathIterator;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.List;
+
+import org.simantics.scenegraph.utils.TransformedRectangle;
+
+/**
+ * Geometry related Utilities
+ *
+ * @see PathUtils2 Path related utilities
+ * 
+ * @author Toni Kalajainen
+ * @author Tuukka Lehtonen
+ */
+public final class GeometryUtils {
+
+    //public static final double EPSILON = 1e-7;
+
+    public static final BasicStroke BASIC_STROKE = new BasicStroke();
+
+    public static BasicStroke scaleStroke(Stroke stroke, float factor)
+    {
+        BasicStroke s = (BasicStroke) stroke;
+        float[] dash = s.getDashArray();
+        if (dash!=null) {
+            assert(factor!=0);
+            dash = scaleArray(factor, dash, new float[dash.length]);
+        }
+        if (dash==null)
+            return new BasicStroke(
+                    s.getLineWidth() * factor,
+                    s.getEndCap(),
+                    s.getLineJoin(),
+                    s.getMiterLimit()
+            );
+        return new BasicStroke(
+                s.getLineWidth() * factor,
+                s.getEndCap(),
+                s.getLineJoin(),
+                s.getMiterLimit(),
+                dash,
+                s.getDashPhase() * factor
+        );
+    }
+
+
+
+    /**
+     * Scales every element in array
+     * @param array
+     * @param factor
+     * @return new scaled array
+     */
+    public static float[] scaleArray(float factor, float [] array, float [] targetArray)
+    {
+        assert(array!=null);
+        if (targetArray==null)
+            targetArray = new float[array.length];
+        for (int i=0; i<array.length; i++)
+        {
+            targetArray[i] = array[i] * factor;
+        }
+        return targetArray;
+    }
+
+    /**
+     * Get x/y scale of a transform
+     * @param at
+     * @param pt
+     * @return
+     */
+    public static Point2D getScaleXY(AffineTransform at, Point2D pt)
+    {
+        double m00 = at.getScaleX();
+        double m11 = at.getScaleY();
+        double m10 = at.getShearY();
+        double m01 = at.getShearX();
+        // Project unit vector to canvas
+        double sx = Math.sqrt( m00*m00+m10*m10 );
+        double sy = Math.sqrt( m01*m01+m11*m11 );
+        if (pt==null) pt = new Point2D.Double();
+        pt.setLocation(sx, sy);
+        return pt;
+    }
+
+    /**
+     * Get scale of a transform
+     * @param at
+     * @param pt
+     * @return
+     */
+    /*
+	public static double getScale(AffineTransform at)
+	{
+		double m00 = at.getScaleX();
+		double m11 = at.getScaleY();
+		double m10 = at.getShearY();
+		double m01 = at.getShearX();
+		// Project unit vector to canvas
+		double sx = Math.sqrt( m00*m00+m10*m10 );
+		double sy = Math.sqrt( m01*m01+m11*m11 );
+		return Math.sqrt(sx*sx+sy*sy);
+	}   */
+
+    /*
+	public static double getScale(AffineTransform at)
+	{
+		double m00 = at.getScaleX();
+		double m11 = at.getScaleY();
+		double m10 = at.getShearY();
+		double m01 = at.getShearX();
+
+		double a = m00 + m11;
+		double b = 4.0 * m10*m01 + (m00 - m11) * (m00 - m11);
+		if(b <= 0.0)
+			return 0.5 * Math.sqrt(a*a + b);
+		else
+			return 0.5 * (Math.abs(a) + Math.sqrt(b));
+	}*/
+
+    public static double getScale(AffineTransform at)
+    {
+        double m00 = at.getScaleX();
+        double m11 = at.getScaleY();
+        double m10 = at.getShearY();
+        double m01 = at.getShearX();
+
+        return Math.sqrt(Math.abs(m00*m11 - m10*m01));
+    }
+
+    /**
+     * Computes the greatest absolute value of the eigenvalues
+     * of the matrix.
+     */
+    public static double getMaxScale(AffineTransform at)
+    {
+        double m00 = at.getScaleX();
+        double m11 = at.getScaleY();
+        double m10 = at.getShearY();
+        double m01 = at.getShearX();
+
+        /*
+         * If a and b are the eigenvalues of the matrix,
+         * then
+         *   trace       = a + b
+         *   determinant = a*b
+         */
+        double trace = m00 + m11;
+        double determinant = m00*m11 - m10*m01;
+
+        double dd = trace*trace*0.25 - determinant;
+        if(dd >= 0.0) {
+            /*
+             * trace/2 +- sqrt(trace^2 / 4 - determinant)
+             * = (a+b)/2 +- sqrt((a+b)^2 / 4 - a b)
+             * = (a+b)/2 +- sqrt(a^2 / 4 + a b / 2 + b^2 / 4 - a b)
+             * = (a+b)/2 +- sqrt(a^2 / 4 - a b / 2 + b^2 / 4)
+             * = (a+b)/2 +- (a-b)/2
+             * = a or b
+             * 
+             * Thus the formula below calculates the greatest
+             * absolute value of the eigenvalues max(abs(a), abs(b))
+             */
+            return Math.abs(trace*0.5) + Math.sqrt(dd);
+        }
+        else {
+            /*
+             * If dd < 0, then the eigenvalues a and b are not real.
+             * Because both trace and determinant are real, a and b
+             * have form:
+             *   a = x + i y
+             *   b = x - i y
+             * 
+             * Then
+             *    sqrt(determinant)
+             *    = sqrt(a b)
+             *    = sqrt(x^2 + y^2),
+             * which is the absolute value of the eigenvalues.
+             */
+            return Math.sqrt(determinant);
+        }
+    }
+
+    /**
+     * Intersect test of two shapes
+     * @param s1
+     * @param s2
+     * @return
+     */
+    public static boolean intersects(Shape s1, Shape s2)
+    {
+        if (s1==s2) return true;
+        if (s1.equals(s2)) return true;
+        if (s1 instanceof Rectangle2D)
+            return s2.intersects((Rectangle2D) s1);
+        if (s2 instanceof Rectangle2D)
+            return s1.intersects((Rectangle2D) s2);
+        if (s1 instanceof TransformedRectangle)
+            return ((TransformedRectangle)s1).intersects(s2);
+        if (s2 instanceof TransformedRectangle)
+            return ((TransformedRectangle)s2).intersects(s1);
+
+        // VERY SLOW IMPLEMENTATION
+        // Convert shapes to areas and intersect them
+        Area a1 = new Area(s1);
+        Area a2 = new Area(s2);
+        a1.intersect(a2);
+        return !a1.isEmpty();
+    }
+
+    /**
+     * Contains test of two shapes
+     * @param s1
+     * @param s2
+     * @return <code>true</code> if s1 contains s2, else <code>false</code>
+     */
+    public static boolean contains(Shape s1, Shape s2)
+    {
+        if (s1==s2) return true;
+        if (s1.equals(s2)) return true;
+        if (s2 instanceof Rectangle2D)
+            return s1.contains((Rectangle2D) s2);
+        if (s1 instanceof Rectangle2D)
+            return contains((Rectangle2D)s1, s2);
+        if (s1 instanceof TransformedRectangle)
+            return ((TransformedRectangle)s1).contains(s2);
+
+        // VERY SLOW IMPLEMENTATION
+        // Convert shapes to areas and intersect them
+        Area a1 = new Area(s1);
+        Area a2 = new Area(s2);
+        a2.subtract(a1);
+        return a2.isEmpty();
+    }
+
+    /**
+     * Tests if rectangle contains a shape
+     * @param r rectangle
+     * @param s shape to be tested
+     * @return <code>true</code> if r contains s, else <code>false</code>
+     */
+    public static boolean contains(Rectangle2D r, Shape s)
+    {
+        // Rectangle contains a shape if
+        //  all points of the shape are contained in r
+        PathIterator pi = s.getPathIterator(null, Double.MAX_VALUE);
+        double coords[] = new double[6];
+        while (!pi.isDone()) {
+            int type = pi.currentSegment(coords);
+            if (type == PathIterator.SEG_MOVETO || type == PathIterator.SEG_LINETO)
+            {
+                if (!r.contains(coords[0], coords[1]))
+                    return false;
+            }
+            assert(type != PathIterator.SEG_CUBICTO && type != PathIterator.SEG_QUADTO);
+            pi.next();
+        }
+        return true;
+    }
+
+    /**
+     * Creates new transformed shape
+     * @param s shape to be transformed
+     * @param t transform
+     * @return new transformed shape
+     */
+    public static Shape transformShape(Shape s, AffineTransform t)
+    {
+        if (t.isIdentity()) return s;
+        if (s instanceof Rectangle2D) {
+            Rectangle2D rect = (Rectangle2D) s;
+            int type = t.getType();
+            if (type == AffineTransform.TYPE_IDENTITY) {
+                Rectangle2D r = new Rectangle2D.Double();
+                r.setFrame(rect);
+                return r;
+            }
+            if ((type & (AffineTransform.TYPE_GENERAL_ROTATION|AffineTransform.TYPE_GENERAL_TRANSFORM) ) != 0)
+                return new TransformedRectangle(rect, t);
+            return org.simantics.scenegraph.utils.GeometryUtils.transformRectangle(t, rect);
+        }
+        if (s instanceof TransformedRectangle)
+        {
+            TransformedRectangle tr = (TransformedRectangle) s;
+            TransformedRectangle result = new TransformedRectangle(tr);
+            result.concatenate(t);
+            return result;
+        }
+
+        //return t.createTransformedShape(s);
+        //return new Area(s).createTransformedArea(t);
+        Area result = new Area(s);
+        result.transform(t);
+        return result;
+    }
+
+    /**
+     * Get compass direction. 0 = north, clockwise
+     * @param pt
+     * @return
+     */
+    public static double getCompassDirection(Point2D pt) {
+        return getCompassDirection(pt.getX(), pt.getY());
+    }
+
+    /**
+     * Get compass direction for the vector p1&rarr;p2. 0 = north, clockwise
+     * 
+     * @param p1 the start of the vector
+     * @param p2 the end of the vector
+     * @return compass direction
+     */
+    public static double getCompassDirection(Point2D p1, Point2D p2) {
+        double dx = p2.getX() - p1.getX();
+        double dy = p2.getY() - p1.getY();
+        return getCompassDirection(dx, dy);
+    }
+
+    /**
+     * Get compass direction. 0 = north, clockwise
+     * @param pt
+     * @return
+     */
+    public static double getCompassDirection(double x, double y) {
+        double rad = Math.atan2(y, x);
+        double deg = rad*180.0 / Math.PI + 90.0;
+        if (deg<0) deg = 360+deg;
+        return deg;
+    }
+
+    /**
+     * Converts compass direction to unit vector
+     * @param deg compass direction
+     * @param uv
+     * @return
+     */
+    public static Point2D toUnitVector(double deg, Point2D uv)
+    {
+        if (uv==null) uv = new Point2D.Double();
+        double x=0, y=0;
+        if (deg==0) {
+            y=-1;
+        } else if (deg==90) {
+            x=1;
+        } else if (deg==180) {
+            y=1;
+        } else if (deg==270) {
+            x=-1;
+        } else {
+            double rad = (deg-90)*Math.PI/180.0;
+            y = Math.sin(rad);
+            x = Math.cos(rad);
+        }
+        uv.setLocation(x, y);
+        return uv;
+    }
+
+    /**
+     * Convert compass direction to radian presentation (0=right, CCW)
+     * @param deg
+     * @return radians
+     */
+    public static double compassToRad(double deg) {
+        double rad = (deg-90)*Math.PI/180.0;
+        return rad;
+
+    }
+
+    /**
+     * Interpolate between two colors
+     * @param c1
+     * @param c2
+     * @param phase 0..1 (0=c1, 1=c2)
+     * @return
+     */
+    public static Color interpolate(Color c1, Color c2, double phase)
+    {
+        float r = (c1.getRed()/255.0f)*(1-(float)phase) + (c2.getRed()/255.0f)*((float)phase);
+        float g = (c1.getGreen()/255.0f)*(1-(float)phase) + (c2.getGreen()/255.0f)*((float)phase);
+        float b = (c1.getBlue()/255.0f)*(1-(float)phase) + (c2.getBlue()/255.0f)*((float)phase);
+        float a = (c1.getAlpha()/255.0f)*(1-(float)phase) + (c2.getAlpha()/255.0f)*((float)phase);
+        return new Color(r, g, b, a);
+    }
+
+    public static Path2D buildPath(List<Point2D> positions)
+    {
+        Path2D result = new Path2D.Double();
+        if (positions.size()==0) return result;
+        Point2D pos = positions.get(0);
+        result.moveTo(pos.getX(), pos.getY());
+        for (int i=1; i<positions.size(); i++)
+        {
+            pos = positions.get(i);
+            result.lineTo(pos.getX(), pos.getY());
+        }
+        return result;
+    }
+
+    /**
+     * Get path positions
+     * 
+     * @param path path
+     * @param positions positions
+     */
+    public static void getPoints(Path2D path, List<Point2D> positions)
+    {
+        PathIterator pi = path.getPathIterator(null);
+        double mat[] = new double[6];
+        while (!pi.isDone()) {
+            pi.currentSegment(mat);
+            positions.add(new Point2D.Double(mat[0], mat[1]));
+            pi.next();
+        }
+    }
+
+    // Tests intersects and contains
+    public static void main(String[] args) {
+/*
+		System.out.println(toUnitVector(getCompassDirection(0, -1), null));
+		System.out.println(toUnitVector(getCompassDirection(1, -1), null));
+		System.out.println(toUnitVector(getCompassDirection(1,  0), null));
+		System.out.println(toUnitVector(getCompassDirection(1,  1), null));
+		System.out.println(toUnitVector(getCompassDirection(0,  1), null));
+		System.out.println(toUnitVector(getCompassDirection(-1, 1), null));
+		System.out.println(toUnitVector(getCompassDirection(-1, 0), null));
+		System.out.println(toUnitVector(getCompassDirection(-1,-1), null));
+
+		System.out.println(getCompassDirection(0, -1));
+		System.out.println(getCompassDirection(1, -1));
+		System.out.println(getCompassDirection(1,  0));
+		System.out.println(getCompassDirection(1,  1));
+		System.out.println(getCompassDirection(0,  1));
+		System.out.println(getCompassDirection(-1, 1));
+		System.out.println(getCompassDirection(-1, 0));
+		System.out.println(getCompassDirection(-1,-1));
+
+        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, -1)));
+        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(1, 0)));
+        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, 1)));
+        System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(-1, 0)));
+ */
+        Shape s1 = new Polygon(new int[]{10,10,0}, new int[]{0,10,10}, 3);
+        Shape s2 = new Ellipse2D.Double(0,0,5,5);
+        Shape s3 = new Ellipse2D.Double(8,8,4,4);
+        Shape s4 = new Rectangle2D.Double(-5, 3, 20, 2);
+        Shape s5 = new Rectangle2D.Double(-100, -100, 200, 200);
+        Shape s6 = new Ellipse2D.Double(-100, -100, 200, 200);
+
+        assert(!intersects(s1, s2) );
+        assert( intersects(s1, s3) );
+        assert( intersects(s1, s4) );
+        assert( intersects(s1, s5) );
+
+        assert(!intersects(s2, s1) );
+        assert(!intersects(s2, s3) );
+        assert( intersects(s2, s4) );
+        assert( intersects(s2, s5) );
+
+        assert( intersects(s3, s1) );
+        assert(!intersects(s3, s2) );
+        assert(!intersects(s3, s4) );
+        assert( intersects(s3, s5) );
+
+        assert( intersects(s4, s1) );
+        assert( intersects(s4, s2) );
+        assert(!intersects(s4, s3) );
+        assert( intersects(s4, s5) );
+
+        assert( intersects(s5, s1) );
+        assert( intersects(s5, s2) );
+        assert( intersects(s5, s3) );
+        assert( intersects(s5, s4) );
+
+        assert(!contains(s1, s2) );
+        assert(!contains(s1, s3) );
+        assert(!contains(s1, s4) );
+        assert(!contains(s1, s5) );
+
+        assert(!contains(s2, s1) );
+        assert(!contains(s2, s3) );
+        assert(!contains(s2, s4) );
+        assert(!contains(s2, s5) );
+
+        assert(!contains(s3, s1) );
+        assert(!contains(s3, s2) );
+        assert(!contains(s3, s4) );
+        assert(!contains(s3, s5) );
+
+        assert(!contains(s4, s1) );
+        assert(!contains(s4, s2) );
+        assert(!contains(s4, s3) );
+        assert(!contains(s4, s5) );
+
+        assert( contains(s5, s1) );
+        assert( contains(s5, s2) );
+        assert( contains(s5, s3) );
+        assert( contains(s5, s4) );
+
+        assert( contains(s6, s1) );
+        assert( contains(s6, s2) );
+        assert( contains(s6, s3) );
+        assert( contains(s6, s4) );
+
+    }
+
+}