1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
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
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.g2d.utils;
14 import java.awt.geom.Path2D;
15 import java.awt.geom.PathIterator;
16 import java.awt.geom.Point2D;
17 import java.util.ArrayList;
18 import java.util.Arrays;
19 import java.util.Collection;
20 import java.util.Iterator;
25 * A line segment (linear, quadratic or cubic bezier) is described
26 * with a double array. The length of the array describes its degree (4,6,8).
27 * The first 2 elements define start point and last 2 the end point.
28 * Points in the middle are bezier control points.
30 * @author Toni Kalajainen
32 public class PathUtils {
35 * Get tangent of an bezier
36 * @param lineSegment bezier of n degrees
41 public static Point2D getLineTangent(double lineSegment[], double t)
43 int degree = getLineDegree(lineSegment);
47 x = lineSegment[2*1+0] - lineSegment[2*0+0];
48 y = lineSegment[2*1+1] - lineSegment[2*0+1];
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]);
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]);
53 } else if (degree==3) {
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;
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;
58 return new Point2D.Double(x, y);
67 public static Point2D getLinePos(double lineSegment[], double t)
69 assert(lineSegment!=null);
70 int degree = getLineDegree(lineSegment);
74 double p0x = lineSegment[0];
75 double p0y = lineSegment[1];
76 double p1x = lineSegment[2];
77 double p1y = lineSegment[3];
79 x = p0x*(1-t) + t*p1x;
80 y = p0y*(1-t) + t*p1y;
81 } else if (degree==2) {
82 double p0x = lineSegment[0];
83 double p0y = lineSegment[1];
84 double p1x = lineSegment[2];
85 double p1y = lineSegment[3];
86 double p2x = lineSegment[4];
87 double p2y = lineSegment[5];
89 double c2x = p0x-2*p1x+p2x;
90 double c2y = p0y-2*p1y+p2y;
92 double c1x = -2*p0x+2*p1x;
93 double c1y = -2*p0y+2*p1y;
98 x = t*t*c2x+t*c1x+c0x;
99 y = t*t*c2y+t*c1y+c0y;
100 } else if (degree==3) {
101 double p0x = lineSegment[0];
102 double p0y = lineSegment[1];
103 double p1x = lineSegment[2];
104 double p1y = lineSegment[3];
105 double p2x = lineSegment[4];
106 double p2y = lineSegment[5];
107 double p3x = lineSegment[6];
108 double p3y = lineSegment[7];
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;
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;
114 return new Point2D.Double(x, y);
117 public static double getLineLength(double lineSegment[])
119 int degree = getLineDegree(lineSegment);
121 double dx = lineSegment[2]-lineSegment[0];
122 double dy = lineSegment[3]-lineSegment[1];
123 return Math.sqrt(dx*dx+dy*dy);
126 // Quick'n'dirty approximation
127 // TODO Replace with accurate value
129 Point2D prevPos = getLinePos(lineSegment, 0.0);
130 for (int i=0; i<10; i++)
132 double t = (double)(i+1)/10;
133 Point2D pos = getLinePos(lineSegment, t);
134 result += pos.distance(prevPos);
135 prevPos.setLocation(pos);
140 double c2x = bezier[2*0+0]-2*bezier[2*1+0]+bezier[2*2+0];
141 double c2y = bezier[2*0+1]-2*bezier[2*1+1]+bezier[2*2+1];
143 double c1x = -2*bezier[2*0+0]+2*bezier[2*1+0];
144 double c1y = -2*bezier[2*0+1]+2*bezier[2*1+1];
146 double c0x = bezier[2*0+0];
147 double c0y = bezier[2*0+1];
149 double intg_x = c2x/3 + c1x/2 + c0x;
150 double intg_y = c2y/3 + c1y/2 + c0y;
151 System.out.println(intg_x +"\t" + intg_y);
153 return intg_x + intg_y;
159 public static int getLineDegree(double lineSegment[])
161 assert(lineSegment.length==4 || lineSegment.length==6 || lineSegment.length==8);
162 return (lineSegment.length-2)/2;
166 * Get first and last point & tangent of a path
169 * @param beginDirection
171 * @param endDirection
172 * @return true if pi contained atleast one line segment
174 public static boolean getPathArrows(PathIterator pi, Point2D begin, Point2D beginDirection, Point2D end, Point2D endDirection)
176 Iterator<double[]> i = toLineIterator(pi);
177 double first[]=null, last[]=null;
178 while (i.hasNext()) {
179 double[] current = i.next();
180 if (first==null) first = current;
181 if (!i.hasNext()) last = current;
183 if (first==null || last==null) return false;
184 begin.setLocation( getLinePos(first, 0) );
185 beginDirection.setLocation( getLineTangent(first, 0) );
186 end.setLocation( getLinePos(last, 1) );
187 Point2D endTangent = getLineTangent(last, 1);
188 endDirection.setLocation( -endTangent.getX(), -endTangent.getY() );
195 * Interpolate two paths
198 * @param t phase 0..1, 0==path1, 1==path2
201 public static Path2D interpolatePaths(PathIterator path1, PathIterator path2, double t)
203 Path2D result = new Path2D.Double();
205 ArrayList<double[]> l1 = new ArrayList<double[]>();
206 toLineSegments(path1, l1);
207 ArrayList<double[]> l2 = new ArrayList<double[]>();
208 toLineSegments(path2, l2);
210 if (l1.size()==l2.size())
215 result.append(path1, false);
219 public static double[] interpolateLineSegment(double l1[], double l2[], double t)
221 assert(t>=0 && t<=1);
222 if (t==0) return Arrays.copyOf(l1, l1.length);
223 if (t==1) return Arrays.copyOf(l1, l1.length);
225 int d1 = getLineDegree(l1);
226 int d2 = getLineDegree(l2);
229 double result [] = new double[l1.length];
230 for (int i=0; i<l1.length; i++)
231 result[i] = l2[i]*t + l1[i]*(1-t);
246 double res[] = new double[l2.length];
248 if (d1==1 && d2==2) {
249 res[0] = l1[0]*(1-t) + l2[0]*t;
250 res[1] = l1[1]*(1-t) + l2[1]*t;
251 res[4] = l1[2]*(1-t) + l2[4]*t;
252 res[5] = l1[3]*(1-t) + l2[5]*t;
253 double cx = (l1[0]+l1[2])/2;
254 double cy = (l1[0]+l1[2])/2;
255 res[2] = cx*(1-t) + l2[2]*t;
256 res[3] = cy*(1-t) + l2[3]*t;
259 if (d1==1 && d2==3) {
260 res[0] = l1[0]*(1-t) + l2[0]*t;
261 res[1] = l1[1]*(1-t) + l2[1]*t;
262 res[4] = l1[2]*(1-t) + l2[4]*t;
263 res[5] = l1[3]*(1-t) + l2[5]*t;
264 double cx = (l1[0]+l1[2])/2;
265 double cy = (l1[0]+l1[2])/2;
266 res[2] = cx*(1-t) + l2[2]*t;
267 res[3] = cy*(1-t) + l2[3]*t;
268 res[4] = cx*(1-t) + l2[4]*t;
269 res[5] = cy*(1-t) + l2[5]*t;
272 if (d1==2 && d2==3) {
273 res[0] = l1[0]*(1-t) + l2[0]*t;
274 res[1] = l1[1]*(1-t) + l2[1]*t;
275 res[2] = l1[2]*(1-t) + l2[2]*t;
276 res[3] = l1[3]*(1-t) + l2[3]*t;
277 res[4] = l1[2]*(1-t) + l2[4]*t;
278 res[5] = l1[3]*(1-t) + l2[5]*t;
279 res[6] = l1[4]*(1-t) + l2[6]*t;
280 res[7] = l1[5]*(1-t) + l2[7]*t;
287 * Returns an iterator that constructs line segments by traversing a path iterator
288 * @param pi path iterator
289 * @return line segment iterator
291 public static Iterator<double[]> toLineIterator(final PathIterator pi)
293 return new PathIteratorToSegmentIterator(pi);
296 public static void toLineSegments(PathIterator pi, Collection<double[]> result)
298 Iterator<double[]> i = toLineIterator(pi);
299 while (i.hasNext()) {
300 double[] segment = i.next();
305 private static class PathIteratorToSegmentIterator implements Iterator<double[]>
307 final PathIterator pi;
308 double lineTo[] = new double[6];
309 double startPos[] = new double[2];
310 double from[] = new double[2];
312 PathIteratorToSegmentIterator(PathIterator pi) {
314 while(!pi.isDone()) {
315 int type = pi.currentSegment(lineTo);
317 if (type == PathIterator.SEG_MOVETO) {
318 startPos[0] = from[0] = lineTo[0];
319 startPos[1] = from[1] = lineTo[1];
321 if (type == PathIterator.SEG_CLOSE) {
322 type = PathIterator.SEG_LINETO;
323 lineTo[0] = startPos[0];
324 lineTo[1] = startPos[1];
326 if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)
335 public boolean hasNext() {
339 public double[] next() {
340 if (degree==0) return null;
341 double result[] = new double[degree*2+2];
344 result[2] = lineTo[0];
345 result[3] = lineTo[1];
347 result[4] = lineTo[2];
348 result[5] = lineTo[3];
349 } else if (degree==3) {
350 result[6] = lineTo[4];
351 result[7] = lineTo[5];
353 // traverse path iterator until end or until next segment is known
357 while(!pi.isDone()) {
358 int type = pi.currentSegment(lineTo);
360 if (type == PathIterator.SEG_MOVETO) {
361 startPos[0] = from[0] = lineTo[0];
362 startPos[1] = from[1] = lineTo[1];
364 if (type == PathIterator.SEG_CLOSE) {
365 type = PathIterator.SEG_LINETO;
366 lineTo[0] = startPos[0];
367 lineTo[1] = startPos[1];
369 if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)
378 public void remove() {
379 throw new UnsupportedOperationException();
389 * Finds intersection of two half-straight lines
398 public static Point2D findIntersection(double p0x, double p0y, double dir0, double p1x, double p1y, double dir1)
400 Point2D uv = new Point2D.Double();
401 GeometryUtils.toUnitVector(dir0, uv);
402 double v0x = uv.getX();
403 double v0y = uv.getY();
404 GeometryUtils.toUnitVector(dir1, uv);
405 double v1x = uv.getX();
406 double v1y = uv.getY();
407 return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);
411 * Finds intersection of two half-straight lines
418 public static Point2D findIntersection(Point2D p0, Point2D v0, Point2D p1, Point2D v1)
420 double v0x = v0.getX();
421 double v0y = v0.getY();
422 double v1x = v1.getX();
423 double v1y = v1.getY();
424 double p0x = p0.getX();
425 double p0y = p0.getY();
426 double p1x = p1.getX();
427 double p1y = p1.getY();
428 return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);
432 * Finds intersection of two half-straight lines
434 * @param v1 direction vector (unit vector)
436 * @param v2 direction vector (unit vector)
439 public static Point2D findIntersection(double p0x, double p0y, double v0x, double v0y, double p1x, double p1y, double v1x, double v1y)
441 if (p0x==p1x && p0y==p1y) return new Point2D.Double(p0x, p0y);
443 i = Intersection point
444 i = p0 + t*v0 = p1 + r*v1;
446 double denominator = v0y*v1x - v0x*v1y;
447 // Straights are in same or opposite directions
448 if (denominator == 0) {
452 boolean overlap = v0x*(p1y-p0y) - v0y*(p1x-p1x) == 0;
453 if (!overlap) return null;
454 double t = v1x==0?(p1y-p0y)/v0y:(p1x-p0x)/v0x;
455 double r = v0x==0?(p0y-p1y)/v1y:(p0x-p1x)/v1x;
456 boolean parallel = (v0x==v1x)&&(v0y==v1y);
458 if (t<0) return new Point2D.Double(p1x, p1y);
459 if (r<0) return new Point2D.Double(p0x, p0y);
466 double nominator = -v0x*p0y + v0x*p1y + v0y*p0x - v0y*p1x;
467 double r = nominator / denominator;
468 if (r<0) return null;
470 //double t = -p0x + p1x + v1x*r;
471 //if (t<0) return null;
473 double x = p1x + r*v1x;
474 double y = p1y + r*v1y;
475 return new Point2D.Double(x, y);
478 public static int findNearestPoints(Point2D p0, Point2D v0, Point2D p1, Point2D v1, Point2D cp1, Point2D cp2)
480 return findNearestPoints(p0.getX(), p0.getY(), v0.getX(), v0.getY(), p1.getX(), p1.getY(), v1.getX(), v1.getY(), cp1, cp2);
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)
486 double r = -( v1x*(p1x-p0x) + v1y*(p1y-p0y) ) / (v1x*v1x+v1y*v1y);
487 double t = -( v0x*(p0x-p1x) + v0y*(p0y-p1y) ) / (v0x*v0x+v0y*v0y);
489 cp1.setLocation( p0x + v0x*t, p0y + v0y*t );
493 cp2.setLocation( p1x + v1x*r, p1y + v1y*r );
499 public static double[] subdiv_takeLeft(double line[], double t)
501 int degree = getLineDegree(line);
503 double p0x = line[0];
504 double p0y = line[1];
505 double p1x = line[2];
506 double p1y = line[3];
507 double p1x_ = p0x*(1-t) + p1x*t;
508 double p1y_ = p0y*(1-t) + p1y*t;
510 return new double[] {p0x, p0y, p1x_, p1y_};
512 double p2x = line[4];
513 double p2y = line[5];
515 double q0x = p0x*(1-t) + p1x*t;
516 double q0y = p0y*(1-t) + p1y*t;
518 double q1x = p1x*(1-t) + p2x*t;
519 double q1y = p1y*(1-t) + p2y*t;
521 double p2x_ = q0x*(1-t) + q1x*t;
522 double p2y_ = q0y*(1-t) + q1y*t;
524 return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_};
527 double p3x = line[6];
528 double p3y = line[7];
530 double q2x = p2x*(1-t) + p3x*t;
531 double q2y = p2y*(1-t) + p3y*t;
533 double r0x = q0x*(1-t) + q1x*t;
534 double r0y = q0y*(1-t) + q1y*t;
536 double r1x = q1x*(1-t) + q2x*t;
537 double r1y = q1y*(1-t) + q2y*t;
539 double p3x_ = r0x*(1-t) + r1x*t;
540 double p3y_ = r0y*(1-t) + r1y*t;
543 return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_, p3x_, p3y_};
548 public static double[] subdiv_takeRight(double line[], double t)
550 int degree = getLineDegree(line);
552 double p0x = line[0];
553 double p0y = line[1];
554 double p1x = line[2];
555 double p1y = line[3];
557 double p0x_ = p0x*(1-t) + p1x*t;
558 double p0y_ = p0y*(1-t) + p1y*t;
560 return new double[] {p0x_, p0y_, p1x, p1y};
562 double p2x = line[4];
563 double p2y = line[5];
565 double q0x = p0x*(1-t) + p1x*t;
566 double q0y = p0y*(1-t) + p1y*t;
568 double q1x = p1x*(1-t) + p2x*t;
569 double q1y = p1y*(1-t) + p2y*t;
571 double p2x_ = q0x*(1-t) + q1x*t;
572 double p2y_ = q0y*(1-t) + q1y*t;
575 return new double[] {p2x_, p2y_, q1x, q1y, p2x, p2y};
577 double p3x = line[6];
578 double p3y = line[7];
580 double q2x = p2x*(1-t) + p3x*t;
581 double q2y = p2y*(1-t) + p3y*t;
583 double r0x = q0x*(1-t) + q1x*t;
584 double r0y = q0y*(1-t) + q1y*t;
586 double r1x = q1x*(1-t) + q2x*t;
587 double r1y = q1y*(1-t) + q2y*t;
589 double p3x_ = r0x*(1-t) + r1x*t;
590 double p3y_ = r0y*(1-t) + r1y*t;
593 return new double[] {p3x_, p3y_, r1x, r1y, q2x, q2y, p3x, p3y};
601 * Crops line segment into a smaller line segment
602 * @param line line segment
605 * @return cropped line segment
607 public static double[] cropLine(double line[], double t0, double t1)
609 double temp[] = subdiv_takeLeft(line, t1);
610 return subdiv_takeRight(temp, t0/t1);
613 @SuppressWarnings("unused")
614 private static Point2D interpolateLine(double x0, double y0, double x1, double y1, double t)
616 double x = (x1-x0)*t + x0;
617 double y = (y1-y0)*t + y0;
618 return new Point2D.Double(x, y);
621 public static Path2D toPath(double lineSegment[])
623 int degree = getLineDegree(lineSegment);
624 Path2D p = new Path2D.Double();
625 p.moveTo(lineSegment[0], lineSegment[1]);
627 p.lineTo(lineSegment[2], lineSegment[3]);
629 p.quadTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5]);
631 p.curveTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5], lineSegment[6], lineSegment[7]);
635 public static Path2D path(double ... pos)
637 assert(pos.length%2==0 && pos.length>=4);
638 Path2D p = new Path2D.Double();
639 p.moveTo(pos[0], pos[1]);
640 for (int i=1; i<pos.length/2; i++)
642 p.lineTo(pos[i*2], pos[i*2+1]);
648 * Create 3rd degree path. Every second point is a control point.
652 // public static Path2D closePath3rdDeg(double ... pos)
654 // assert(pos.length%2==0 && pos.length>=4);
655 // Path2D p = new Path2D.Double();
656 // p.moveTo(pos[0], pos[1]);
657 // for (int i=1; i<pos.length/2; i++)
659 // p.lineTo(pos[i*2], pos[i*2+1]);
665 public static Path2D closedPath(double ... pos)
667 Path2D p = path(pos);
672 public static void main(String[] args) {
674 double[] cubic = new double[] {0,0, 0, -1, 3, -1, 3,0};
675 double[] cropped = cropLine(cubic, 0.2, 1);
676 System.out.println(Arrays.toString(cropped));
677 System.out.println(getLinePos(cubic, 0.5));
678 System.out.println(getLinePos(cropped, 0.375));
680 Path2D p = new Path2D.Double();
686 PathIterator pi = p.getPathIterator(null);
687 double dada[] = new double[6];
688 while (!pi.isDone()) {
689 Arrays.fill(dada, 0);
690 int type = pi.currentSegment(dada);
691 System.out.println(type+":\t"+Arrays.toString(dada));
695 assert(findIntersection(0,0,90, 10,1,270+45)!=null);
696 assert(findIntersection(0,0,90, 1,1,89)!=null);
697 assert(findIntersection(0,0,90, 1,1,270+45)==null);
698 //System.out.println(findIntersection(0,0,270, 10,0,270));
699 //System.out.println(findIntersection(0,0,90, 10,-10,180));
701 Point2D cp1 = new Point2D.Double();
702 Point2D cp2 = new Point2D.Double();
703 int i = findNearestPoints(0, 0, 0, 1, 2, 10, 0, -1, cp1, cp2);
705 System.out.println(cp1+"\t"+cp2);
707 System.out.println("non posible");
710 double bezier[] = new double[] {100,1,102,1,105,1};
711 System.out.println(getLineLength(bezier, 2));
712 for (int i=0; i<=10; i++)
714 double t = ((double)i)/10;
715 System.out.println(GeometryUtils.getCompassDirection( getLineTangent(bezier, t) ));