bundles/org.simantics.g2d/src/org/simantics/g2d/utils/GeometryUtils.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.g2d.utils;\r
  13 \r
  14 import java.awt.BasicStroke;\r
  15 import java.awt.Color;\r
  16 import java.awt.Polygon;\r
  17 import java.awt.Shape;\r
  18 import java.awt.Stroke;\r
  19 import java.awt.geom.AffineTransform;\r
  20 import java.awt.geom.Area;\r
  21 import java.awt.geom.Ellipse2D;\r
  22 import java.awt.geom.Path2D;\r
  23 import java.awt.geom.PathIterator;\r
  24 import java.awt.geom.Point2D;\r
  25 import java.awt.geom.Rectangle2D;\r
  26 import java.util.List;\r
  27 \r
  28 import org.simantics.scenegraph.utils.TransformedRectangle;\r
  29 \r
  30 /**\r
  31  * Geometry related Utilities\r
  32  *\r
  33  * @see PathUtils2 Path related utilities\r
  34  * \r
  35  * @author Toni Kalajainen\r
  36  * @author Tuukka Lehtonen\r
  37  */\r
  38 public final class GeometryUtils {\r
  39 \r
  40     //public static final double EPSILON = 1e-7;\r
  41 \r
  42     public static final BasicStroke BASIC_STROKE = new BasicStroke();\r
  43 \r
  44     public static BasicStroke scaleStroke(Stroke stroke, float factor)\r
  45     {\r
  46         BasicStroke s = (BasicStroke) stroke;\r
  47         float[] dash = s.getDashArray();\r
  48         if (dash!=null) {\r
  49             assert(factor!=0);\r
  50             dash = scaleArray(factor, dash, new float[dash.length]);\r
  51         }\r
  52         if (dash==null)\r
  53             return new BasicStroke(\r
  54                     s.getLineWidth() * factor,\r
  55                     s.getEndCap(),\r
  56                     s.getLineJoin(),\r
  57                     s.getMiterLimit()\r
  58             );\r
  59         return new BasicStroke(\r
  60                 s.getLineWidth() * factor,\r
  61                 s.getEndCap(),\r
  62                 s.getLineJoin(),\r
  63                 s.getMiterLimit(),\r
  64                 dash,\r
  65                 s.getDashPhase() * factor\r
  66         );\r
  67     }\r
  68 \r
  69 \r
  70 \r
  71     /**\r
  72      * Scales every element in array\r
  73      * @param array\r
  74      * @param factor\r
  75      * @return new scaled array\r
  76      */\r
  77     public static float[] scaleArray(float factor, float [] array, float [] targetArray)\r
  78     {\r
  79         assert(array!=null);\r
  80         if (targetArray==null)\r
  81             targetArray = new float[array.length];\r
  82         for (int i=0; i<array.length; i++)\r
  83         {\r
  84             targetArray[i] = array[i] * factor;\r
  85         }\r
  86         return targetArray;\r
  87     }\r
  88 \r
  89     /**\r
  90      * Get x/y scale of a transform\r
  91      * @param at\r
  92      * @param pt\r
  93      * @return\r
  94      */\r
  95     public static Point2D getScaleXY(AffineTransform at, Point2D pt)\r
  96     {\r
  97         double m00 = at.getScaleX();\r
  98         double m11 = at.getScaleY();\r
  99         double m10 = at.getShearY();\r
 100         double m01 = at.getShearX();\r
 101         // Project unit vector to canvas\r
 102         double sx = Math.sqrt( m00*m00+m10*m10 );\r
 103         double sy = Math.sqrt( m01*m01+m11*m11 );\r
 104         if (pt==null) pt = new Point2D.Double();\r
 105         pt.setLocation(sx, sy);\r
 106         return pt;\r
 107     }\r
 108 \r
 109     /**\r
 110      * Get scale of a transform\r
 111      * @param at\r
 112      * @param pt\r
 113      * @return\r
 114      */\r
 115     /*\r
 116         public static double getScale(AffineTransform at)\r
 117         {\r
 118                 double m00 = at.getScaleX();\r
 119                 double m11 = at.getScaleY();\r
 120                 double m10 = at.getShearY();\r
 121                 double m01 = at.getShearX();\r
 122                 // Project unit vector to canvas\r
 123                 double sx = Math.sqrt( m00*m00+m10*m10 );\r
 124                 double sy = Math.sqrt( m01*m01+m11*m11 );\r
 125                 return Math.sqrt(sx*sx+sy*sy);\r
 126         }   */\r
 127 \r
 128     /*\r
 129         public static double getScale(AffineTransform at)\r
 130         {\r
 131                 double m00 = at.getScaleX();\r
 132                 double m11 = at.getScaleY();\r
 133                 double m10 = at.getShearY();\r
 134                 double m01 = at.getShearX();\r
 135 \r
 136                 double a = m00 + m11;\r
 137                 double b = 4.0 * m10*m01 + (m00 - m11) * (m00 - m11);\r
 138                 if(b <= 0.0)\r
 139                         return 0.5 * Math.sqrt(a*a + b);\r
 140                 else\r
 141                         return 0.5 * (Math.abs(a) + Math.sqrt(b));\r
 142         }*/\r
 143 \r
 144     public static double getScale(AffineTransform at)\r
 145     {\r
 146         double m00 = at.getScaleX();\r
 147         double m11 = at.getScaleY();\r
 148         double m10 = at.getShearY();\r
 149         double m01 = at.getShearX();\r
 150 \r
 151         return Math.sqrt(Math.abs(m00*m11 - m10*m01));\r
 152     }\r
 153 \r
 154     /**\r
 155      * Computes the greatest absolute value of the eigenvalues\r
 156      * of the matrix.\r
 157      */\r
 158     public static double getMaxScale(AffineTransform at)\r
 159     {\r
 160         double m00 = at.getScaleX();\r
 161         double m11 = at.getScaleY();\r
 162         double m10 = at.getShearY();\r
 163         double m01 = at.getShearX();\r
 164 \r
 165         /*\r
 166          * If a and b are the eigenvalues of the matrix,\r
 167          * then\r
 168          *   trace       = a + b\r
 169          *   determinant = a*b\r
 170          */\r
 171         double trace = m00 + m11;\r
 172         double determinant = m00*m11 - m10*m01;\r
 173 \r
 174         double dd = trace*trace*0.25 - determinant;\r
 175         if(dd >= 0.0) {\r
 176             /*\r
 177              * trace/2 +- sqrt(trace^2 / 4 - determinant)\r
 178              * = (a+b)/2 +- sqrt((a+b)^2 / 4 - a b)\r
 179              * = (a+b)/2 +- sqrt(a^2 / 4 + a b / 2 + b^2 / 4 - a b)\r
 180              * = (a+b)/2 +- sqrt(a^2 / 4 - a b / 2 + b^2 / 4)\r
 181              * = (a+b)/2 +- (a-b)/2\r
 182              * = a or b\r
 183              * \r
 184              * Thus the formula below calculates the greatest\r
 185              * absolute value of the eigenvalues max(abs(a), abs(b))\r
 186              */\r
 187             return Math.abs(trace*0.5) + Math.sqrt(dd);\r
 188         }\r
 189         else {\r
 190             /*\r
 191              * If dd < 0, then the eigenvalues a and b are not real.\r
 192              * Because both trace and determinant are real, a and b\r
 193              * have form:\r
 194              *   a = x + i y\r
 195              *   b = x - i y\r
 196              * \r
 197              * Then\r
 198              *    sqrt(determinant)\r
 199              *    = sqrt(a b)\r
 200              *    = sqrt(x^2 + y^2),\r
 201              * which is the absolute value of the eigenvalues.\r
 202              */\r
 203             return Math.sqrt(determinant);\r
 204         }\r
 205     }\r
 206 \r
 207     /**\r
 208      * Intersect test of two shapes\r
 209      * @param s1\r
 210      * @param s2\r
 211      * @return\r
 212      */\r
 213     public static boolean intersects(Shape s1, Shape s2)\r
 214     {\r
 215         if (s1==s2) return true;\r
 216         if (s1.equals(s2)) return true;\r
 217         if (s1 instanceof Rectangle2D)\r
 218             return s2.intersects((Rectangle2D) s1);\r
 219         if (s2 instanceof Rectangle2D)\r
 220             return s1.intersects((Rectangle2D) s2);\r
 221         if (s1 instanceof TransformedRectangle)\r
 222             return ((TransformedRectangle)s1).intersects(s2);\r
 223         if (s2 instanceof TransformedRectangle)\r
 224             return ((TransformedRectangle)s2).intersects(s1);\r
 225 \r
 226         // VERY SLOW IMPLEMENTATION\r
 227         // Convert shapes to areas and intersect them\r
 228         Area a1 = new Area(s1);\r
 229         Area a2 = new Area(s2);\r
 230         a1.intersect(a2);\r
 231         return !a1.isEmpty();\r
 232     }\r
 233 \r
 234     /**\r
 235      * Contains test of two shapes\r
 236      * @param s1\r
 237      * @param s2\r
 238      * @return <code>true</code> if s1 contains s2, else <code>false</code>\r
 239      */\r
 240     public static boolean contains(Shape s1, Shape s2)\r
 241     {\r
 242         if (s1==s2) return true;\r
 243         if (s1.equals(s2)) return true;\r
 244         if (s2 instanceof Rectangle2D)\r
 245             return s1.contains((Rectangle2D) s2);\r
 246         if (s1 instanceof Rectangle2D)\r
 247             return contains((Rectangle2D)s1, s2);\r
 248         if (s1 instanceof TransformedRectangle)\r
 249             return ((TransformedRectangle)s1).contains(s2);\r
 250 \r
 251         // VERY SLOW IMPLEMENTATION\r
 252         // Convert shapes to areas and intersect them\r
 253         Area a1 = new Area(s1);\r
 254         Area a2 = new Area(s2);\r
 255         a2.subtract(a1);\r
 256         return a2.isEmpty();\r
 257     }\r
 258 \r
 259     /**\r
 260      * Tests if rectangle contains a shape\r
 261      * @param r rectangle\r
 262      * @param s shape to be tested\r
 263      * @return <code>true</code> if r contains s, else <code>false</code>\r
 264      */\r
 265     public static boolean contains(Rectangle2D r, Shape s)\r
 266     {\r
 267         // Rectangle contains a shape if\r
 268         //  all points of the shape are contained in r\r
 269         PathIterator pi = s.getPathIterator(null, Double.MAX_VALUE);\r
 270         double coords[] = new double[6];\r
 271         while (!pi.isDone()) {\r
 272             int type = pi.currentSegment(coords);\r
 273             if (type == PathIterator.SEG_MOVETO || type == PathIterator.SEG_LINETO)\r
 274             {\r
 275                 if (!r.contains(coords[0], coords[1]))\r
 276                     return false;\r
 277             }\r
 278             assert(type != PathIterator.SEG_CUBICTO && type != PathIterator.SEG_QUADTO);\r
 279             pi.next();\r
 280         }\r
 281         return true;\r
 282     }\r
 283 \r
 284     /**\r
 285      * Creates new transformed shape\r
 286      * @param s shape to be transformed\r
 287      * @param t transform\r
 288      * @return new transformed shape\r
 289      */\r
 290     public static Shape transformShape(Shape s, AffineTransform t)\r
 291     {\r
 292         if (t.isIdentity()) return s;\r
 293         if (s instanceof Rectangle2D) {\r
 294             Rectangle2D rect = (Rectangle2D) s;\r
 295             int type = t.getType();\r
 296             if (type == AffineTransform.TYPE_IDENTITY) {\r
 297                 Rectangle2D r = new Rectangle2D.Double();\r
 298                 r.setFrame(rect);\r
 299                 return r;\r
 300             }\r
 301             if ((type & (AffineTransform.TYPE_GENERAL_ROTATION|AffineTransform.TYPE_GENERAL_TRANSFORM) ) != 0)\r
 302                 return new TransformedRectangle(rect, t);\r
 303             return org.simantics.scenegraph.utils.GeometryUtils.transformRectangle(t, rect);\r
 304         }\r
 305         if (s instanceof TransformedRectangle)\r
 306         {\r
 307             TransformedRectangle tr = (TransformedRectangle) s;\r
 308             TransformedRectangle result = new TransformedRectangle(tr);\r
 309             result.concatenate(t);\r
 310             return result;\r
 311         }\r
 312 \r
 313         //return t.createTransformedShape(s);\r
 314         //return new Area(s).createTransformedArea(t);\r
 315         Area result = new Area(s);\r
 316         result.transform(t);\r
 317         return result;\r
 318     }\r
 319 \r
 320     /**\r
 321      * Get compass direction. 0 = north, clockwise\r
 322      * @param pt\r
 323      * @return\r
 324      */\r
 325     public static double getCompassDirection(Point2D pt) {\r
 326         return getCompassDirection(pt.getX(), pt.getY());\r
 327     }\r
 328 \r
 329     /**\r
 330      * Get compass direction for the vector p1&rarr;p2. 0 = north, clockwise\r
 331      * \r
 332      * @param p1 the start of the vector\r
 333      * @param p2 the end of the vector\r
 334      * @return compass direction\r
 335      */\r
 336     public static double getCompassDirection(Point2D p1, Point2D p2) {\r
 337         double dx = p2.getX() - p1.getX();\r
 338         double dy = p2.getY() - p1.getY();\r
 339         return getCompassDirection(dx, dy);\r
 340     }\r
 341 \r
 342     /**\r
 343      * Get compass direction. 0 = north, clockwise\r
 344      * @param pt\r
 345      * @return\r
 346      */\r
 347     public static double getCompassDirection(double x, double y) {\r
 348         double rad = Math.atan2(y, x);\r
 349         double deg = rad*180.0 / Math.PI + 90.0;\r
 350         if (deg<0) deg = 360+deg;\r
 351         return deg;\r
 352     }\r
 353 \r
 354     /**\r
 355      * Converts compass direction to unit vector\r
 356      * @param deg compass direction\r
 357      * @param uv\r
 358      * @return\r
 359      */\r
 360     public static Point2D toUnitVector(double deg, Point2D uv)\r
 361     {\r
 362         if (uv==null) uv = new Point2D.Double();\r
 363         double x=0, y=0;\r
 364         if (deg==0) {\r
 365             y=-1;\r
 366         } else if (deg==90) {\r
 367             x=1;\r
 368         } else if (deg==180) {\r
 369             y=1;\r
 370         } else if (deg==270) {\r
 371             x=-1;\r
 372         } else {\r
 373             double rad = (deg-90)*Math.PI/180.0;\r
 374             y = Math.sin(rad);\r
 375             x = Math.cos(rad);\r
 376         }\r
 377         uv.setLocation(x, y);\r
 378         return uv;\r
 379     }\r
 380 \r
 381     /**\r
 382      * Convert compass direction to radian presentation (0=right, CCW)\r
 383      * @param deg\r
 384      * @return radians\r
 385      */\r
 386     public static double compassToRad(double deg) {\r
 387         double rad = (deg-90)*Math.PI/180.0;\r
 388         return rad;\r
 389 \r
 390     }\r
 391 \r
 392     /**\r
 393      * Interpolate between two colors\r
 394      * @param c1\r
 395      * @param c2\r
 396      * @param phase 0..1 (0=c1, 1=c2)\r
 397      * @return\r
 398      */\r
 399     public static Color interpolate(Color c1, Color c2, double phase)\r
 400     {\r
 401         float r = (c1.getRed()/255.0f)*(1-(float)phase) + (c2.getRed()/255.0f)*((float)phase);\r
 402         float g = (c1.getGreen()/255.0f)*(1-(float)phase) + (c2.getGreen()/255.0f)*((float)phase);\r
 403         float b = (c1.getBlue()/255.0f)*(1-(float)phase) + (c2.getBlue()/255.0f)*((float)phase);\r
 404         float a = (c1.getAlpha()/255.0f)*(1-(float)phase) + (c2.getAlpha()/255.0f)*((float)phase);\r
 405         return new Color(r, g, b, a);\r
 406     }\r
 407 \r
 408     public static Path2D buildPath(List<Point2D> positions)\r
 409     {\r
 410         Path2D result = new Path2D.Double();\r
 411         if (positions.size()==0) return result;\r
 412         Point2D pos = positions.get(0);\r
 413         result.moveTo(pos.getX(), pos.getY());\r
 414         for (int i=1; i<positions.size(); i++)\r
 415         {\r
 416             pos = positions.get(i);\r
 417             result.lineTo(pos.getX(), pos.getY());\r
 418         }\r
 419         return result;\r
 420     }\r
 421 \r
 422     /**\r
 423      * Get path positions\r
 424      * \r
 425      * @param path path\r
 426      * @param positions positions\r
 427      */\r
 428     public static void getPoints(Path2D path, List<Point2D> positions)\r
 429     {\r
 430         PathIterator pi = path.getPathIterator(null);\r
 431         double mat[] = new double[6];\r
 432         while (!pi.isDone()) {\r
 433             pi.currentSegment(mat);\r
 434             positions.add(new Point2D.Double(mat[0], mat[1]));\r
 435             pi.next();\r
 436         }\r
 437     }\r
 438 \r
 439     // Tests intersects and contains\r
 440     public static void main(String[] args) {\r
 441 /*\r
 442                 System.out.println(toUnitVector(getCompassDirection(0, -1), null));\r
 443                 System.out.println(toUnitVector(getCompassDirection(1, -1), null));\r
 444                 System.out.println(toUnitVector(getCompassDirection(1,  0), null));\r
 445                 System.out.println(toUnitVector(getCompassDirection(1,  1), null));\r
 446                 System.out.println(toUnitVector(getCompassDirection(0,  1), null));\r
 447                 System.out.println(toUnitVector(getCompassDirection(-1, 1), null));\r
 448                 System.out.println(toUnitVector(getCompassDirection(-1, 0), null));\r
 449                 System.out.println(toUnitVector(getCompassDirection(-1,-1), null));\r
 450 \r
 451                 System.out.println(getCompassDirection(0, -1));\r
 452                 System.out.println(getCompassDirection(1, -1));\r
 453                 System.out.println(getCompassDirection(1,  0));\r
 454                 System.out.println(getCompassDirection(1,  1));\r
 455                 System.out.println(getCompassDirection(0,  1));\r
 456                 System.out.println(getCompassDirection(-1, 1));\r
 457                 System.out.println(getCompassDirection(-1, 0));\r
 458                 System.out.println(getCompassDirection(-1,-1));\r
 459 \r
 460         System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, -1)));\r
 461         System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(1, 0)));\r
 462         System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(0, 1)));\r
 463         System.out.println(getCompassDirection(new Point2D.Double(0, 0), new Point2D.Double(-1, 0)));\r
 464  */\r
 465         Shape s1 = new Polygon(new int[]{10,10,0}, new int[]{0,10,10}, 3);\r
 466         Shape s2 = new Ellipse2D.Double(0,0,5,5);\r
 467         Shape s3 = new Ellipse2D.Double(8,8,4,4);\r
 468         Shape s4 = new Rectangle2D.Double(-5, 3, 20, 2);\r
 469         Shape s5 = new Rectangle2D.Double(-100, -100, 200, 200);\r
 470         Shape s6 = new Ellipse2D.Double(-100, -100, 200, 200);\r
 471 \r
 472         assert(!intersects(s1, s2) );\r
 473         assert( intersects(s1, s3) );\r
 474         assert( intersects(s1, s4) );\r
 475         assert( intersects(s1, s5) );\r
 476 \r
 477         assert(!intersects(s2, s1) );\r
 478         assert(!intersects(s2, s3) );\r
 479         assert( intersects(s2, s4) );\r
 480         assert( intersects(s2, s5) );\r
 481 \r
 482         assert( intersects(s3, s1) );\r
 483         assert(!intersects(s3, s2) );\r
 484         assert(!intersects(s3, s4) );\r
 485         assert( intersects(s3, s5) );\r
 486 \r
 487         assert( intersects(s4, s1) );\r
 488         assert( intersects(s4, s2) );\r
 489         assert(!intersects(s4, s3) );\r
 490         assert( intersects(s4, s5) );\r
 491 \r
 492         assert( intersects(s5, s1) );\r
 493         assert( intersects(s5, s2) );\r
 494         assert( intersects(s5, s3) );\r
 495         assert( intersects(s5, s4) );\r
 496 \r
 497         assert(!contains(s1, s2) );\r
 498         assert(!contains(s1, s3) );\r
 499         assert(!contains(s1, s4) );\r
 500         assert(!contains(s1, s5) );\r
 501 \r
 502         assert(!contains(s2, s1) );\r
 503         assert(!contains(s2, s3) );\r
 504         assert(!contains(s2, s4) );\r
 505         assert(!contains(s2, s5) );\r
 506 \r
 507         assert(!contains(s3, s1) );\r
 508         assert(!contains(s3, s2) );\r
 509         assert(!contains(s3, s4) );\r
 510         assert(!contains(s3, s5) );\r
 511 \r
 512         assert(!contains(s4, s1) );\r
 513         assert(!contains(s4, s2) );\r
 514         assert(!contains(s4, s3) );\r
 515         assert(!contains(s4, s5) );\r
 516 \r
 517         assert( contains(s5, s1) );\r
 518         assert( contains(s5, s2) );\r
 519         assert( contains(s5, s3) );\r
 520         assert( contains(s5, s4) );\r
 521 \r
 522         assert( contains(s6, s1) );\r
 523         assert( contains(s6, s2) );\r
 524         assert( contains(s6, s3) );\r
 525         assert( contains(s6, s4) );\r
 526 \r
 527     }\r
 528 \r
 529 }\r