Finding intersecting lines

Here is all the information you need.

Click here: intersection or two lines

Now, was that so hard?

Excuse me for a sec, I''m going to go beat my head against the wall.

Thank you for your time.

If the 2D lines don''t have the same slope then they intersect. If they have the same slope, then they''re either parallel or coincident. If there slopes are negative reciprocals of eachother, then the two lines are perpendicular to each other. The negative reciprocal the negated inverse of the slope. For instance, if a line has a slope of 2, which means that for every positive movement on the x axis there are 2 positive movements along the y, then any line perpendicular to it would have a slope of -1/2 (2^-1 = 1/2). This methode even works if the the line happens to be coincident or parallel to the x or y axes. For instance, a line parallel to the x axis could have an eqution of y=3. The slope of y=3 is zero, because the slope-intercept form of a line is y=mx + b, where m is the slope. Now, the negative reciprocal of zero is 1 over 0, which can be translated as moving up one unit and to the right zero units, or as "undefined," which in mathematics terms means a vertical line--one perpendicular to a horizontal line and parallel/coincident with the y axis.

Ok, this Is the code I''m using. You''ll have to excuse the space it takes up. I don''t know the codes for this board. If someone could enlighten me.

I think my problem is specifically with the last section which determines if the lines actually intersect at their current lengths.

And if I could opmitize it somehow, that would be good.

COORDVAR Line_Sect(COORDVAR c1, COORDVAR c2, COORDVAR c3, COORDVAR c4)
{
//function designed to give the intersection point of two lines.
//Lines that eventually would intersect if infinite cause a to equal 0, otherwise its 1.

float b1, b2; //The slope of each line
float a1, a2; //The adjustment each line needs
COORDVAR ReturnInfo; //The information that will be returned by the function

//This whole algorith runs off sytems of equations and the fact that any straight lines can
//be written as y = a + (b * x)

if(c1.x - c2.x == 0)
c2.x += .001;

if(c3.x - c4.x == 0)
c4.x += .001;

//Find the slope of each line

//Slope of first line
b1 = (c1.y - c2.y) / (c1.x - c2.x);
//Check to make sure slope is non-zero
if(b1 == 0)
b1 = .001;

//slope of second line
b2 = (c3.y - c4.y) / (c3.x - c4.x);
//Check to make sure slope is non-zero
if(b2 == 0)
b2 = .001;

//Make sure lines aren''t perpendicular
if(b1 == b2)
b1 += .001;

//add the height adjustments
a1 = c1.y - (b1 * c1.x);
a2 = c3.y - (b2 * c3.x);

//Finally, find the intersection points
ReturnInfo.x = -(a1 - a2) / (b1 - b2);
ReturnInfo.y = a1 + (b1 * ReturnInfo.x);

//Check to make sure the lines intersect immediatly
if((c1.x - ReturnInfo.x) * (ReturnInfo.x - c2.x) < 0 && (c3.x - ReturnInfo.x) * (ReturnInfo.x - c3.x) < 0)
{
//"Intersect" should change to 0,0 and A should be set to 0
ReturnInfo.x = 0;
ReturnInfo.y = 0;
ReturnInfo.a = 0;
}
else
ReturnInfo.a = 1;





return(ReturnInfo);
}

Here's some fun math for you.

Let q and r be the y coordinates of the given lines.
q = mx + b
r = Mx + B

Let a line segment be defined by:
q(x) for x: min <= x <= max

So a line segment would be a combination of a line equation and a min,max pair:




[edited by - ApochPiQ on May 27, 2003 12:00:44 PM]

Is my code optimized enough? This is going to be used in my game to test collisions... regardless of framerate.

Are there some quick ways to optimize?

I think you peeps are doing way too many calculations. Think about a scenario where one line has a slope of 100, for instance, every year the city grows 100 in population--the x-axis being the year. And another city loses 100 people a year, so the difference in change between them is 200, correct?---abs(-00-100). Now, divide that into the y intercept of one, and you''ll get a coord, I think...>_<

with that kind of maths, you can do 100,000 tests per frame on recent hardware. I don''t think you should worry too much about the performance.

However, if you want performance, try to remove the divisions, and try to exit the functions as soon as possible, with minimum calculations. The lines are more likely to not collide than to collide, so rejecting no-collision cases quickly is good.

I''m trying to think of a separating-axis algorithm, but in 2D. That must be achievable. This does not need divisions. so it''s both faster and safer. Look on Google for separating axes on convex hulls or boxes. After all, a line is a convex shape, so the algorithm also applies to lines. Just look at the concept, and see if can come up with an idea.

after 5 mins of reflexion, I think I''ve got it. you''ll need 6 separating axis tests. I let you find out which ones

http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf

the first few lines and the first drawing will explain to you what it''s all about. The rest is maths, so be prepared if you want to go in-depth.

the site has other interesting docs about 2D intersection techniques, that you might want to check out.

http://www.win.tue.nl/~gino/solid/jgt98convex.pdf

I guess that optimization isn''t needed... the collision code is only applied to nearby tiles...

Anyhow, I got it working perfectly. My old coordinate system used points, and when a certain point was in a tile the ship went in a certain direction. No longer! The old points are all tested against the four walls of the tile in question. If it intersects with a certain tile, it moves the ship out of the tile and changes its velocity. Presto!

A note: for each wall, I had to include three checks:

1) Make sure ship is on the side of the tile that this wall is on
2) Only check if ship is moving towards tile
3) Make sure the tile doesn''t have a neighbor in the direction of the wall.

The last one was done with a table set up earlier at level load.

Anyhow, I''m happy.

rofl

optimizing your code doesn t take to much time does it?

there s no reason not to speed up your code this will give you more freedom for adding more complex calculations to do what ever you want

quite frankly there s a reason to optimize it
1. collision detection is fine when it works at decent speed but with growing polycounts collision detection time grows resulting in less performance-> less polycounts

2. you haven t finished or even started most parts of your engine so how can you say it s not needed?

you never know what you are planing to do

for example you want to write a collision detection function

fine but what if you decide to add collision detection to your particles? ehhehehe
have much fun with optimizing your code then

My game is 2d...

And the amount of checks done each second are minimal...