finding closest point
Yundi Li, Daniel
Greenhorn
Posts: 26
posted 14 years ago
i wanna implement a operation that calculate a closest point to a Line from one point.
the signature of the operation should be
public Point getClosestPoint(Point p1, Point p2, Point target);
the point 1 and point 2 form a line , the method should return a point on the line that is closest to the target.
I just use some stupid method to do that.
Anyone have smart algoirthem or method to do it ?
Thanks for your help
the signature of the operation should be
public Point getClosestPoint(Point p1, Point p2, Point target);
the point 1 and point 2 form a line , the method should return a point on the line that is closest to the target.
I just use some stupid method to do that.
Anyone have smart algoirthem or method to do it ?
Thanks for your help
karl koch
Ranch Hand
Posts: 388
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
posted 14 years ago
That's java.awt.geom. The Line2D class has a method ptLineDist() which seems like what you want  assuming you are talking about points in 2D.
I just use some stupid method to do that.
So what is the method you're using? And what exactly is the problem with it?
I just use some stupid method to do that.
So what is the method you're using? And what exactly is the problem with it?
"I'm not back."  Bill Harding, Twister
Erik Pragt
Ranch Hand
Posts: 125
posted 14 years ago
I've taken the liberty to draw your method (with pencil), and the things I see are two ([edit] I mean three[/edit]) triangles. You might use pythagoras to calculate the closest point. I don't know if it's the best solution, but what I do know is that it works.
If I need to explain myself a little clearer, let me know.
Erik
[ January 23, 2003: Message edited by: Erik Pragt ]
If I need to explain myself a little clearer, let me know.
Erik
[ January 23, 2003: Message edited by: Erik Pragt ]
Anonymous
Ranch Hand
Posts: 18944
posted 14 years ago
Given those two points that span a line, it's quite easy to find the equation of that line:
L: ax+by = c
where x and y are the two unknowns and (a, b) is a vector orthogonal to line L.
Given the target point (p, q), the following vector equation describes a line through the target point, orthogonal to line L:
M': (p, q)+lambda*(a, b)
This vector equation can be transformed to a linear equation:
M: bx+ay = aqbp
Now you have to linear equations (L and M) and two unknowns. This is easy to solve ...
kind regards
L: ax+by = c
where x and y are the two unknowns and (a, b) is a vector orthogonal to line L.
Given the target point (p, q), the following vector equation describes a line through the target point, orthogonal to line L:
M': (p, q)+lambda*(a, b)
This vector equation can be transformed to a linear equation:
M: bx+ay = aqbp
Now you have to linear equations (L and M) and two unknowns. This is easy to solve ...
kind regards
David Weitzman
Ranch Hand
Posts: 1365
posted 14 years ago
I've gone a step further and come up with a more concrete result. Hell, it's more fun than homework (what kind of freak am I?). Hopefully I didn't make too many mistakes.
I'll call A and B the points that define the line and P will be the point off of it.
The slope of the line, M, equals (ByAy)/(BxAx)
I did a bit of algebra and matrix multiplication and stuff to get this result:
x = (M^2 * Ax  M * (Ay  Py) + Px)/(M^2 + 1)
y = (M^2 * Py  M * (Ax  Px) + Ay)/(M^2 + 1)
So who wants to verify my answer?
I guess if I want full credit I have to show my work.
I'll call A and B the points that define the line and P will be the point off of it.
The slope of the line, M, equals (ByAy)/(BxAx)
I did a bit of algebra and matrix multiplication and stuff to get this result:
x = (M^2 * Ax  M * (Ay  Py) + Px)/(M^2 + 1)
y = (M^2 * Py  M * (Ax  Px) + Ay)/(M^2 + 1)
So who wants to verify my answer?
I guess if I want full credit I have to show my work.
Yundi Li, Daniel
Greenhorn
Posts: 26
posted 14 years ago
Thanks all of you.
I got a fast solution.
Let me share my stupid method first.
this method sucks, i just directly use a loop to search for the closing distance between the line and a point and then return this point
private static Point getClosestPoint(Point pt1, Point pt2, Point p)
{
Point p1, p2;
if(pt1.x>pt2.x)
{
p1 = pt1;
p2 = pt2;
}
else
{
p1 = pt2;
p2 = pt1;
}
Point pt = new Point();
Line2D l = new Line2D.Double();
l.setLine(p1,p2);
pt.y = (int)(getSlope(p1,p2)*(p1.xp2.x)+p2.y);
pt.x = (int)((pt.yp2.y)/getSlope(p1, p2)+p2.x);
double distance = p.distance(pt);
for(double x = p1.x+1; x<p2.x ; x=x+1d)
{
pt.y = (int)(getSlope(p1,p2)*(double)(x(double)p2.x)+(double)p2.y);
pt.x = (int)((pt.yp2.y)/getSlope(p1, p2)+p2.x);
if(p.distance(pt)>distance){
pt.y = pt.y1;
pt.x = pt.x 1;
break;
}
else
distance = p.distance(pt);
}
return pt;
}
private static double getSlope(Point p1, Point p2)
{
Rectangle rect = new Rectangle(p1);
rect.add(p2);
return(double)(rect.height/rect.width);
}
I got a fast solution.
Let me share my stupid method first.
this method sucks, i just directly use a loop to search for the closing distance between the line and a point and then return this point
private static Point getClosestPoint(Point pt1, Point pt2, Point p)
{
Point p1, p2;
if(pt1.x>pt2.x)
{
p1 = pt1;
p2 = pt2;
}
else
{
p1 = pt2;
p2 = pt1;
}
Point pt = new Point();
Line2D l = new Line2D.Double();
l.setLine(p1,p2);
pt.y = (int)(getSlope(p1,p2)*(p1.xp2.x)+p2.y);
pt.x = (int)((pt.yp2.y)/getSlope(p1, p2)+p2.x);
double distance = p.distance(pt);
for(double x = p1.x+1; x<p2.x ; x=x+1d)
{
pt.y = (int)(getSlope(p1,p2)*(double)(x(double)p2.x)+(double)p2.y);
pt.x = (int)((pt.yp2.y)/getSlope(p1, p2)+p2.x);
if(p.distance(pt)>distance){
pt.y = pt.y1;
pt.x = pt.x 1;
break;
}
else
distance = p.distance(pt);
}
return pt;
}
private static double getSlope(Point p1, Point p2)
{
Rectangle rect = new Rectangle(p1);
rect.add(p2);
return(double)(rect.height/rect.width);
}
Yundi Li, Daniel
Greenhorn
Posts: 26
posted 14 years ago
And this is the correct fast solution.
Using the fact that the line defined by 'pt1' and 'pt2' must be orthogonal to the line defined by 'p' and the target point then this is my solution
private static Point myGetClosestPoint(Point pt1, Point pt2, Point p)
{
double u = ((p.xpt1.x)*(pt2.xpt1.x)+(p.ypt1.y)*(pt2.ypt1.y))/(sqr(pt2.xpt1.x)+sqr(pt2.ypt1.y));
if (u > 1.0)
return (Point)pt2.clone();
else if (u <= 0.0)
return (Point)pt1.clone();
else
return new Point((int)(pt2.x*u+pt1.x*(1.0u)+0.5), (int)(pt2.y*u+pt1.y*(1.0u)+0.5));
}
private static double sqr(double x)
{
return x*x;
}
Using the fact that the line defined by 'pt1' and 'pt2' must be orthogonal to the line defined by 'p' and the target point then this is my solution
private static Point myGetClosestPoint(Point pt1, Point pt2, Point p)
{
double u = ((p.xpt1.x)*(pt2.xpt1.x)+(p.ypt1.y)*(pt2.ypt1.y))/(sqr(pt2.xpt1.x)+sqr(pt2.ypt1.y));
if (u > 1.0)
return (Point)pt2.clone();
else if (u <= 0.0)
return (Point)pt1.clone();
else
return new Point((int)(pt2.x*u+pt1.x*(1.0u)+0.5), (int)(pt2.y*u+pt1.y*(1.0u)+0.5));
}
private static double sqr(double x)
{
return x*x;
}
Yundi Li, Daniel
Greenhorn
Posts: 26
posted 14 years ago
A demo program written by Roger
mport java.awt.*;
import javax.swing.*;
public class Test101 extends JFrame
{
public Test101()
{
super("Test 101");
this.getContentPane().setLayout(new BorderLayout());
MyCanvas canvas = new MyCanvas();
this.getContentPane().add(canvas, BorderLayout.CENTER);
this.setSize(700, 700);
}
class MyCanvas extends JPanel
{
Point pt1 = new Point(10, 20);
Point pt2 = new Point(200, 400);
double r = 300;
public void paintComponent(Graphics g)
{
g.translate(200, 100);
g.setColor(Color.red);
g.drawLine(pt1.x, pt1.y, pt2.x, pt2.y);
g.setColor(Color.blue);
for (double theta = 0.0; theta <2.0*Math.PI; theta += 0.11)
{
Point p = new Point((int)(Math.sin(theta)*r+0.5)+100, (int)(Math.cos(theta)*r+0.5)+200);
Point q = myGetClosestPoint(pt2, pt1, p);
g.drawLine(q.x, q.y, p.x, p.y);
}
}
}
public static void main(String[] args)
{
new Test101().setVisible(true);
}
private static Point myGetClosestPoint(Point pt1, Point pt2, Point p)
{
double u = ((p.xpt1.x)*(pt2.xpt1.x)+(p.ypt1.y)*(pt2.ypt1.y))/(sqr(pt2.xpt1.x)+sqr(pt2.ypt1.y));
if (u > 1.0)
return (Point)pt2.clone();
else if (u <= 0.0)
return (Point)pt1.clone();
else
return new Point((int)(pt2.x*u+pt1.x*(1.0u)+0.5), (int)(pt2.y*u+pt1.y*(1.0u)+0.5));
}
private static double sqr(double x)
{
return x*x;
}
}
mport java.awt.*;
import javax.swing.*;
public class Test101 extends JFrame
{
public Test101()
{
super("Test 101");
this.getContentPane().setLayout(new BorderLayout());
MyCanvas canvas = new MyCanvas();
this.getContentPane().add(canvas, BorderLayout.CENTER);
this.setSize(700, 700);
}
class MyCanvas extends JPanel
{
Point pt1 = new Point(10, 20);
Point pt2 = new Point(200, 400);
double r = 300;
public void paintComponent(Graphics g)
{
g.translate(200, 100);
g.setColor(Color.red);
g.drawLine(pt1.x, pt1.y, pt2.x, pt2.y);
g.setColor(Color.blue);
for (double theta = 0.0; theta <2.0*Math.PI; theta += 0.11)
{
Point p = new Point((int)(Math.sin(theta)*r+0.5)+100, (int)(Math.cos(theta)*r+0.5)+200);
Point q = myGetClosestPoint(pt2, pt1, p);
g.drawLine(q.x, q.y, p.x, p.y);
}
}
}
public static void main(String[] args)
{
new Test101().setVisible(true);
}
private static Point myGetClosestPoint(Point pt1, Point pt2, Point p)
{
double u = ((p.xpt1.x)*(pt2.xpt1.x)+(p.ypt1.y)*(pt2.ypt1.y))/(sqr(pt2.xpt1.x)+sqr(pt2.ypt1.y));
if (u > 1.0)
return (Point)pt2.clone();
else if (u <= 0.0)
return (Point)pt1.clone();
else
return new Point((int)(pt2.x*u+pt1.x*(1.0u)+0.5), (int)(pt2.y*u+pt1.y*(1.0u)+0.5));
}
private static double sqr(double x)
{
return x*x;
}
}
David Weitzman
Ranch Hand
Posts: 1365
posted 14 years ago
My version and your version both appear to work. (They're both also quite cryptic without explanation. I'd guess from the 0 and 1 comparson that your method is based on trig, but I don't want to bother resolving the problem with the law of cosines). Here's the code I used to examine them:
Anonymous
Ranch Hand
Posts: 18944
posted 14 years ago
No, these 0, 1 comparisons have to do with the following: the line through points A and B is represented by the following vecor equation:
L: (Bx, By)+u*((AxBx, AyBy)
if u < 0 then the intersection does not really exist (the line starts at B and ends at A) because it lies 'on the other side' of point A. similar, if u > 1 the point lies 'on the other side of point B. So, if u < 0, u is set to 0 and point B is chosen, otherwise if u > 1, u is set to 1 and point A is chosen, otherwise the calculation of L (see above) is performed. If the line L were thought of as being infinite, both comparisons could be removed.
kind regards
Originally posted by David Weitzman:
My version and your version both appear to work. (They're both also quite cryptic without explanation. I'd guess from the 0 and 1 comparson that your method is based on trig, but I don't want to bother resolving the problem with the law of cosines).
No, these 0, 1 comparisons have to do with the following: the line through points A and B is represented by the following vecor equation:
L: (Bx, By)+u*((AxBx, AyBy)
if u < 0 then the intersection does not really exist (the line starts at B and ends at A) because it lies 'on the other side' of point A. similar, if u > 1 the point lies 'on the other side of point B. So, if u < 0, u is set to 0 and point B is chosen, otherwise if u > 1, u is set to 1 and point A is chosen, otherwise the calculation of L (see above) is performed. If the line L were thought of as being infinite, both comparisons could be removed.
kind regards
David Weitzman
Ranch Hand
Posts: 1365
posted 14 years ago
That's pretty clever. So
equals (by rearrangement)
The two solutions seem to have roughly the same number of operations performed (although performance isn't an issue for this method) but in mine you'd have to check that (x,y) was on the segment afterwards.
If (x < min(Ax, Bx)) x = min(Ax, Bx);
If (x > max(Ax, Bx)) x = max(Ax, Bx);
// etc.
I don't write scientific or mathmatical stuff often, but if I ever become a game programmer I think I'll aim to overcomment. Or should proofs and derivations go in a seperate documentation file, fully referenced in the source? But that's a topic for a rainy day.
Added to my TODO list: Get a book on computational geometry.
equals (by rearrangement)
The two solutions seem to have roughly the same number of operations performed (although performance isn't an issue for this method) but in mine you'd have to check that (x,y) was on the segment afterwards.
If (x < min(Ax, Bx)) x = min(Ax, Bx);
If (x > max(Ax, Bx)) x = max(Ax, Bx);
// etc.
I don't write scientific or mathmatical stuff often, but if I ever become a game programmer I think I'll aim to overcomment. Or should proofs and derivations go in a seperate documentation file, fully referenced in the source? But that's a topic for a rainy day.
Added to my TODO list: Get a book on computational geometry.
Jim Yingst
Wanderer
Sheriff
Sheriff
Posts: 18671
John Lee
Ranch Hand
Posts: 2545
posted 14 years ago
I think this is a middle school Geometry problem. I am glad it is still useful in Java.
What are you doing? You are supposed to be reading this tiny ad!
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
