bundles/org.simantics.g2d/src/org/simantics/g2d/utils/PathUtils.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.geom.Path2D;\r
  15 import java.awt.geom.PathIterator;\r
  16 import java.awt.geom.Point2D;\r
  17 import java.util.ArrayList;\r
  18 import java.util.Arrays;\r
  19 import java.util.Collection;\r
  20 import java.util.Iterator;\r
  21 \r
  22 /**\r
  23  * Path Utils.\r
  24  * <p>\r
  25  * A line segment (linear, quadratic or cubic bezier) is described\r
  26  * with a double array. The length of the array describes its degree (4,6,8).\r
  27  * The first 2 elements define start point and last 2 the end point.\r
  28  * Points in the middle are bezier control points.\r
  29  * \r
  30  * @author Toni Kalajainen\r
  31  */\r
  32 public class PathUtils {\r
  33 \r
  34         /**\r
  35          * Get tangent of an bezier\r
  36          * @param lineSegment bezier of n degrees\r
  37          * @param degree 1..3 \r
  38          * @param t 0..1\r
  39          * @return unit vector\r
  40          */\r
  41         public static Point2D getLineTangent(double lineSegment[], double t)\r
  42         {\r
  43                 int degree = getLineDegree(lineSegment);\r
  44                 double x=0, y=0;\r
  45                 if (degree==1)\r
  46                 {\r
  47                         x = lineSegment[2*1+0] - lineSegment[2*0+0];\r
  48                         y = lineSegment[2*1+1] - lineSegment[2*0+1];\r
  49                 } else {                \r
  50                         if (degree==2) {\r
  51                                 x = 2*t*(lineSegment[2*0+0] - 2*lineSegment[2*1+0] + lineSegment[2*2+0]) + 2*(-lineSegment[2*0+0] + lineSegment[2*1+0]);\r
  52                                 y = 2*t*(lineSegment[2*0+1] - 2*lineSegment[2*1+1] + lineSegment[2*2+1]) + 2*(-lineSegment[2*0+1] + lineSegment[2*1+1]);\r
  53                         } else if (degree==3) {\r
  54                                 x = 3*(1-t)*(1-t)*(lineSegment[2*1+0]-lineSegment[2*0+0]) + 3*(lineSegment[2*2+0]-lineSegment[2*1+0])*2*t*(1-t) + 3*(lineSegment[2*3+0]-lineSegment[2*2+0])*t*t;\r
  55                                 y = 3*(1-t)*(1-t)*(lineSegment[2*1+1]-lineSegment[2*0+1]) + 3*(lineSegment[2*2+1]-lineSegment[2*1+1])*2*t*(1-t) + 3*(lineSegment[2*3+1]-lineSegment[2*2+1])*t*t;\r
  56                         }\r
  57                 }               \r
  58                 return new Point2D.Double(x, y);\r
  59         }\r
  60         \r
  61         /**\r
  62          * \r
  63          * @param lineSegment\r
  64          * @param t 0..1\r
  65          * @return\r
  66          */\r
  67         public static Point2D getLinePos(double lineSegment[], double t)\r
  68         {               \r
  69                 assert(lineSegment!=null);\r
  70                 int degree = getLineDegree(lineSegment);\r
  71                 double x=0, y=0;\r
  72                 \r
  73                 if (degree==1) {\r
  74                         double p0x = lineSegment[0];\r
  75                         double p0y = lineSegment[1];\r
  76                         double p1x = lineSegment[2];\r
  77                         double p1y = lineSegment[3];\r
  78                         \r
  79                         x = p0x*(1-t) + t*p1x;\r
  80                         y = p0y*(1-t) + t*p1y;\r
  81                 } else if (degree==2) {\r
  82                         double p0x = lineSegment[0];\r
  83                         double p0y = lineSegment[1];\r
  84                         double p1x = lineSegment[2];\r
  85                         double p1y = lineSegment[3];\r
  86                         double p2x = lineSegment[4];\r
  87                         double p2y = lineSegment[5];                    \r
  88                         \r
  89                         double c2x = p0x-2*p1x+p2x;\r
  90                         double c2y = p0y-2*p1y+p2y;\r
  91                         \r
  92                         double c1x = -2*p0x+2*p1x;\r
  93                         double c1y = -2*p0y+2*p1y;\r
  94                         \r
  95                         double c0x = p0x;\r
  96                         double c0y = p0y;\r
  97                         \r
  98                         x = t*t*c2x+t*c1x+c0x;\r
  99                         y = t*t*c2y+t*c1y+c0y;\r
 100                 } else if (degree==3) {\r
 101                         double p0x = lineSegment[0];\r
 102                         double p0y = lineSegment[1];\r
 103                         double p1x = lineSegment[2];\r
 104                         double p1y = lineSegment[3];\r
 105                         double p2x = lineSegment[4];\r
 106                         double p2y = lineSegment[5];                    \r
 107                         double p3x = lineSegment[6];\r
 108                         double p3y = lineSegment[7];                    \r
 109 \r
 110                         x = (1-t)*(1-t)*(1-t)*p0x + 3*t*(1-t)*(1-t)*p1x + 3*t*t*(1-t)*p2x + t*t*t*p3x;\r
 111                         y = (1-t)*(1-t)*(1-t)*p0y + 3*t*(1-t)*(1-t)*p1y + 3*t*t*(1-t)*p2y + t*t*t*p3y;\r
 112                 }\r
 113                 \r
 114                 return new Point2D.Double(x, y);\r
 115         }\r
 116         \r
 117         public static double getLineLength(double lineSegment[])\r
 118         {\r
 119                 int degree = getLineDegree(lineSegment);                \r
 120                 if (degree==1) {\r
 121                         double dx = lineSegment[2]-lineSegment[0];\r
 122                         double dy = lineSegment[3]-lineSegment[1];\r
 123                         return Math.sqrt(dx*dx+dy*dy);\r
 124                 }\r
 125                 \r
 126                 // Quick'n'dirty approximation \r
 127                 // TODO Replace with accurate value\r
 128                 double result = 0;\r
 129                 Point2D prevPos = getLinePos(lineSegment, 0.0); \r
 130                 for (int i=0; i<10; i++)\r
 131                 {\r
 132                         double t = (double)(i+1)/10;\r
 133                         Point2D pos = getLinePos(lineSegment, t);\r
 134                         result += pos.distance(prevPos);\r
 135                         prevPos.setLocation(pos);\r
 136                 }\r
 137                 return result;\r
 138                 /*\r
 139                 if (degree==2) {\r
 140                         double c2x = bezier[2*0+0]-2*bezier[2*1+0]+bezier[2*2+0];\r
 141                         double c2y = bezier[2*0+1]-2*bezier[2*1+1]+bezier[2*2+1];\r
 142                         \r
 143                         double c1x = -2*bezier[2*0+0]+2*bezier[2*1+0];\r
 144                         double c1y = -2*bezier[2*0+1]+2*bezier[2*1+1];\r
 145                         \r
 146                         double c0x = bezier[2*0+0];\r
 147                         double c0y = bezier[2*0+1];\r
 148                         \r
 149                         double intg_x = c2x/3 + c1x/2 + c0x;\r
 150                         double intg_y = c2y/3 + c1y/2 + c0y;\r
 151                         System.out.println(intg_x +"\t" + intg_y);\r
 152                         \r
 153                         return intg_x + intg_y;\r
 154                 }\r
 155                 return 0;\r
 156                 */\r
 157         }\r
 158         \r
 159         public static int getLineDegree(double lineSegment[])\r
 160         {\r
 161                 assert(lineSegment.length==4 || lineSegment.length==6 || lineSegment.length==8);\r
 162                 return (lineSegment.length-2)/2;\r
 163         }\r
 164         \r
 165         /**\r
 166          * Get first and last point & tangent of a path\r
 167          * @param path\r
 168          * @param begin\r
 169          * @param beginDirection\r
 170          * @param end\r
 171          * @param endDirection\r
 172          * @return true if pi contained atleast one line segment\r
 173          */\r
 174         public static boolean getPathArrows(PathIterator pi, Point2D begin, Point2D beginDirection, Point2D end, Point2D endDirection)\r
 175         {\r
 176                 Iterator<double[]> i = toLineIterator(pi);\r
 177                 double first[]=null, last[]=null;\r
 178                 while (i.hasNext()) {\r
 179                         double[] current = i.next();\r
 180                         if (first==null) first = current;\r
 181                         if (!i.hasNext()) last = current;\r
 182                 }\r
 183                 if (first==null || last==null) return false;\r
 184                 begin.setLocation( getLinePos(first, 0) );\r
 185                 beginDirection.setLocation( getLineTangent(first, 0) );\r
 186                 end.setLocation( getLinePos(last, 1) );\r
 187                 Point2D endTangent = getLineTangent(last, 1);\r
 188                 endDirection.setLocation( -endTangent.getX(), -endTangent.getY() );\r
 189                 return true;\r
 190         }\r
 191 \r
 192         \r
 193         \r
 194         /**\r
 195          * Interpolate two paths\r
 196          * @param path1\r
 197          * @param path2\r
 198          * @param t phase 0..1, 0==path1, 1==path2\r
 199          * @return\r
 200          */\r
 201         public static Path2D interpolatePaths(PathIterator path1, PathIterator path2, double t)\r
 202         {\r
 203                 Path2D result = new Path2D.Double();\r
 204                                 \r
 205                 ArrayList<double[]> l1 = new ArrayList<double[]>(); \r
 206                 toLineSegments(path1, l1);\r
 207                 ArrayList<double[]> l2 = new ArrayList<double[]>(); \r
 208                 toLineSegments(path2, l2);\r
 209                 \r
 210                 if (l1.size()==l2.size())\r
 211                 {\r
 212                         \r
 213                 }\r
 214                 \r
 215                 result.append(path1, false);\r
 216                 return result;\r
 217         }\r
 218         \r
 219         public static double[] interpolateLineSegment(double l1[], double l2[], double t)\r
 220         {\r
 221                 assert(t>=0 && t<=1);\r
 222                 if (t==0) return Arrays.copyOf(l1, l1.length);\r
 223                 if (t==1) return Arrays.copyOf(l1, l1.length);\r
 224                 \r
 225                 int d1 = getLineDegree(l1);\r
 226                 int d2 = getLineDegree(l2);\r
 227                 \r
 228                 if (d1==d2) {\r
 229                         double result [] = new double[l1.length];               \r
 230                         for (int i=0; i<l1.length; i++)                 \r
 231                                 result[i] = l2[i]*t + l1[i]*(1-t); \r
 232                         return result;\r
 233                 }\r
 234                 \r
 235                 if (d2<d1) {\r
 236                         int d_ = d1;\r
 237                         d1 = d2;\r
 238                         d2 = d_;\r
 239                         double[] l_ = l1;\r
 240                         l1 = l2;\r
 241                         l2 = l_;\r
 242                         t = 1-t;\r
 243                 }\r
 244                 \r
 245                 // d1 < d2\r
 246                 double res[] = new double[l2.length];\r
 247                 \r
 248                 if (d1==1 && d2==2) {\r
 249                         res[0] = l1[0]*(1-t) + l2[0]*t;\r
 250                         res[1] = l1[1]*(1-t) + l2[1]*t;\r
 251                         res[4] = l1[2]*(1-t) + l2[4]*t;\r
 252                         res[5] = l1[3]*(1-t) + l2[5]*t;\r
 253                         double cx  = (l1[0]+l1[2])/2;\r
 254                         double cy  = (l1[0]+l1[2])/2;\r
 255                         res[2] = cx*(1-t) + l2[2]*t;\r
 256                         res[3] = cy*(1-t) + l2[3]*t;                    \r
 257                 }\r
 258 \r
 259                 if (d1==1 && d2==3) {\r
 260                         res[0] = l1[0]*(1-t) + l2[0]*t;\r
 261                         res[1] = l1[1]*(1-t) + l2[1]*t;\r
 262                         res[4] = l1[2]*(1-t) + l2[4]*t;\r
 263                         res[5] = l1[3]*(1-t) + l2[5]*t;\r
 264                         double cx  = (l1[0]+l1[2])/2;\r
 265                         double cy  = (l1[0]+l1[2])/2;\r
 266                         res[2] = cx*(1-t) + l2[2]*t;\r
 267                         res[3] = cy*(1-t) + l2[3]*t;                    \r
 268                         res[4] = cx*(1-t) + l2[4]*t;\r
 269                         res[5] = cy*(1-t) + l2[5]*t;                    \r
 270                 }\r
 271                 \r
 272                 if (d1==2 && d2==3) {\r
 273                         res[0] = l1[0]*(1-t) + l2[0]*t;\r
 274                         res[1] = l1[1]*(1-t) + l2[1]*t;\r
 275                         res[2] = l1[2]*(1-t) + l2[2]*t;\r
 276                         res[3] = l1[3]*(1-t) + l2[3]*t;                 \r
 277                         res[4] = l1[2]*(1-t) + l2[4]*t;\r
 278                         res[5] = l1[3]*(1-t) + l2[5]*t;                 \r
 279                         res[6] = l1[4]*(1-t) + l2[6]*t;\r
 280                         res[7] = l1[5]*(1-t) + l2[7]*t;\r
 281                 }                                       \r
 282                 \r
 283                 return res;\r
 284         }\r
 285         \r
 286         /**\r
 287          * Returns an iterator that constructs line segments by traversing a path iterator\r
 288          * @param pi path iterator\r
 289          * @return line segment iterator\r
 290          */\r
 291         public static Iterator<double[]> toLineIterator(final PathIterator pi)\r
 292         {\r
 293                 return new PathIteratorToSegmentIterator(pi);\r
 294         }\r
 295         \r
 296         public static void toLineSegments(PathIterator pi, Collection<double[]> result)\r
 297         {\r
 298                 Iterator<double[]> i = toLineIterator(pi);\r
 299                 while (i.hasNext()) {\r
 300                         double[] segment = i.next();\r
 301                         result.add(segment);\r
 302                 }\r
 303         }\r
 304         \r
 305         private static class PathIteratorToSegmentIterator implements Iterator<double[]>\r
 306         {\r
 307                 final PathIterator pi;\r
 308                 double  lineTo[] = new double[6];\r
 309                 double  startPos[] = new double[2];\r
 310                 double  from[] = new double[2];\r
 311                 int             degree = 0;\r
 312                 PathIteratorToSegmentIterator(PathIterator pi) {\r
 313                         this.pi = pi;\r
 314                         while(!pi.isDone()) {\r
 315                                 int type = pi.currentSegment(lineTo);\r
 316                                 pi.next();\r
 317                                 if (type == PathIterator.SEG_MOVETO) {\r
 318                                         startPos[0] = from[0] = lineTo[0];\r
 319                                         startPos[1] = from[1] = lineTo[1];\r
 320                                 }\r
 321                                 if (type == PathIterator.SEG_CLOSE) {\r
 322                                         type = PathIterator.SEG_LINETO;\r
 323                                         lineTo[0] = startPos[0];\r
 324                                         lineTo[1] = startPos[1];\r
 325                                 }\r
 326                                 if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)\r
 327                                 {\r
 328                                         degree = type;\r
 329                                         // from == xx\r
 330                                         break;\r
 331                                 }\r
 332                         }\r
 333                 }               \r
 334                 @Override\r
 335                 public boolean hasNext() {\r
 336                         return degree>0;\r
 337                 }\r
 338                 @Override\r
 339                 public double[] next() {\r
 340                         if (degree==0) return null;\r
 341                         double result[] = new double[degree*2+2]; \r
 342                         result[0] = from[0];\r
 343                         result[1] = from[1];\r
 344                         result[2] = lineTo[0];\r
 345                         result[3] = lineTo[1];\r
 346                         if (degree==2) {\r
 347                                 result[4] = lineTo[2];\r
 348                                 result[5] = lineTo[3];\r
 349                         } else if (degree==3) {\r
 350                                 result[6] = lineTo[4];\r
 351                                 result[7] = lineTo[5];\r
 352                         }\r
 353                         // traverse path iterator until end or until next segment is known\r
 354                         degree = 0;\r
 355                         from[0] = lineTo[0];\r
 356                         from[1] = lineTo[1];\r
 357                         while(!pi.isDone()) {\r
 358                                 int type = pi.currentSegment(lineTo);\r
 359                                 pi.next();\r
 360                                 if (type == PathIterator.SEG_MOVETO) {\r
 361                                         startPos[0] = from[0] = lineTo[0];\r
 362                                         startPos[1] = from[1] = lineTo[1];\r
 363                                 }\r
 364                                 if (type == PathIterator.SEG_CLOSE) {\r
 365                                         type = PathIterator.SEG_LINETO;\r
 366                                         lineTo[0] = startPos[0];\r
 367                                         lineTo[1] = startPos[1];\r
 368                                 }\r
 369                                 if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)\r
 370                                 {\r
 371                                         degree = type;\r
 372                                         break;\r
 373                                 }\r
 374                         }\r
 375                         return result;\r
 376                 }\r
 377                 @Override\r
 378                 public void remove() {\r
 379                         throw new UnsupportedOperationException();\r
 380                 }\r
 381         }\r
 382 \r
 383         \r
 384         \r
 385         \r
 386         \r
 387         \r
 388         /**\r
 389          * Finds intersection of two half-straight lines\r
 390          * @param p0x\r
 391          * @param p0y\r
 392          * @param dir0\r
 393          * @param p1x\r
 394          * @param p1y\r
 395          * @param dir1\r
 396          * @return\r
 397          */\r
 398         public static Point2D findIntersection(double p0x, double p0y, double dir0, double p1x, double p1y, double dir1)\r
 399         {\r
 400                 Point2D uv = new Point2D.Double();\r
 401                 GeometryUtils.toUnitVector(dir0, uv);\r
 402                 double v0x = uv.getX();\r
 403                 double v0y = uv.getY();\r
 404                 GeometryUtils.toUnitVector(dir1, uv);\r
 405                 double v1x = uv.getX();\r
 406                 double v1y = uv.getY();\r
 407                 return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);\r
 408         }\r
 409         \r
 410         /**\r
 411          * Finds intersection of two half-straight lines\r
 412          * @param p0\r
 413          * @param v0\r
 414          * @param p1\r
 415          * @param v1\r
 416          * @return\r
 417          */\r
 418         public static Point2D findIntersection(Point2D p0, Point2D v0, Point2D p1, Point2D v1)\r
 419         {\r
 420                 double v0x = v0.getX();\r
 421                 double v0y = v0.getY();\r
 422                 double v1x = v1.getX();\r
 423                 double v1y = v1.getY();\r
 424                 double p0x = p0.getX();\r
 425                 double p0y = p0.getY();\r
 426                 double p1x = p1.getX();\r
 427                 double p1y = p1.getY();         \r
 428                 return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);\r
 429         }\r
 430         \r
 431         /**\r
 432          * Finds intersection of two half-straight lines\r
 433          * @param p1\r
 434          * @param v1 direction vector (unit vector)\r
 435          * @param p2\r
 436          * @param v2 direction vector (unit vector)\r
 437          * @return\r
 438          */\r
 439         public static Point2D findIntersection(double p0x, double p0y, double v0x, double v0y, double p1x, double p1y, double v1x, double v1y)\r
 440         {\r
 441                 if (p0x==p1x && p0y==p1y) return new Point2D.Double(p0x, p0y);\r
 442                 /*\r
 443                    i = Intersection point                 \r
 444                    i = p0 + t*v0 = p1 + r*v1;\r
 445                  */                             \r
 446                 double denominator      = v0y*v1x - v0x*v1y;\r
 447                 // Straights are in same or opposite directions\r
 448                 if (denominator == 0) {\r
 449                         return null;\r
 450                         /*\r
 451                         // Do they overlap?\r
 452                         boolean overlap         = v0x*(p1y-p0y) - v0y*(p1x-p1x) == 0;\r
 453                         if (!overlap) return null;\r
 454                         double t = v1x==0?(p1y-p0y)/v0y:(p1x-p0x)/v0x;\r
 455                         double r = v0x==0?(p0y-p1y)/v1y:(p0x-p1x)/v1x;\r
 456                         boolean parallel        = (v0x==v1x)&&(v0y==v1y);\r
 457                         if (parallel) {\r
 458                                 if (t<0) return new Point2D.Double(p1x, p1y);\r
 459                                 if (r<0) return new Point2D.Double(p0x, p0y);\r
 460                                 return null;\r
 461                         }\r
 462                         return null;\r
 463                         */\r
 464                 }\r
 465                 \r
 466                 double nominator        = -v0x*p0y + v0x*p1y + v0y*p0x - v0y*p1x;\r
 467                 double r                        = nominator / denominator;\r
 468                 if (r<0) return null;\r
 469                 // XXX t on väärin\r
 470                 //double t                      = -p0x + p1x + v1x*r;\r
 471                 //if (t<0) return null;\r
 472                 \r
 473                 double x                        = p1x + r*v1x;\r
 474                 double y                        = p1y + r*v1y;\r
 475                 return new Point2D.Double(x, y);\r
 476         }\r
 477 \r
 478         public static int findNearestPoints(Point2D p0, Point2D v0, Point2D p1, Point2D v1, Point2D cp1, Point2D cp2)\r
 479         {\r
 480                 return findNearestPoints(p0.getX(), p0.getY(), v0.getX(), v0.getY(), p1.getX(), p1.getY(), v1.getX(), v1.getY(), cp1, cp2);\r
 481         }\r
 482         \r
 483         public static int findNearestPoints(double p0x, double p0y, double v0x, double v0y, double p1x, double p1y, double v1x, double v1y, Point2D cp1, Point2D cp2)\r
 484         {\r
 485                 int result = 0;\r
 486                 double r = -( v1x*(p1x-p0x) + v1y*(p1y-p0y) ) / (v1x*v1x+v1y*v1y);\r
 487                 double t = -( v0x*(p0x-p1x) + v0y*(p0y-p1y) ) / (v0x*v0x+v0y*v0y);\r
 488                 if (t>0) {\r
 489                         cp1.setLocation( p0x + v0x*t, p0y + v0y*t );\r
 490                         result |= 1;\r
 491                 }\r
 492                 if (r>0) {\r
 493                         cp2.setLocation( p1x + v1x*r, p1y + v1y*r );\r
 494                         result |= 2;\r
 495                 }\r
 496                 return result;\r
 497         }\r
 498         \r
 499         public static double[] subdiv_takeLeft(double line[], double t)\r
 500         {\r
 501                 int     degree  = getLineDegree(line); \r
 502                 \r
 503                 double p0x = line[0];\r
 504                 double p0y = line[1];\r
 505                 double p1x = line[2];\r
 506                 double p1y = line[3];\r
 507                 double p1x_  = p0x*(1-t) + p1x*t;\r
 508                 double p1y_  = p0y*(1-t) + p1y*t;\r
 509                 if (degree==1)                  \r
 510                         return new double[] {p0x, p0y, p1x_, p1y_};\r
 511 \r
 512                 double p2x = line[4];\r
 513                 double p2y = line[5];                   \r
 514 \r
 515                 double q0x = p0x*(1-t) + p1x*t;\r
 516                 double q0y = p0y*(1-t) + p1y*t;\r
 517 \r
 518                 double q1x = p1x*(1-t) + p2x*t;\r
 519                 double q1y = p1y*(1-t) + p2y*t;\r
 520                 \r
 521                 double p2x_ = q0x*(1-t) + q1x*t;\r
 522                 double p2y_ = q0y*(1-t) + q1y*t;\r
 523                 if (degree==2)          \r
 524                         return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_};                 \r
 525                 \r
 526                 \r
 527                 double p3x = line[6];\r
 528                 double p3y = line[7];\r
 529                 \r
 530                 double q2x = p2x*(1-t) + p3x*t;\r
 531                 double q2y = p2y*(1-t) + p3y*t;\r
 532 \r
 533                 double r0x = q0x*(1-t) + q1x*t;\r
 534                 double r0y = q0y*(1-t) + q1y*t;\r
 535                         \r
 536                 double r1x = q1x*(1-t) + q2x*t;\r
 537                 double r1y = q1y*(1-t) + q2y*t;\r
 538                         \r
 539                 double p3x_  = r0x*(1-t) + r1x*t;\r
 540                 double p3y_  = r0y*(1-t) + r1y*t;\r
 541 \r
 542                 if (degree==3) \r
 543                         return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_, p3x_, p3y_};\r
 544                 \r
 545                 return null;\r
 546         }\r
 547         \r
 548         public static double[] subdiv_takeRight(double line[], double t)\r
 549         {\r
 550                 int     degree  = getLineDegree(line); \r
 551                 \r
 552                 double p0x = line[0];\r
 553                 double p0y = line[1];\r
 554                 double p1x = line[2];\r
 555                 double p1y = line[3];\r
 556 \r
 557                 double p0x_  = p0x*(1-t) + p1x*t;\r
 558                 double p0y_  = p0y*(1-t) + p1y*t;\r
 559                 if (degree==1)                  \r
 560                         return new double[] {p0x_, p0y_, p1x, p1y};\r
 561                 \r
 562                 double p2x = line[4];\r
 563                 double p2y = line[5];                   \r
 564 \r
 565                 double q0x = p0x*(1-t) + p1x*t;\r
 566                 double q0y = p0y*(1-t) + p1y*t;\r
 567 \r
 568                 double q1x = p1x*(1-t) + p2x*t;\r
 569                 double q1y = p1y*(1-t) + p2y*t;\r
 570                 \r
 571                 double p2x_ = q0x*(1-t) + q1x*t;\r
 572                 double p2y_ = q0y*(1-t) + q1y*t;        \r
 573 \r
 574                 if (degree==2)          \r
 575                         return new double[] {p2x_, p2y_, q1x, q1y, p2x, p2y};                   \r
 576                                 \r
 577                 double p3x = line[6];\r
 578                 double p3y = line[7];\r
 579                 \r
 580                 double q2x = p2x*(1-t) + p3x*t;\r
 581                 double q2y = p2y*(1-t) + p3y*t;\r
 582 \r
 583                 double r0x = q0x*(1-t) + q1x*t;\r
 584                 double r0y = q0y*(1-t) + q1y*t;\r
 585                         \r
 586                 double r1x = q1x*(1-t) + q2x*t;\r
 587                 double r1y = q1y*(1-t) + q2y*t;\r
 588                         \r
 589                 double p3x_  = r0x*(1-t) + r1x*t;\r
 590                 double p3y_  = r0y*(1-t) + r1y*t;\r
 591 \r
 592                 if (degree==3) \r
 593                         return new double[] {p3x_, p3y_, r1x, r1y, q2x, q2y, p3x, p3y};\r
 594                 \r
 595                 return null;\r
 596         }\r
 597         \r
 598 \r
 599 \r
 600         /**\r
 601          * Crops line segment into a smaller line segment\r
 602          * @param line line segment\r
 603          * @param t0 begin t\r
 604          * @param t1 end t\r
 605          * @return cropped line segment\r
 606          */\r
 607         public static double[] cropLine(double line[], double t0, double t1)\r
 608         {\r
 609                 double temp[] = subdiv_takeLeft(line, t1);\r
 610                 return subdiv_takeRight(temp, t0/t1);\r
 611         }\r
 612         \r
 613         @SuppressWarnings("unused")\r
 614         private static Point2D interpolateLine(double x0, double y0, double x1, double y1, double t)\r
 615         {\r
 616                 double x = (x1-x0)*t + x0;\r
 617                 double y = (y1-y0)*t + y0;\r
 618                 return new Point2D.Double(x, y);\r
 619         }\r
 620         \r
 621         public static Path2D toPath(double lineSegment[])\r
 622         {\r
 623                 int     degree  = getLineDegree(lineSegment); \r
 624                 Path2D  p = new Path2D.Double();\r
 625                 p.moveTo(lineSegment[0], lineSegment[1]);\r
 626                 if (degree==1)\r
 627                         p.lineTo(lineSegment[2], lineSegment[3]);\r
 628                 if (degree==2)\r
 629                         p.quadTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5]);\r
 630                 if (degree==3)\r
 631                         p.curveTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5], lineSegment[6], lineSegment[7]);              \r
 632                 return p;\r
 633         }\r
 634 \r
 635         public static Path2D path(double ... pos)\r
 636         {\r
 637                 assert(pos.length%2==0 && pos.length>=4);\r
 638                 Path2D p = new Path2D.Double();\r
 639                 p.moveTo(pos[0], pos[1]);\r
 640                 for (int i=1; i<pos.length/2; i++)\r
 641                 {\r
 642                         p.lineTo(pos[i*2], pos[i*2+1]);\r
 643                 }\r
 644                 return p;\r
 645         }\r
 646 \r
 647         /**\r
 648          * Create 3rd degree path. Every second point is a control point.\r
 649          * @param positions\r
 650          * @return\r
 651          */\r
 652 //      public static Path2D closePath3rdDeg(double ... pos)\r
 653 //      {\r
 654 //              assert(pos.length%2==0 && pos.length>=4);\r
 655 //              Path2D p = new Path2D.Double();\r
 656 //              p.moveTo(pos[0], pos[1]);\r
 657 //              for (int i=1; i<pos.length/2; i++)\r
 658 //              {\r
 659 //                      p.lineTo(pos[i*2], pos[i*2+1]);\r
 660 //              }\r
 661 //              return p;\r
 662 //      }\r
 663 //      \r
 664         \r
 665         public static Path2D closedPath(double ... pos)\r
 666         {\r
 667                 Path2D p = path(pos);\r
 668                 p.closePath();\r
 669                 return p;\r
 670         }       \r
 671         \r
 672         public static void main(String[] args) {\r
 673                 // test crop line\r
 674                 double[] cubic = new double[] {0,0, 0, -1, 3, -1, 3,0};\r
 675                 double[] cropped = cropLine(cubic, 0.2, 1);\r
 676                 System.out.println(Arrays.toString(cropped));\r
 677                 System.out.println(getLinePos(cubic, 0.5));\r
 678                 System.out.println(getLinePos(cropped, 0.375));\r
 679                 /*              \r
 680                                 Path2D p = new Path2D.Double();\r
 681                                 p.moveTo(4, 1);\r
 682                                 p.quadTo(6,1,6,3);\r
 683                                 p.quadTo(6,5,4,5);\r
 684                                 p.quadTo(2,5,2,3);\r
 685                                 p.quadTo(2,1,4,1);\r
 686                                 PathIterator pi = p.getPathIterator(null);\r
 687                                 double dada[] = new double[6];\r
 688                                 while (!pi.isDone()) {\r
 689                                         Arrays.fill(dada, 0);\r
 690                                         int type = pi.currentSegment(dada);\r
 691                                         System.out.println(type+":\t"+Arrays.toString(dada));\r
 692                                         pi.next();\r
 693                                 }*/\r
 694                                 \r
 695                                 assert(findIntersection(0,0,90,  10,1,270+45)!=null);\r
 696                                 assert(findIntersection(0,0,90,  1,1,89)!=null);\r
 697                                 assert(findIntersection(0,0,90,  1,1,270+45)==null);\r
 698                                 //System.out.println(findIntersection(0,0,270,  10,0,270));\r
 699                                 //System.out.println(findIntersection(0,0,90,  10,-10,180));            \r
 700                                 /*\r
 701                                 Point2D cp1 = new Point2D.Double();\r
 702                                 Point2D cp2 = new Point2D.Double();\r
 703                                 int i = findNearestPoints(0, 0, 0, 1, 2, 10, 0, -1, cp1, cp2);\r
 704                                 if (i>0)\r
 705                                         System.out.println(cp1+"\t"+cp2);\r
 706                                 else\r
 707                                         System.out.println("non posible");\r
 708 */\r
 709                                 /*\r
 710                                 double bezier[] = new double[] {100,1,102,1,105,1};  \r
 711                                 System.out.println(getLineLength(bezier, 2));\r
 712                                 for (int i=0; i<=10; i++)\r
 713                                 {\r
 714                                         double t = ((double)i)/10;\r
 715                                         System.out.println(GeometryUtils.getCompassDirection( getLineTangent(bezier, t) ));                     \r
 716                                 }*/\r
 717                         }\r
 718                         \r
 719         \r
 720 }\r