Jump to content

  • Log In with Google      Sign In   
  • Create Account


Distance to ray intersection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 dEgle   Members   -  Reputation: 131

Like
0Likes
Like

Posted 15 April 2012 - 05:54 AM

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)
Posted Image
Everything that i tried is not properly working Posted Image
Could you help me please and tell way to find that distance.

Sponsor:

#2 JTippetts   Moderators   -  Reputation: 7948

Like
1Likes
Like

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:
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 Álvaro   Crossbones+   -  Reputation: 10693

Like
2Likes
Like

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 JTippetts   Moderators   -  Reputation: 7948

Like
1Likes
Like

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 dEgle   Members   -  Reputation: 131

Like
0Likes
Like

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:


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

#6 Álvaro   Crossbones+   -  Reputation: 10693

Like
1Likes
Like

Posted 15 April 2012 - 12:35 PM

My code seems a lot easier than that. Can you explain how yours works? Like, where do you get the angle from?

#7 dEgle   Members   -  Reputation: 131

Like
0Likes
Like

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 Posted Image

#8 Álvaro   Crossbones+   -  Reputation: 10693

Like
0Likes
Like

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).

#9 dEgle   Members   -  Reputation: 131

Like
0Likes
Like

Posted 16 April 2012 - 12:24 AM

Sorry guys for my mistake in he title :) But still thanks for your concern. I will use your algorithms in other project :)




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS