i have 2 segments

the first line has points whose coordinates are:

(x1,y1) and (x2,y2)

and second line has points whose coordinates are:

(u1,v1) and (u2,v2)

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

I suggest that you might start by visualization, aided by actual visual construction.

In other words...

Draw the lines (with pencil and paper). Try to see whether you can convince yourself that the following claims are always true.

First of all, you need to know that the two infinite lines (the lines that contain the given segments) are collinear. That is, the equations for the lines are linearly dependent and consistent.

In general what might happen between the line segments?



I think that there are three possibilities:

They might have no points in common. (The segments don't overlap at all.)

They might have exactly one point in common. (One segment butts up against the other.)

They might overlap with an infinite number of common points

I suggest that you draw line segments that illustrate these three conditions. Are all possibilities covered? What else could happen with segments from collinear lines?

Then, given that the lines are collinear, and (x1 != x2) and (u1 != u2), lets see if we can make some general observations that might lead to something useful.

Let minx = min(x1,x2), maxx = max(x1,x2)
Let minu = min(u1,u2), maxu = max(u1,u2)

Consider the two cases:

Case 1: minx <= minu

Claim 1a: The line segments have exactly one point in common if and only if
minu == maxx

Claim 1b: The line segments overlap with an infinite number of common points if and only if
minu < maxx

Claim 1c (The only other possibility if neither the conditions for Claim 1a or Claim 1b hold): The line segments don't overlap if and only if
minu > maxx

Case 2: minu < minx

Claim 2a: The line segments have exactly one point in common if and only if
minx == maxu

Claim 2b: The line segments overlap with an infinite number of common points if and only if
minx < maxu

Claim 2c (The only other possibility if neither the conditions for Claim 1a or Claim 1b hold): The line segments don't overlap if and only if
minx > maxu

If these claims are true, then an implementation can be straightforward. Of course it is possible that a more elegant solution can be formulated, but I think an implementation that is obtained directly from observation might be practical, at least for starters.


Regards,

Dave