Calculate the intersection point of 2 straight lines

[Paul Dixon]

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.

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).]