Sign in to follow this  
dEgle95

Distance to ray intersection

Recommended Posts

dEgle95    131
Hello guys!
I'm having such a problem: i can't figure easiest way to find distance between point and block (as shown on picture)
[img]https://p.twimg.com/AqhSb2nCQAAMY57.png[/img]
Everything that i tried is not properly working [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img]
Could you help me please and tell way to find that distance.

Share this post


Link to post
Share on other sites
JTippetts    12950
Consider that the box is formed by the points A,B,C,D

A B
C D

From these points, you can obtain the equations of the lines forming the edges of the box: A->B, C->D, A->C, B->D. Recall that the parametric form of a line can be expressed as:
[code]
P=P1+u*(P2-P1)
[/code]
for any 2 points, P1 and P2, on a line. This means that any point along the line can be expressed in terms of the parameter, u. A value of u=0 evaluates to P1 on the line, a value of u=1 evaluates to P2 on the line, and values of u in between 0 and 1 evaluate to points on the linesegment described by P1 and P2. Values of u less than 0 or greater than 1 evaluate to points beyond the ends of the line segment.

For a given point, P, you can find the value of u that corresponds to the closest point on the line, P1->P2, by:
[code]

u=((P.x-P1.x)*(P2.x-P1.x) + (P.y-P1.y)*(P2.y-P1.y)) / length(P2-P1)^2
[/code]

In essence, you project the point, P, onto the line. You calculate the dotproduct of the vectors P1->P and P1->P2, and divide this dot product by the length of P1->P2 squared.

This will obtain the value of u for that particular line that denotes the point on the line nearest to P. Since you are testing for distance to a box made of line segments, then you have to account for the fact that this nearest point might not lie on the box. In this case, you can simple clamp the value of u to the range [0,1]. If u is less than zero, then the closest point on that line segment to P is the point P1. If us is greater than 1, then the closest point is P2.

Once u is clamped, you can plug it into the parametric form of the line being tested, to find out the actual coordinates of the point. Perform this test for all four of the line segments forming the box, then calculate the distances between P and the closest points, returning the smallest of these four distances as the result.

Some sample Lua code is as follows:
[code]

function closestPointOnLineU(p, p1, p2)
local length=math.sqrt((p2.x-p1.x)*(p2.x-p1.x) + (p2.y-p1.y)*(p2.y-p1.y))
return ((p.x-p1.x)*(p2.x-p1.x) + (p.y-p1.y)*(p2.y-p1.y)) / (length*length)
end

function closestPointOnLineSegment(p, p1, p2)
local u=closestPointOnLineU(p,p1,p2)
u=math.max(0, math.min(1, u))
return {x=p1.x+u*(p2.x-p1.x), y=p1.y+u*(p2.y-p1.y)}
end

function distanceToLineSegment(p, p1, p2)
local closest=closestPointOnLineSegment(p,p1,p2)
return math.sqrt((p.x-closest.x)*(p.x-closest.x) + (p.y-closest.y)*(p.y-closest.y))
end

function distanceToBox(p, A, B, C, D)
local d1=distanceToLineSegment(p, A, B)
local d2=distanceToLineSegment(p, C, D)
local d3=distanceToLineSegment(p, A, C)
local d4=distanceToLineSegment(p, B, D)
return math.min(d1,d2,d3,d4)
end

[/code] Note that it's quick code, so I might have made an error somewhere, but initial tests indicate it works.

Share this post


Link to post
Share on other sites
alvaro    21247
Here's some C++ code for you:
[code]float distance_point_to_box(float x, float y,
float min_x, float min_y,
float max_x, float max_y) {
float dx = x < min_x ? x - min_x : x < max_x ? 0.0f : max_x - x;
float dy = y < min_y ? y - min_y : y < max_y ? 0.0f : max_y - y;
return std::sqrt(dx * dx + dy * dy);
}
[/code]

Share this post


Link to post
Share on other sites
JTippetts    12950
Heh, yeah, alvaro's code is the way to go if your boxes are axis-aligned. The algorithm I presented will work for any arbitrary box, but is overkill if your boxes never rotate. And looking at his, I realized that I didn't include the tests for if a point is inside the box, return 0 distance. As it stands, the code I presented will give the distance to the box's wireframe, so points inside the box will have a non-0 distance value. On an arbitrary box (as long as it is a box, and not a rhombus or trapezoid or other funny shape) you can test this easily by checking the values for u of the A->B and A->C tests, and if both do not require clamping (ie, both are in the range of [0,1]) then the point is inside the box, and you can return 0 for the distance.

Share this post


Link to post
Share on other sites
dEgle95    131
Thank you guys.
I did find another way, it's quite light too:
On each line, that presents side of block we find collision point and check if it's really on side of our block:

[CODE]

int lx,ly; //temporary point
float t_distance[4];

//FIND POINT ON TOP SIDE
ly = block->y;
lx = (block->y - y) / tan(angle) + x;

if( lx >= block->x && lx <= block->x + block->w && ly >= block->y && ly <= block->y + block->h)
//find distance to it
t_distance[0] = sqrt((float) (x - lx)*(x - lx) + (y - ly)*(y - ly));


//FIND POINT BOTTOM SIDE
ly = block->y + block->h;
lx = (block->y + block->h - y) /tan(angle) + x;

if( lx >= block->x && lx <= block->x + block->w && ly >= block->y && ly <= block->y + block->h)
//find distance to it
t_distance[1] = sqrt((float) (x - lx)*(x - lx) + (y - ly)*(y - ly));


//FIND POINT ON LEFT SIDE

lx = block->x;
ly = tan(angle) * (block->x - x) + y;

//check if temp point is onside of block
if( lx >= block->x && lx <= block->x + block->w && ly >= block->y && ly <= block->y + block->h)
//find distance to it
t_distance[2] = sqrt((float) (x - lx)*(x - lx) + (y - ly)*(y - ly));


//FIND POINT ON RIGHT SIDE
lx = block->x + block->w;
ly = tan(angle) * (block->x + block->w - x) + y;


if( lx >= block->x && lx <= block->x + block->w && ly >= block->y && ly <= block->y + block->h)
//find distance to it
t_distance[3] = sqrt((float) (x - lx)*(x - lx) + (y - ly)*(y - ly));
[/CODE]
Then just find minimum in t_distance and there u have it!

Ohh...and by the way my blocks aren't rotating and are just represented as x,y,width and height

Share this post


Link to post
Share on other sites
dEgle95    131
Well...it's part of ray class, so my ray has angle, maximum length and point of start.
Now how it works:
To find distance to each side we make 2 functions:
y = kx — function of ray.
x = c or y = c — function of side, because they are not rotating.
Then we need to find k — it's just [b]tan(angle)[/b].
Then calculate point where 2 functions are crossing and check if this point lies on side of current block.

pretty simple [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

Share this post


Link to post
Share on other sites
alvaro    21247
I think both JPTippetts and I were under the impression that you wanted to compute the distance from a point to a box (see the title you gave to this thread). Now it looks like you wanted to find the first intersection of a ray and a box. A clear description of what you were trying to do would have been nice.

As usual, you probably shouldn't an angle at all. If you use a vector instead, you won't have to handle special cases (like when the tangent of the angle is infinite).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this