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

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