Programming by Example

 

A BB4W Compendium

freeman69@gmx.com

IDIC BBC_Owl2 M&P

Intersecting Lines

Technically, this program should be called 'intersecting line segments' because lines are infinite and this program determines if, and where, two line segments intersect.

 

This version uses vectors and not y=mx+c.

 

  10 MODE 9:OFF

  20 *REFRESH OFF

  30

  40 DIM ix{(4) x,y}

  50 MAXLINES=30

  60 DIM polygon{(MAXLINES) x,y}

  70 REM Create polygon

  80 x=640:y=512

  90 FOR a=0 TO MAXLINES-1

 100   angle=360/MAXLINES*a

 110   r=RND(200)+200

 120   polygon{(a)}.x=x+SIN(RAD(angle))*r

 130   polygon{(a)}.y=y+COS(RAD(angle))*r

 140 NEXT

 150 polygon{(MAXLINES)}.x=polygon{(0)}.x

 160 polygon{(MAXLINES)}.y=polygon{(0)}.y

 170

 180 angle=0

 190 REPEAT

 200   TIME=0:CLS

 210   REM Draw polygon

 220   GCOL 0,2

 230   FOR a=0 TO MAXLINES

 240     IF a=0 THEN

 250       MOVE polygon{(a)}.x,polygon{(a)}.y

 260     ELSE

 270       IF a<MAXLINES b=a ELSE b=0

 280       DRAW polygon{(b)}.x,polygon{(b)}.y

 290     ENDIF

 300   NEXT

 310   REM Test each polygon line against blue radial line

 320   angle+=1:r=350

 330   FOR a=0 TO MAXLINES-1

 340     ix{(0)}.x=x

 350     ix{(0)}.y=y

 360     ix{(1)}.x=x+SIN(RAD(angle))*r

 370     ix{(1)}.y=y+COS(RAD(angle))*r

 380     GCOL 0,4:LINE x,y,ix{(1)}.x,ix{(1)}.y

 390     ix{(2)}.x=polygon{(a)}.x

 400     ix{(2)}.y=polygon{(a)}.y

 410     ix{(3)}.x=polygon{(a+1)}.x

 420     ix{(3)}.y=polygon{(a+1)}.y

 430     IF FNintersect THEN

 440       GCOL 0,7:CIRCLE ix{(4)}.x,ix{(4)}.y,12

 450     ENDIF

 460   NEXT

 470   *REFRESH

 480   WAIT 4-TIME

 490 UNTIL FALSE

 500 END

 510

 520 REM This routine expects 4 pairs of co-ordinates (2 lines) in ix{()}

 530 REM and determines if the lines intersect

 540 REM The point of intersection is stored in row 4 of ix{()} and the

 550 REM function returns TRUE if an intersect occurs

 560 DEF FNintersect

 570 LOCAL xa,ya,xb,yb,xg,yg,xn,yn,ndotb,ndota,t,xd,yd

 580 REM Calculate vectors alpha, beta & gamma

 590 xa=ix{(1)}.x-ix{(0)}.x:REM alpha

 600 ya=ix{(1)}.y-ix{(0)}.y

 610 xb=ix{(2)}.x-ix{(0)}.x:REM beta

 620 yb=ix{(2)}.y-ix{(0)}.y

 630 xg=ix{(3)}.x-ix{(2)}.x:REM gamma

 640 yg=ix{(3)}.y-ix{(2)}.y

 650 xn=-yg:yn=xg:REM Normal of gamma

 660 ndotb=xn*xb+yn*yb

 670 REM Lines parallel (never intersect)?

 680 IF ndotb=0 THEN =FALSE

 690 ndota=xn*xa+yn*ya

 700 t=ndotb/ndota

 710 REM Intersect is within first line segment?

 720 IF t<0 OR t>1 THEN =FALSE

 730 REM Calculate intersect point

 740 ix{(4)}.x=ix{(0)}.x+t*xa

 750 ix{(4)}.y=ix{(0)}.y+t*ya

 760 REM Intersect is within second line segment?

 770 xd=ix{(4)}.x-ix{(2)}.x:REM delta

 780 yd=ix{(4)}.y-ix{(2)}.y

 790 IF xd*xg+yd*yg<0 OR (xd^2+yd^2)>(xg^2+yg^2) THEN =FALSE

 800 =TRUE

Arrow black large Arrow black large