-1

I have the below end points of line segments.

Line segment 1:

A = (X1, Y1)
B = (X2, Y2)

Line segment 2:

C = (X3, Y3)
D = (X4, Y4)

I want to get the point of intersection of these two line segments.

I tried like this:

def intersectionfn(l1,l2):

    x1,y1 = l1.src.x, l1.src.y
    x2,y2 = l1.dst.x, l1.dst.y
    x3,y3 = l2.src.x, l2.src.y
    x4,y4 = l2.dst.x, l2.dst.y

    try:
        xnum = float(((x1*y2-y1*x2)*(x3-x4))-((x1-x2)*(x3*y4-y3*x4)))
        xden = float(((x1-x2)*(y3-y4))-((y1-y2)*(x3-x4)))
        #print xnum, xden
        xcoor = float(xnum)/xden
        #print xcoor
        ynum = float((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))
        yden = float((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
        #print ynum, yden
        ycoor = float(ynum)/yden
        #print ycoor
        return Point(xcoor,ycoor)
    except:
        print "No intersection.. 0/0 attempted"

But I am getting the output for infinitely long lines. I'm not aware of how to find it for line segments. If there is any algorithm/mathematical rule for it, please suggest it to me. I will implement it.

Cedric Zoppolo
  • 4,271
  • 6
  • 29
  • 59
buddingengineer
  • 95
  • 9
  • 2
    Take a look at [this question](https://stackoverflow.com/questions/34982918/segment-segment-intersection). – jdehesa Sep 25 '17 at 16:57
  • 1
    Pure code-writing requests are off-topic on Stack Overflow -- we expect questions here to relate to *specific* programming problems -- but we will happily help you write it yourself! Tell us [what you've tried](https://stackoverflow.com/help/how-to-ask), and where you are stuck. This will also help us answer your question better. – glennsl Sep 25 '17 at 16:58
  • Hi glennsl, I edited my question. I tried to find using line intersection equation. It worked fine but intersection points are given for infinitely long lines. I just want to know if there is any mathematical equation or inbuilt function to find out line segment intersection. – buddingengineer Sep 25 '17 at 17:08
  • jdehesa, Thanks. I will take a look at it! – buddingengineer Sep 25 '17 at 17:13
  • In a nutshell, you need to check if the calculated point of intersection actually lies on each of the lines—so look up/find out how to do that ("Is point on line?"). – martineau Sep 25 '17 at 17:53
  • @Martineau: IMO, a pretty bad piece of advice (or bad formulation). Because the intersection naturally lies on both lines, and checking if a point lies on a line requires to set a tolerance. This is both useless and risky. The real test is if the point lies on the *line segments*, knowing that it lies on the lines. –  Sep 26 '17 at 08:10
  • @Yves: I meant check if the point actually lies on each the line segments. In 2D all infinite non-parallel line "intesect" and have a point-in-common—which is what the general equations for them allow you to calculate. – martineau Sep 26 '17 at 14:27

1 Answers1

0

The sign of the cross product PQ x QR (let us call it Cross(P, Q, R)) tells you if P is on the left or right of the line through QR.

Your two segments will intersect iff A and B are on opposite sides of CD, while C and D are on opposite sides of AB.

Furthermore, the function Cross is linear, so that Cross((1 - t) A + t B, C, D) = (1 - t) Cross(A, C, D) + t Cross(B, C, D). If you compute the t that cancels this expression, that leads you to the intersection point.