Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

Calculate the intersection point of 2 straight lines

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Calculate the intersection point of 2 straight lines

    A correction..
    The original code failed on certain horizontal lines. Now fixed.
    Also runs a little quicker, average about 45cpu clocks.
    ..end correction

    A quick PB/CC1.0 function to see if and where 2 straight lines intersect. It takes about 50 cpu clock cycles on a k6-III.
    At 400MHz clock that's 8 million intersection checks per second.

    The 2 lines are specified by (x1,y1)-(x2,y2) and (x3,y3)-(x4,y4)

    The function returns -1 if the lines cross. xc and yc are the co-ordinates of the point of intersection.
    The function returns 0 if the lines don't cross. xc and yc are the co-ordinates of where the extrapolated lines would cross.
    The value returned is +1 if the lines are parallel. In this case the xc and yc are not valid.

    Call the function using e.g.
    If intersect(a,b , c,d , e,f , g,h)=-1 then print "The lines intersect at"xc,yc

    For a quick demonstration check out a simple program using the function at www.axol-electronics.com/inttest.exe

    Paul.

    Code:
    GLOBAL xc AS DOUBLE, yc AS DOUBLE
    FUNCTION intersect(BYVAL x1,BYVAL y1,BYVAL x2,BYVAL y2,BYVAL x3,BYVAL y3,BYVAL x4,BYVAL y4) AS LONG
    
    REM First LINE slope AND intercept
    !fld x1
    !fld x2
    !fsubp st(1),st(0)    ;x1-x2
    
    !ftst
    !fstsw ax
    !test ax,&h4000
    !jnz infS1            ;slope1=infinite
    
    'slope1<>infinite.
    !call eq1             ;get slope and intercept 1
    
    REM Second LINE slope AND intercept
    !fld x3
    !fld x4
    !fsubp st(1),st(0)    ;x3-x4
    
    !ftst
    !fstsw ax
    !test ax,&h4000
    !jnz infs2          ;slope2=infinite
    
    'slope1<>inf and slope2<>inf
    !call eq2             ;get slope and intercept 2
    
    'now get cross point
    !fsubr st(0),st(2)    ;slope1 - slope2
    
    !ftst
    !fstsw ax
    !test ax,&h4000
    !jnz parallel           ;slope1=slope2 so lines do not intercept
    
    'lines intercept, now work out where
    !fxch
    !fsub st(0),st(3)     ;int2 - int1
    !fdivrp st(1),st(0)   ;xcross
    
    !fst xc
    !fmulp st(1),st(0)
    !faddp st(1),st(0)    ;ycross
    !fst yc
    
    !jmp InSeg            ;see if they cross in the defined segments of the lines
    
    infS1:
    'slope1=infinite
    'FPstack=x1-x2
    !fstp st(0)         ;discard stack
    
    REM Second LINE slope AND intercept
    !fld x3
    !fld x4
    !fsubp st(1),st(0)    ;x3-x4
    
    !ftst
    !fstsw ax
    !test ax,&h4000
    !jnz infS12            ;slope1=slope2=infinite
    
    'slope2<>infinite
    'slope1=inf and slope2<>inf
    !call eq2            ;get slope and intercept 2
    
    'now get cross point
    !fld x1
    !fst xc
    !fmulp st(1),st(0)
    !faddp st(1),st(0)      ;slope2*x1 + int2 = yint
    !fst yc
    
    !jmp InSeg              ;see if they cross in the defined segments of the lines
    
    
    infS2:
    'slope2=infinite, slope1 not infinite
    'FPstack= x3-x4,s1,i1
    !fstp st(0)         ;discard stack
    
    'now get cross point
    !fld x3
    !fst xc
    !fmulp st(1),st(0)
    !faddp st(1),st(0)      ;slope1*x3 + int1 = yint
    !fst yc
    
    !jmp InSeg              ;see if they cross in the defined segments of the lines
    
    
    parallel:
    !fstp st(0)         ;clean up FP stack
    !fstp st(0)
    !fstp st(0)
    infS12:
    !fstp st(0)
    !mov function,1     ;the lines do not cross (they're parallel)
    !jmp xit
    
    
    eq1:
    'assume x1-x2 is on stack
    !fld y1
    !fld y2
    !fsubp st(1),st(0)    ;y1-y2
    
    !fdiv st(0),st(1)     ;slope1
    
    !fld x1
    !fld y2
    !fmulp st(1),st(0)    ;x1*y2
    
    !fld y1
    !fld x2
    !fmulp st(1),st(0)    ;x2*y1
    
    !fsubp st(1),st(0)    ;x1*y2 - x2*y1
    !fdivrp st(2),st(0)   ;intercept1
    'FPstack = s1,i1 + FPstack
    !retn
    
    eq2:
    'assume x3-x4 is on stack
    !fld y3
    !fld y4
    !fsubp st(1),st(0)    ;y3-y4
    
    !fdiv st(0),st(1)     ;slope2
    
    !fld x3
    !fld y4
    !fmulp st(1),st(0)    ;x3*y4
    
    !fld y3
    !fld x4
    !fmulp st(1),st(0)    ;x3*y4
    
    !fsubp st(1),st(0)    ;x3*y4 - x4*y3
    !fdivrp st(2),st(0)   ;intercept2
    'FPstack= s2,i2 + FPstack
    !retn
    
    'rem is the cross within the defined line segments?
    InSeg:
    'yc is on the stack
    !fld y1
    !fcomp st(1)
    !fstsw ax
    !mov bx,ax
    
    !fld y2
    !fcompp     ; st(1)
    !fstsw ax
    
    !sahf
    !jz skip3a
    
    !xor bx,ax
    !and bx,&b0100010100000000
    !jz xit              ;they don't cross in the defined segments
    
    skip3a:
    !fld yc
    !fld y3
    !fcomp st(1)
    !fstsw ax
    !mov bx,ax
    
    !fld y4
    !fcompp     ; st(1)
    !fstsw ax
    
    !sahf
    !jz skip5a
    
    !xor bx,ax
    !and bx,&b0100010100000000
    !jz xit             ;they don't cross in the defined segments
    
    skip5a:
    !fld xc
    !fld x1
    !fcomp st(1)
    !fstsw ax
    !mov bx,ax
    
    !fld x2
    !fcompp     ; st(1)
    !fstsw ax
    
    !sahf
    !jz skip3
    
    !xor bx,ax
    !and bx,&b0100010100000000
    !jz xit             ;they don't cross in the defined segments
    
    skip3:
    !fld xc
    !fld x3
    !fcomp st(1)
    !fstsw ax
    !mov bx,ax
    
    !fld x4
    !fcompp     ; st(1)
    !fstsw ax
    
    !sahf
    !jz skip5
    
    !xor bx,ax
    !and bx,&b0100010100000000
    !jz xit             ;they don't cross in the defined segments
    
    skip5:
    !mov function,-1   ;they do cross in the defined segments
    
    xit:
    'At this point xc = X co-ord of intersetion, yc = Y co-ord of intersetion
    'FUNCTION=0 if the lines do not cross in the segments specified
    'FUNCTION=-1 IF they DO cross in the segments specified
    'FUNCTION=+1 if the lines are parallel (do not cross at all)
    
    
    END FUNCTION

    [This message has been edited by Paul Dixon (edited February 07, 2003).]
Working...
X