I'm having such a problem: i can't figure easiest way to find distance between point and block (as shown on picture)
Everything that i tried is not properly working
Could you help me please and tell way to find that distance.
0
8 replies to this topic
Sponsor:
#2 Moderators - Reputation: 5033
Posted 15 April 2012 - 08:01 AM
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:
For a given point, P, you can find the value of u that corresponds to the closest point on the line, P1->P2, by:
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:
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:
P=P1+u*(P2-P1)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:
u=((P.x-P1.x)*(P2.x-P1.x) + (P.y-P1.y)*(P2.y-P1.y)) / length(P2-P1)^2
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:
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
Note that it's quick code, so I might have made an error somewhere, but initial tests indicate it works.
#3 Members - Reputation: 5882
Posted 15 April 2012 - 08:51 AM
Here's some C++ code for you:
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);
}
#4 Moderators - Reputation: 5033
Posted 15 April 2012 - 10:01 AM
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.
#5 Members - Reputation: 131
Posted 15 April 2012 - 11:31 AM
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:
Ohh...and by the way my blocks aren't rotating and are just represented as x,y,width and height
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:
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));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
#7 Members - Reputation: 131
Posted 15 April 2012 - 01:31 PM
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 tan(angle).
Then calculate point where 2 functions are crossing and check if this point lies on side of current block.
pretty simple
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 tan(angle).
Then calculate point where 2 functions are crossing and check if this point lies on side of current block.
pretty simple
#8 Members - Reputation: 5882
Posted 15 April 2012 - 01:46 PM
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).
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).
