/*******************************************************************************
* Copyright (c) 2007, 2010 Association for Decentralized Information Management
* in Industry THTH ry.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* VTT Technical Research Centre of Finland - initial API and implementation
*******************************************************************************/
package org.simantics.g2d.utils;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
/**
* Path Utils.
*
* A line segment (linear, quadratic or cubic bezier) is described
* with a double array. The length of the array describes its degree (4,6,8).
* The first 2 elements define start point and last 2 the end point.
* Points in the middle are bezier control points.
*
* @author Toni Kalajainen
*/
public class PathUtils {
/**
* Get tangent of an bezier
* @param lineSegment bezier of n degrees
* @param degree 1..3
* @param t 0..1
* @return unit vector
*/
public static Point2D getLineTangent(double lineSegment[], double t)
{
int degree = getLineDegree(lineSegment);
double x=0, y=0;
if (degree==1)
{
x = lineSegment[2*1+0] - lineSegment[2*0+0];
y = lineSegment[2*1+1] - lineSegment[2*0+1];
} else {
if (degree==2) {
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]);
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]);
} else if (degree==3) {
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;
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;
}
}
return new Point2D.Double(x, y);
}
/**
*
* @param lineSegment
* @param t 0..1
* @return
*/
public static Point2D getLinePos(double lineSegment[], double t)
{
assert(lineSegment!=null);
int degree = getLineDegree(lineSegment);
double x=0, y=0;
if (degree==1) {
double p0x = lineSegment[0];
double p0y = lineSegment[1];
double p1x = lineSegment[2];
double p1y = lineSegment[3];
x = p0x*(1-t) + t*p1x;
y = p0y*(1-t) + t*p1y;
} else if (degree==2) {
double p0x = lineSegment[0];
double p0y = lineSegment[1];
double p1x = lineSegment[2];
double p1y = lineSegment[3];
double p2x = lineSegment[4];
double p2y = lineSegment[5];
double c2x = p0x-2*p1x+p2x;
double c2y = p0y-2*p1y+p2y;
double c1x = -2*p0x+2*p1x;
double c1y = -2*p0y+2*p1y;
double c0x = p0x;
double c0y = p0y;
x = t*t*c2x+t*c1x+c0x;
y = t*t*c2y+t*c1y+c0y;
} else if (degree==3) {
double p0x = lineSegment[0];
double p0y = lineSegment[1];
double p1x = lineSegment[2];
double p1y = lineSegment[3];
double p2x = lineSegment[4];
double p2y = lineSegment[5];
double p3x = lineSegment[6];
double p3y = lineSegment[7];
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;
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;
}
return new Point2D.Double(x, y);
}
public static double getLineLength(double lineSegment[])
{
int degree = getLineDegree(lineSegment);
if (degree==1) {
double dx = lineSegment[2]-lineSegment[0];
double dy = lineSegment[3]-lineSegment[1];
return Math.sqrt(dx*dx+dy*dy);
}
// Quick'n'dirty approximation
// TODO Replace with accurate value
double result = 0;
Point2D prevPos = getLinePos(lineSegment, 0.0);
for (int i=0; i<10; i++)
{
double t = (double)(i+1)/10;
Point2D pos = getLinePos(lineSegment, t);
result += pos.distance(prevPos);
prevPos.setLocation(pos);
}
return result;
/*
if (degree==2) {
double c2x = bezier[2*0+0]-2*bezier[2*1+0]+bezier[2*2+0];
double c2y = bezier[2*0+1]-2*bezier[2*1+1]+bezier[2*2+1];
double c1x = -2*bezier[2*0+0]+2*bezier[2*1+0];
double c1y = -2*bezier[2*0+1]+2*bezier[2*1+1];
double c0x = bezier[2*0+0];
double c0y = bezier[2*0+1];
double intg_x = c2x/3 + c1x/2 + c0x;
double intg_y = c2y/3 + c1y/2 + c0y;
System.out.println(intg_x +"\t" + intg_y);
return intg_x + intg_y;
}
return 0;
*/
}
public static int getLineDegree(double lineSegment[])
{
assert(lineSegment.length==4 || lineSegment.length==6 || lineSegment.length==8);
return (lineSegment.length-2)/2;
}
/**
* Get first and last point & tangent of a path
* @param path
* @param begin
* @param beginDirection
* @param end
* @param endDirection
* @return true if pi contained atleast one line segment
*/
public static boolean getPathArrows(PathIterator pi, Point2D begin, Point2D beginDirection, Point2D end, Point2D endDirection)
{
Iterator i = toLineIterator(pi);
double first[]=null, last[]=null;
while (i.hasNext()) {
double[] current = i.next();
if (first==null) first = current;
if (!i.hasNext()) last = current;
}
if (first==null || last==null) return false;
begin.setLocation( getLinePos(first, 0) );
beginDirection.setLocation( getLineTangent(first, 0) );
end.setLocation( getLinePos(last, 1) );
Point2D endTangent = getLineTangent(last, 1);
endDirection.setLocation( -endTangent.getX(), -endTangent.getY() );
return true;
}
/**
* Interpolate two paths
* @param path1
* @param path2
* @param t phase 0..1, 0==path1, 1==path2
* @return
*/
public static Path2D interpolatePaths(PathIterator path1, PathIterator path2, double t)
{
Path2D result = new Path2D.Double();
ArrayList l1 = new ArrayList();
toLineSegments(path1, l1);
ArrayList l2 = new ArrayList();
toLineSegments(path2, l2);
if (l1.size()==l2.size())
{
}
result.append(path1, false);
return result;
}
public static double[] interpolateLineSegment(double l1[], double l2[], double t)
{
assert(t>=0 && t<=1);
if (t==0) return Arrays.copyOf(l1, l1.length);
if (t==1) return Arrays.copyOf(l1, l1.length);
int d1 = getLineDegree(l1);
int d2 = getLineDegree(l2);
if (d1==d2) {
double result [] = new double[l1.length];
for (int i=0; i toLineIterator(final PathIterator pi)
{
return new PathIteratorToSegmentIterator(pi);
}
public static void toLineSegments(PathIterator pi, Collection result)
{
Iterator i = toLineIterator(pi);
while (i.hasNext()) {
double[] segment = i.next();
result.add(segment);
}
}
private static class PathIteratorToSegmentIterator implements Iterator
{
final PathIterator pi;
double lineTo[] = new double[6];
double startPos[] = new double[2];
double from[] = new double[2];
int degree = 0;
PathIteratorToSegmentIterator(PathIterator pi) {
this.pi = pi;
while(!pi.isDone()) {
int type = pi.currentSegment(lineTo);
pi.next();
if (type == PathIterator.SEG_MOVETO) {
startPos[0] = from[0] = lineTo[0];
startPos[1] = from[1] = lineTo[1];
}
if (type == PathIterator.SEG_CLOSE) {
type = PathIterator.SEG_LINETO;
lineTo[0] = startPos[0];
lineTo[1] = startPos[1];
}
if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)
{
degree = type;
// from == xx
break;
}
}
}
@Override
public boolean hasNext() {
return degree>0;
}
@Override
public double[] next() {
if (degree==0) return null;
double result[] = new double[degree*2+2];
result[0] = from[0];
result[1] = from[1];
result[2] = lineTo[0];
result[3] = lineTo[1];
if (degree==2) {
result[4] = lineTo[2];
result[5] = lineTo[3];
} else if (degree==3) {
result[6] = lineTo[4];
result[7] = lineTo[5];
}
// traverse path iterator until end or until next segment is known
degree = 0;
from[0] = lineTo[0];
from[1] = lineTo[1];
while(!pi.isDone()) {
int type = pi.currentSegment(lineTo);
pi.next();
if (type == PathIterator.SEG_MOVETO) {
startPos[0] = from[0] = lineTo[0];
startPos[1] = from[1] = lineTo[1];
}
if (type == PathIterator.SEG_CLOSE) {
type = PathIterator.SEG_LINETO;
lineTo[0] = startPos[0];
lineTo[1] = startPos[1];
}
if (type>=PathIterator.SEG_LINETO && type<=PathIterator.SEG_CUBICTO)
{
degree = type;
break;
}
}
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
/**
* Finds intersection of two half-straight lines
* @param p0x
* @param p0y
* @param dir0
* @param p1x
* @param p1y
* @param dir1
* @return
*/
public static Point2D findIntersection(double p0x, double p0y, double dir0, double p1x, double p1y, double dir1)
{
Point2D uv = new Point2D.Double();
GeometryUtils.toUnitVector(dir0, uv);
double v0x = uv.getX();
double v0y = uv.getY();
GeometryUtils.toUnitVector(dir1, uv);
double v1x = uv.getX();
double v1y = uv.getY();
return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);
}
/**
* Finds intersection of two half-straight lines
* @param p0
* @param v0
* @param p1
* @param v1
* @return
*/
public static Point2D findIntersection(Point2D p0, Point2D v0, Point2D p1, Point2D v1)
{
double v0x = v0.getX();
double v0y = v0.getY();
double v1x = v1.getX();
double v1y = v1.getY();
double p0x = p0.getX();
double p0y = p0.getY();
double p1x = p1.getX();
double p1y = p1.getY();
return findIntersection(p0x, p0y, v0x, v0y, p1x, p1y, v1x, v1y);
}
/**
* Finds intersection of two half-straight lines
* @param p1
* @param v1 direction vector (unit vector)
* @param p2
* @param v2 direction vector (unit vector)
* @return
*/
public static Point2D findIntersection(double p0x, double p0y, double v0x, double v0y, double p1x, double p1y, double v1x, double v1y)
{
if (p0x==p1x && p0y==p1y) return new Point2D.Double(p0x, p0y);
/*
i = Intersection point
i = p0 + t*v0 = p1 + r*v1;
*/
double denominator = v0y*v1x - v0x*v1y;
// Straights are in same or opposite directions
if (denominator == 0) {
return null;
/*
// Do they overlap?
boolean overlap = v0x*(p1y-p0y) - v0y*(p1x-p1x) == 0;
if (!overlap) return null;
double t = v1x==0?(p1y-p0y)/v0y:(p1x-p0x)/v0x;
double r = v0x==0?(p0y-p1y)/v1y:(p0x-p1x)/v1x;
boolean parallel = (v0x==v1x)&&(v0y==v1y);
if (parallel) {
if (t<0) return new Point2D.Double(p1x, p1y);
if (r<0) return new Point2D.Double(p0x, p0y);
return null;
}
return null;
*/
}
double nominator = -v0x*p0y + v0x*p1y + v0y*p0x - v0y*p1x;
double r = nominator / denominator;
if (r<0) return null;
// XXX t on väärin
//double t = -p0x + p1x + v1x*r;
//if (t<0) return null;
double x = p1x + r*v1x;
double y = p1y + r*v1y;
return new Point2D.Double(x, y);
}
public static int findNearestPoints(Point2D p0, Point2D v0, Point2D p1, Point2D v1, Point2D cp1, Point2D cp2)
{
return findNearestPoints(p0.getX(), p0.getY(), v0.getX(), v0.getY(), p1.getX(), p1.getY(), v1.getX(), v1.getY(), cp1, cp2);
}
public static int findNearestPoints(double p0x, double p0y, double v0x, double v0y, double p1x, double p1y, double v1x, double v1y, Point2D cp1, Point2D cp2)
{
int result = 0;
double r = -( v1x*(p1x-p0x) + v1y*(p1y-p0y) ) / (v1x*v1x+v1y*v1y);
double t = -( v0x*(p0x-p1x) + v0y*(p0y-p1y) ) / (v0x*v0x+v0y*v0y);
if (t>0) {
cp1.setLocation( p0x + v0x*t, p0y + v0y*t );
result |= 1;
}
if (r>0) {
cp2.setLocation( p1x + v1x*r, p1y + v1y*r );
result |= 2;
}
return result;
}
public static double[] subdiv_takeLeft(double line[], double t)
{
int degree = getLineDegree(line);
double p0x = line[0];
double p0y = line[1];
double p1x = line[2];
double p1y = line[3];
double p1x_ = p0x*(1-t) + p1x*t;
double p1y_ = p0y*(1-t) + p1y*t;
if (degree==1)
return new double[] {p0x, p0y, p1x_, p1y_};
double p2x = line[4];
double p2y = line[5];
double q0x = p0x*(1-t) + p1x*t;
double q0y = p0y*(1-t) + p1y*t;
double q1x = p1x*(1-t) + p2x*t;
double q1y = p1y*(1-t) + p2y*t;
double p2x_ = q0x*(1-t) + q1x*t;
double p2y_ = q0y*(1-t) + q1y*t;
if (degree==2)
return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_};
double p3x = line[6];
double p3y = line[7];
double q2x = p2x*(1-t) + p3x*t;
double q2y = p2y*(1-t) + p3y*t;
double r0x = q0x*(1-t) + q1x*t;
double r0y = q0y*(1-t) + q1y*t;
double r1x = q1x*(1-t) + q2x*t;
double r1y = q1y*(1-t) + q2y*t;
double p3x_ = r0x*(1-t) + r1x*t;
double p3y_ = r0y*(1-t) + r1y*t;
if (degree==3)
return new double[] {p0x, p0y, p1x_, p1y_, p2x_, p2y_, p3x_, p3y_};
return null;
}
public static double[] subdiv_takeRight(double line[], double t)
{
int degree = getLineDegree(line);
double p0x = line[0];
double p0y = line[1];
double p1x = line[2];
double p1y = line[3];
double p0x_ = p0x*(1-t) + p1x*t;
double p0y_ = p0y*(1-t) + p1y*t;
if (degree==1)
return new double[] {p0x_, p0y_, p1x, p1y};
double p2x = line[4];
double p2y = line[5];
double q0x = p0x*(1-t) + p1x*t;
double q0y = p0y*(1-t) + p1y*t;
double q1x = p1x*(1-t) + p2x*t;
double q1y = p1y*(1-t) + p2y*t;
double p2x_ = q0x*(1-t) + q1x*t;
double p2y_ = q0y*(1-t) + q1y*t;
if (degree==2)
return new double[] {p2x_, p2y_, q1x, q1y, p2x, p2y};
double p3x = line[6];
double p3y = line[7];
double q2x = p2x*(1-t) + p3x*t;
double q2y = p2y*(1-t) + p3y*t;
double r0x = q0x*(1-t) + q1x*t;
double r0y = q0y*(1-t) + q1y*t;
double r1x = q1x*(1-t) + q2x*t;
double r1y = q1y*(1-t) + q2y*t;
double p3x_ = r0x*(1-t) + r1x*t;
double p3y_ = r0y*(1-t) + r1y*t;
if (degree==3)
return new double[] {p3x_, p3y_, r1x, r1y, q2x, q2y, p3x, p3y};
return null;
}
/**
* Crops line segment into a smaller line segment
* @param line line segment
* @param t0 begin t
* @param t1 end t
* @return cropped line segment
*/
public static double[] cropLine(double line[], double t0, double t1)
{
double temp[] = subdiv_takeLeft(line, t1);
return subdiv_takeRight(temp, t0/t1);
}
@SuppressWarnings("unused")
private static Point2D interpolateLine(double x0, double y0, double x1, double y1, double t)
{
double x = (x1-x0)*t + x0;
double y = (y1-y0)*t + y0;
return new Point2D.Double(x, y);
}
public static Path2D toPath(double lineSegment[])
{
int degree = getLineDegree(lineSegment);
Path2D p = new Path2D.Double();
p.moveTo(lineSegment[0], lineSegment[1]);
if (degree==1)
p.lineTo(lineSegment[2], lineSegment[3]);
if (degree==2)
p.quadTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5]);
if (degree==3)
p.curveTo(lineSegment[2], lineSegment[3], lineSegment[4], lineSegment[5], lineSegment[6], lineSegment[7]);
return p;
}
public static Path2D path(double ... pos)
{
assert(pos.length%2==0 && pos.length>=4);
Path2D p = new Path2D.Double();
p.moveTo(pos[0], pos[1]);
for (int i=1; i=4);
// Path2D p = new Path2D.Double();
// p.moveTo(pos[0], pos[1]);
// for (int i=1; i0)
System.out.println(cp1+"\t"+cp2);
else
System.out.println("non posible");
*/
/*
double bezier[] = new double[] {100,1,102,1,105,1};
System.out.println(getLineLength(bezier, 2));
for (int i=0; i<=10; i++)
{
double t = ((double)i)/10;
System.out.println(GeometryUtils.getCompassDirection( getLineTangent(bezier, t) ));
}*/
}
}