This might fit in Computer Science, but its mostly geometry, so I figured i'd put it here. If it belongs somewhere else, sorry.

Here's the situation. I have a box which is defined by 4 x,y pairs. I also have an origin which is another x,y pair. You're guarenteed that the origin is not inside the box. I need to find what point on the box is closest to the origin. Is there a way to do that? I mean i could find random points around the box and find distances to see which is closest and work from there, but it seems there should be an easier way.

-AntonK

Here's a picture to explain it further...

I guess you mean a 2 dimensional box rather than a 3D one, and I assume the corners are the (x,y) pairs you're talking about. Is that right?

I suspect that the following might work. Find the corner closest to the origin. This narrows your search to two sides. Of the two possible corners, use the one closer to the origin as the other end of the side you will search. Set up the equation of the line joining those corners. Use the equation to binary search along that side for the closest point.

I think the it is likely that a corner is the closest point. The method I suggested in previous post should include logic to check for the closest corner being the closest point. If not, then start the binary search.

James R.: Yes, just as you have assumed.

Dinosaur: The only problem I see with a binary search is that it assumes we are working with discrete points. If I introduce a continous number system, that makes it quite difficult. Any ideas how how do deal with this? Also, may i ask why you think that it will be a corner?

-AntonK

If you have co-ordinates can't you use simple trigonometry to find out?

I'm not trying to outsmart you Antonk, I would just like to clarify the situation to help solve your problem. If the box is two dimensional then how can there be 4 x, y pairs? I assume there are two pairs on axis x and two pairs on axis y?

Originally posted by BillClintonsCigar
I'm not trying to outsmart you Antonk, I would just like to clarify the situation to help solve your problem. If the box is two dimensional then how can there be 4 x, y pairs? I assume there are two pairs on axis x and two pairs on axis y?

In a 2-dimensional system they all have one X coordinate and one Y coordinate :)

And oh, I think he meant X and Y as a pair not a pair of coordinates.

Just use what you know of trigonometry to show that Hypotenuse A is shorter than B and you will have proved that one of them is closer.

dX^2 + dY^2 = Hypotenuse^2

This all I know. Its very simply to compute which of the 4 corners of the box is closest of course. What I need to know is if any of the points ON the box, including any corner or any point on the sides of the box. Since a box is made up of 4 line segments there are infinite number of points (because of course, wherever you have 2 points on a line segment, you can always go halfway between them and have a new point).

What I meant by an x,y pair was a single point is represented on a coordinate system with its X value and its Y value (this is what I'm calling an x,y pair). 4 points make a box. Thats why I said the box is made of 4 x,y pairs. BUT, call it whatever you want. I need a way to find one which point which exists on the box (one of the four line segments) is closest to the origin point.

-AntonK

Let Z (Xo,Yo) be the orgin.

Find out the nearest corner N1 : (X1,Y1) and next nearest corner N2 : (X2,Y2).

Let P be the point (Xn,Yn) which could be obtained by
solving line equations of N1N2 and ZP, (note that ZP is perpendicular to N1N2 or its extension), where the slope of ZP is -ve inverse of slope of N1N2 that you know and apply appropriate offsets to line equations for the N1N2 & ZP.

If the P is on line segment N1N2 then P is the nearest point. P is outside of N1N2 line segment then N1 is the nearest point.

Edit : assumed the box is a square. even if it is not square, for finding the next nearest corner N2 imagine a square with lesser side of the rectangle as equal sides of that imaginary square. for our purpose that does not matter.

I think I understand what you're saying here... IF i understand what you mean, I think it may work. Do you think you can edit the drawing i put up and repost it? Thanks

-AntonK

As an algorithm,

1. ignore the fact that you have a box, you are only interested in lines, the nearest line which has 2 points.

2. test wether a point is the nearest to the origin, alot of time a point will be the nearest.
with your drawing in mind,
IF (x1 AND x2) OR (y1 AND y2) are greater than the origin then a point will be closest. if it's less than the origin then the origin would be in the box in your drawing.
It depends on wether the gradient is +ve or -ve and which side of the origen the nearest line is.
For instance if you mirrored your drawing the IF statement above would show a point to be closest IF (x1 AND x2) OR (y1 AND y2) are less than the origin then a point will be closest.
If you find that a point is closest this way you won't have to do any math.

3. If a point isn't closest then find the equation of the line and the equation of the NORMAL to the line. these are vectors so now you have 2 line equations with 2 points that the lines pass throung, x1,y1 pass through the line and Ox,Oy pass through the normal.
Now find out where the lines intersect. cramer's rule. or any other method.

Do a set of drawings with lots of points and figure out the correct algorithm for any case.

Modified your diagram. ABCD is the box. First nearest corner of Orgin is A and next nearest corner is D. Orgin intersects the line contains AD at P perpendicularly. You know the slopes of both lines. solving the line equations you can findout P. in this case P is lying outside the line segment AD. So the nearest point is A.

Z1,Z2,Z3 are different positions of orgin and they all have P within the respective line segments formed by their first and next nearest corners respectively. respective P's are the nearest points for Z1,Z2,Z3.

everneo: You are completely right. The more I look at it, the more I'm sure your way works. The picture definately cleared it up. Thank you so much. Now to code it. Thanks again!!

-AntonK

you're welcome and thanks for the interesting post.