hello friend

i have to find out an intersection point between 2 segments

input will be x & y coordinate of 2 segments

line 1 (AB) ==> x,y coordinate of A & B are given
line 2 (CD) ==> x,y coordinate of C & D are given

how to find out whether these 2 segments intersects each other or not ???????

give psudo code if possible

hello friends

i have found a solution to find whether 2 segments intersectseach other or not as follow

m1=(y2-y1)/(x2-x1) ---- A
m2=(v2-v1)/(u2-u1) ---- B

c1=y1-m1*x1
c2=v1-m2*x2

so the intersection points are

xi=(c2-c1)/(m1-m2) ---- C
yi=m1*xi+c1

if((((x1-xi)*(xi-x2))>0)&&(((y1-yi)*(yi-y2))>0)&&(((u1-xi)*(xi-u2))>0)&&(((v1-xi)*(xi-v2))>0))
{
both segments intersects each other
}
else
both segments will not intersect each other


but in special case this solution will fail which are as follows

1) if line 1 is vertical, the instruction labeled (A) will cause an error because of an attempt to divide by zero, as numerical processors cannot deal with infinity

2) similarly if line 2 is vertical, line (B) will cause an error

3) if the two lines are parallel, line (C) will cause an error

how to handle these cases
CAN ANYONE HELP ME ?????

It is the program's responsibility (i.e. the Programmer's responsibility) to make sure that no undefined mathematical operations take place. Within your context, you must test to see if x1 is equal to x2 before performing calculation A. If they are equal then that line is vertical, and its equation is x = x1 (or, equivalently, x = x2). If they are not equal, then obtain the value of m1 by performing calculation A.
Same comment. If u1 is equal to u2, then the line is vertical and its equation is x = u1 (or, equivalently, x = u2). If u1 is not equal to u2, then obtain the value of m2 by performing calculation B.

Note that if one is vertical and other is not, then the two infinite lines will intersect at exactly one point. It should be pretty simple to see whether the line segments contain that point.

If they are both vertical, it's a special case: The infinite lines are parallel or they are collinear. If they are parallel, then there is no intersection. If they are collinear, then the intersection of the line segments consists of the points in common. (The number of common points may be zero, or one, or infinity.)

If m1 and m2 are both defined (that is x1 != x2 and u1 != u2) and if m1 is equal to m2, then the infinite lines are either parallel (no intersection) or they are collinear, with the same considerations as mentioned in the previous step.

If you get this far and m1 is not equal to m2, then proceed along the lines of your remaining post.

Regards,

Dave

hello dave

thanks for your suggestion
i have changed the method to find intersection between 2 segments
as follows

each line can be represented in the form Ax+By=C, where A, B and C are the numbers which define the line.

we are given two different points, (x1, y1) and (x2, y2), and want to find A, B and C for the equation above. We can do so by setting
A = y2-y1
B = x1-x2
C = A*x1+B*y1

Regardless of how the lines are specified, you should be able to generate two different points along the line, and then generate A, B and C. Now, lets say that you have lines, given by the equations:
A1x + B1y = C1
A2x + B2y = C2

To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.

det = A1*B2 - A2*B1
if(det == 0)
{
//Lines are parallel
}
else
{
double x = (B2*C1 - B1*C2)/det
double y = (A1*C2 - A2*C1)/det
}

this solution handles all the cases of vertical line as well as parallel line

but there is only 1 problem
when 2 segments overlaps each other then this solution fails

can anyone tell me how to find out 2 segments overlaps each other or not ?

i want to find out whether these 2 segments overlap each other or not
(whether thy have more than 1 point common)
for example

A(2,2),B(6,6) & C(3,3),D(5,5)
now segment AB & CD overlaps each other
how to find it out mathematically
plz give explanation

Consider your system of two equations in the unknowns x and y.

There are three possibilities:

1. There is exactly one solution. This is the case where the infinite lines intersect, and the values of x and y from your solution equations tell us the intersection point. Note that the solution that you show only works if the determinant is not equal to zero. The equations of the lines are linearly independent.

2. There are an infinite number of solutions. This is the case where the infinite lines are collinear. The determinant is equal to zero. The equations of the lines are linearly dependent and they are consistent.

For example

3. There are no solutions. This is the case where the lines are parallel. The determinant is equal to zero. The equations of the lines are linearly dependent and they are inconsistent.

For example

Here's the deal: If the determinant is not equal to zero this is case 1, and there is a unique solution, given by your equations. The solution equations that you show are a manifestation of what is known as "Cramer's Rule," and the solutions equations are valid only when the determinant is not equal to zero.

If the determinant is equal to zero, there is not a unique solution. The value of the determinant alone can not tell you whether it is case 2 or case 3. One way that a program might discover which it is could be to let x and y have values representing a point that is on line number 1 and see whether that point is also on line 2. The way to do this programatically might be obvious, or, maybe, not.

Bottom line: Your program still has to do some work beyond just plugging values into some equations somewhere. I think it might be about the same amount of work as for the previous method (maybe a little more; maybe a little less), but clever programming might make one method seem more elegant than the other.

Regards,

Dave