Archived

This topic is now archived and is closed to further replies.

Distance between two line segments (2D)

This topic is 5041 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

As the topic implies, I need to determine whether or not a line segment (line1) passes within a certain distance of another (line2) in 2D. The tricky part is that I also need to find the first point on line1 that passes within that minimum distance. By "first point" I mean the point of intersection that is closest to startpoint on a line segment defined with startpoint and endpoint. I'll explain what I am trying to achieve and what I have already tried. Basically, I have a ball that moves, of which I wish to collide with a series of line segments. Previously, I have been checking the path taken by the ball each frame and seeing if it passes through any lines using line-segment to line-segment intersection tests: LineA = the line segment made by the movement of the ball each frame. Ie original position to updated position. LineB = some line segment in the game world. If LineA intersects LineB { Ball position = intersection point of LineA and LineB Ball velocity = reflection vector of the balls velocity on LineB Ball position += Ball velocity (get the position off the line) } This works fine when the ball is small (only a few pixels in radius). Otherwise it looks odd. So now I have come to the problem described. I do not want to merely cirlce-line segment test because I want the collisions to register even if there is a pause in the framerate. What I tried was calculating the reflection vector of LineA on LineB, then moving LineA equal to the ball's radius in the opposite direction of that vector. I was thereby moving LineA closer to LineB to account for the radius of the ball. This worked in a way, but my ball kept falling through the lines in many cases. Is there a better way to do this? Is there a simple answer to my original question (How to detect if a line passes within a certain distance of another, then determining the first point along that line that does)? Any help would be great, but keep in mind that I am no mathematician. Thanks. [edited by - jack_1313 on February 20, 2004 1:56:12 AM] [edited by - jack_1313 on February 20, 2004 2:07:19 AM] [edited by - jack_1313 on February 25, 2004 3:57:30 AM]

Share this post


Link to post
Share on other sites
gamasutra has an article about this at http://www.gamasutra.com/features/19991018/Gomez_1.htm

Note that it doesn''t handle the case of the ball bouncing off the tip of a line segment. Once you''ve found that that has happened, you can use the vector of the line segment tip through the center of the circle as the normal of the surface when calculating the reflection vector... but calculating the exact position of the circle when it hits the tip... you might have to look that one up.

btw, OT but how do you post a link to an article? Is there some <link> directive?

Share this post


Link to post
Share on other sites

// < a h r e f = " h t t p : \ \ ......... " > Link Here < / a >




with less spaces


and for source code

[ s o u r c e ]


...
..
..

[ / s o u r c e ]


[edited by - oliii on February 20, 2004 4:47:44 AM]

Share this post


Link to post
Share on other sites
I found this yesterday:
http://mathworld.wolfram.com/Line-LineDistance.html

I assume the ''x'' symbol means Cross product, ''.'' means Dot product and |...| is the length....
Didn''t have engouth time to test

Share this post


Link to post
Share on other sites
Thanks a lot. I've had a good look at the article on Gamasutra and although it discusses planes rather than segments I think I can apply this relatively easily.
So that is the second part of my question solved (more or less). I can determine the point of first intersection with a 2d line (I think) using the formula described in the article. Now all I need to know is how to calculate the minimum distance between two 2d segments so as that I can say "if min_dist(line1,line2) is below ball_radius then determine intersection point etc etc". Thanks all the same MV, but the link you provided discusses a method of finding the distance between two skew lines rather than 2d segments. I have googled but apparently it is not a common problem. Anyone willing to help?
I apologize for my late response.


[edited by - jack_1313 on February 23, 2004 2:27:41 AM]

Share this post


Link to post
Share on other sites
Hey, I have adopted this code from here and tried to put it into use. It is suposed to give the distance between two line segments. The problem is that it is designed for use in 3d, and I cannot get it to work in 2d, despite the fact that the code does not make specific use of the z dimension. I may be far off with this anyway, but it is all I can come up with.



#define SMALL_NUM 0.00000001 // anything that avoids division overflow

#define dot(u,v) ((u.x*v.x) + (u.y*v.y)) //<- This is changed from the original to allow for 2d rather than 3d

#define norm(v) sqrt(dot(v,v)) // norm = length of vector

#define d(u,v) norm(u-v) // distance = norm of difference

#define abs(x) ((x) >= 0 ? (x) : -(x)) // absolute value


float
dist_Segment_to_Segment( Point2D l1p1, Point2D l1p2, Point2D l2p1, Point2D l2p2)
{
Point2D u = l1p2 - l1p1;
Point2D v = l2p2 - l2p1;
Point2D w = l1p1 - l2p1;
float a = dot(u,u); // always >= 0

float b = dot(u,v);
float c = dot(v,v); // always >= 0

float d = dot(u,w);
float e = dot(v,w);
float D = a*c - b*b; // always >= 0

float sc, sN, sD = D; // sc = sN / sD, default sD = D >= 0

float tc, tN, tD = D; // tc = tN / tD, default tD = D >= 0


// compute the line parameters of the two closest points

if (D < SMALL_NUM) { // the lines are almost parallel

sN = 0.0; // force using point P0 on segment S1

sD = 1.0; // to prevent possible division by 0.0 later

tN = e;
tD = c;
}
else { // get the closest points on the infinite lines

sN = (b*e - c*d);
tN = (a*e - b*d);
if (sN < 0.0) { // sc < 0 => the s=0 edge is visible

sN = 0.0;
tN = e;
tD = c;
}
else if (sN > sD) { // sc > 1 => the s=1 edge is visible

sN = sD;
tN = e + b;
tD = c;
}
}

if (tN < 0.0) { // tc < 0 => the t=0 edge is visible

tN = 0.0;
// recompute sc for this edge

if (-d < 0.0)
sN = 0.0;
else if (-d > a)
sN = sD;
else {
sN = -d;
sD = a;
}
}
else if (tN > tD) { // tc > 1 => the t=1 edge is visible

tN = tD;
// recompute sc for this edge

if ((-d + b) < 0.0)
sN = 0;
else if ((-d + b) > a)
sN = sD;
else {
sN = (-d + b);
sD = a;
}
}
// finally do the division to get sc and tc

sc = (abs(sN) < SMALL_NUM ? 0.0 : sN / sD);
tc = (abs(tN) < SMALL_NUM ? 0.0 : tN / tD);

// get the difference of the two closest points

Point2D dP = w + (u * sc) - (v * tc); // = S1(sc) - S2(tc)


return norm(dP); // return the closest distance

}



Any help?

Share this post


Link to post
Share on other sites
quote:
problem is that it is designed for use in 3d


You can apply the preceding formulae assuming z=0, or another value, it doesn''t matter as long as it stays constant

Share this post


Link to post
Share on other sites
quote:
Original post by MV
quote:
problem is that it is designed for use in 3d


You can apply the preceding formulae assuming z=0, or another value, it doesn''t matter as long as it stays constant




Yeah, that''s the messy way to do it. For the time being it will be good enough.

Share this post


Link to post
Share on other sites
To anyone reading this post at a later stage – the code in the box above works perfectly, I was just doing something ridiculously stupid with my loop in which I was testing it. Excuse me while I beat myself over the head with a brick .

[edited by - jack_1313 on February 27, 2004 8:25:56 PM]

Share this post


Link to post
Share on other sites