# A BB4W Compendium

freeman69@gmx.com

IDIC

# 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

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

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