QuadCurve2D

Ok, here's an applet demonstrating my solution. Say point p is given. What I'm doing basically is create a flattened PathIterator, iterate through it and take the distance between each point on the PathIterator and p. I arbitrarily chose the flatness of the PathIterator ... so maybe you have to adjust it.

The solution is not very elegant, but maybe it's helpful to you.

If someone knows a direct calculation of the closest point, let me know .....

Cheers, Tom

import java.awt.*;

import java.awt.geom.*;

import java.applet.*;

public class QuadCurveTest extends Applet {

Point2D.Double p0 = new Point2D.Double(100,100);

Point2D.Double p1 = new Point2D.Double(140,45);

Point2D.Double p2 = new Point2D.Double(285,90);

QuadCurve2D quad = new QuadCurve2D.Double(p0.x, p0.y, p1.x, p1.y, p2.x, p2.y);

Point2D.Double p = new Point2D.Double(200, 220);

public void init() {}

public void paint(Graphics g){

Graphics2D g2 = (Graphics2D)g;

drawPoint(p0, "start", g2);

drawPoint(p1, "control point", g2);

drawPoint(p2, "end", g2);

drawPoint(p, "p", g2);

g2.draw(quad);

Point2D closeP = closestPoint(quad, p, g2);

g2.setColor(Color.red);

drawPoint(closeP, "", g2);

g2.setColor(Color.green);

Line2D line = new Line2D.Double(p, closeP);

g2.draw(line);

}

public Point2D closestPoint (QuadCurve2D quad, Point2D.Double p, Graphics2D g2) {

PathIterator path = quad.getPathIterator(null, 0.005);

// 0.005 = the flatness; reduce if result is not accurate enough!

double[] coords = new double[2];

int counter = 0;

double x = 0.0, y = 0.0;

double px = p.x, py = p.y;

double closestX = 0.0;

double closestY = 0.0;

double closestDistanceSquare = 1000000.0;

while( !path.isDone() ) {

path.currentSegment(coords);

x = coords[0]; y = coords[1];

double distanceSquare = Point2D.distanceSq(x,y,px,py);

if (distanceSquare < closestDistanceSquare) {

closestDistanceSquare = distanceSquare;

closestX = x;

closestY = y;

}

path.next();

}

return new Point2D.Double(closestX, closestY);

}

private void drawPoint(Point2D p, String text, Graphics g) {

int x = (int)p.getX(),

y = (int)p.getY();

g.fillOval(x-2, y-2, 4, 4);

g.drawString(text, x-4, y+10);

}

static void p(String s) {

System.out.println(s);

}

}

Tom7 at 2007-7-1 19:37:48 >

An analytic approach leads to a 3rd degree polynomial, by the way.

All QuadCurve2D's can be transformed to segments of the unit parabola y = x^2 with an affine tranformation so it suffices to find p1(x1,y1) on the curve such that the distance from p1 to p2(x2,y2), a given point, is minimal.

The distance squared is d(x1,y1) = (x1-x2)^2+ (y1-y2)^2 = (x1-x2)^2+ (x1^2-y2)^2.

Taking the derivative gives d'(x1) = 2(x1-x2) + 2 (2 x1)(x1^2-y2) = 2x1 - 2x2 + 4x1^3 - 4x1y2

Solving for zeroes leads to 2x1^3 + (1 - 2 y2) x1 - x2 = 0 for the x coordinate of the point on the curve.

jsalonen at 2007-7-1 19:37:48 >