C>>>TESS TESS 10 C ..................................................................TESS 20 C TESS 30 C SUBROUTINE TESSEL TESS 40 C TESS 50 C PURPOSE TESS 60 C CONSIDER A NETWORK OF POLYGONS IN A PLANE. IF ALL THAT IS TESS 70 C KNOWN IS THE POSITIONS OF THE POINTS AND WHICH POINTS ARE TESS 80 C JOINED BY EDGES, THIS PROGRAM WILL FIND THE POLYGONS. TESS 90 C TESS 100 C USAGE TESS 110 C CALL TESSEL (P, NPOI, INED, NED, POLY, START, NPOLY, LBUG) TESS 120 C TESS 130 C DESCRIPTION OF THE PARAMETERS TESS 140 C P - MAXPOI BY 2 ARRAY GIVING THE POINTS' POSITIONS TESS 150 C NPOI - NUMBER OF POINTS TESS 160 C INED - MAXEDG BY 2 INTEGER*2 ARRAY WHEREIN INED(I,1) AND TESS 170 C INED(I,2) ARE THE NUMBERS OF THE POINTS AT THE TESS 180 C ENDS OF THE I-TH EDGE. THE POINTS ARE NUMBERED TESS 190 C SEQUENTIALLY AS THEY ARE LISTED IN P. TESS 200 C NED - NUMBER OF EDGES LISTED IN INED. TESS 210 C POLY - IS RETURNED AS A MAXVER LONG INTEGER*2 VECTOR, TESS 220 C CONTAINING THE NUMBERS OF THE VERTICES OF ALL THE TESS 230 C RESULTANT POLYGONS. TESS 240 C START - IS RETURNED AS A MAXPLY LONG INTEGER*2 VECTOR TESS 250 C WHERE START(N) IS THE LOCATION IN POLY OF THE TESS 260 C FIRST VERTEX OF POLYGON #N. THE VERTEX NUMBERS ARETESS 270 C LISTED SEQUENTIALLY IN POLY, WITH THE LAST VERTEX TESS 280 C OF POLYGON #N IN POLY(START(N+1)-1). TESS 290 C NPOLY - NUMBER OF POLYGONS FOUND AND PLACED IN POLY. TESS 300 C LBUG - A LOGICAL VARIABLE SUPPLIED BY MAIN PROGRAM. IF TESS 310 C .TRUE. THEN VARIOUS DEBUGGING INFO IS PRINTED. TESS 320 C TESS 330 C REMARKS TESS 340 C NOTE: MAXPOI,MAXEDG,MAXVER,MAXPLY REFER TO ARRAY SIZES TESS 350 C MAXPOI=600,MAXEDG=650,MAXVER=2600,MAXPLY=101 TESS 360 C UP TO MAXPOI DATA POINTS AND MAXEDG EDGES ARE TESS 370 C ALLOWED IN THE INPUT DATA. THERE MAY BE UP TO MEV=10 TESS 380 C EDGES FROM ANY ONE POINT. THE RESULTANT POLYGONS CAN HAVE TESS 390 C UP TO MAXPOI VERTICES. THE TOTAL NUMBER OF VERTICES IN TESS 400 C ALL THE POLYGONS MUST NOT EXCEED MAXVER. TESS 410 C THERE MAY BE UP TO MPOLY POLYGONS. TO INCREASE THESE TESS 420 C LIMITS, THE VARIABLES NAMED IN COMMON, AS WELL TESS 430 C AS THE BOUNDS OF SOME ARRAYS MUST BE INCREASED. TESS 440 C THE POLYGONS ARE RETURNED RUNNING COUNTERCLOCKWISE. TESS 450 C THE FIRST VERTEX OF EACH POLYGON IS REPEATED IN POLY, AND TESS 460 C IS COUNTED TWICE WHEN THE NUMBER OF VERTICES IS CALCULATED. TESS 470 C THE NUMBER OF VERTICES IN POLYGON #N IS START(N+1)-START(N).TESS 480 C DURING CALCULATION, ANY NUMBERS WITHIN TOLER OF EACH TESS 490 C OTHER ARE CONSIDERED EQUAL. TESS 500 C ANY POLYGONS THAT WOULD HAVE ZERO AREA ARE NOT RETURNED. TESS 510 C THE RESULTANT POLYGONS MAY FORM SEVERAL DISJOINT GROUPS, TESS 520 C THAT IS THE GRAPH OF THE EDGES NEED NOT BE CONNECTED. TESS 530 C WRITTEN BY RANDOLPH FRANKLIN, UNIVERSITY OF OTTAWA, 6/72. TESS 540 C TESS 550 C SUBROUTINES AND FUNCTION SUBPROGRAMS REQUIRED TESS 560 C AREA - FUNCTION TO CALCULATE SIGNED AREA OF A POLYGON. TESS 570 C TESS 580 C METHOD TESS 590 C SEE FLOWCHART FOR THIS SUBROUTINE TESS 600 C TESS 610 C ..................................................................TESS 620 C TESS 630 SUBROUTINE TESSEL (P,NPOI,INED,NED,POLY,START,NPOLY,LBUG) TESS 640 C EVERY EDGE IS USED ONCE EACH WAY, EXCEPT THE EXTERIOR EDGES WHICH TESS 650 C ARE ONLY USED ONCE. TESS 660 C NEP(I,*) LISTS THE EDGES ADJOINING THE I-TH POINT. TESS 670 C NONEP(I) IS THE NUMBER OF EDGES ADJOINING THE I-TH POINT. TESS 680 C LNEP(I,J)=.TRUE. IF THE J-TH EDGE FROM THE I-TH POINT RUNS TOWARD TESS 690 C A HIGHER NUMBERED POINT, OTHERWISE IT IS FALSE. TESS 700 C ANGLE(I) IS THE ANGLE OF THE I-TH LINE. TESS 710 REAL P(600,2),ANGLE(650),TX(600),TY(600) TESS 720 INTEGER*2 INED(650,2),NEP(600,10),POLY(2600),NONEP(600) TESS 730 INTEGER*2 START(101) TESS 740 LOGICAL LBUG,LNEP*1(600,10),LFIRST TESS 750 C LFIRST=.TRUE. FOR THE FIRST EDGE OF A POLYGON. TESS 760 C IFIRST IS THE FIRST EDGE OF A POLYGON. TESS 770 C O IS UNIT FOR PRINTED MESSAGES. TESS 780 INTEGER O/3/ TESS 790 NPOLY=0 TESS 800 MAXPOI=600 TESS 810 MAXEDG=650 TESS 820 MAXVER=2600 TESS 830 C LK IS THE NUMBER OF SPACES USED TO DATE IN POLY. TESS 840 LK=0 TESS 850 MPOLY=100 TESS 860 MEV=10 TESS 870 PI=3.141593 TESS 880 TOLER=.0001 TESS 890 WRITE (O,1) NED,NPOI TESS 900 1 FORMAT ('-TESSEL HAS RECEIVED',I5,' LINKS JOINING',I5,' VERTICES.'TESS 910 1) TESS 920 IF (NPOI.LE.MAXPOI) GO TO 3 TESS 930 WRITE (O,2) NPOI,MAXPOI TESS 940 2 FORMAT ('-ERROR:',I5,' INPUT POINTS IS TOO MANY FOR TESSEL. THE MATESS 950 1XIMUM IS ',I5) TESS 960 RETURN TESS 970 3 IF (NED.LE.MAXEDG) GO TO 5 TESS 980 WRITE (O,4) NED,MAXEDG TESS 990 4 FORMAT ('-ERROR:',I5,' INPUT LINES IS TOO MANY FOR TESSEL. THE MAXTESS1000 1IMUM IS',I5) TESS1010 RETURN TESS1020 C CALCULATE ANGLES. TESS1030 5 DO 12 I=1,NED TESS1040 IF (INED(I,1).LE.NPOI.AND.INED(I,1).GE.1.AND.INED(I,2).LE.NPOI.ANDTESS1050 1.INED(I,2).GE.1) GO TO 7 TESS1060 IF (LBUG) WRITE (O,6) I,INED(I,1),INED(I,2) TESS1070 6 FORMAT ('-ERROR: EDGE',I3,' WHICH HAS ENDPOINTS',2I5,' IS ILLEGAL.TESS1080 1 IT WILL BE IGNORED BY TESSEL.') TESS1090 INED(I,1)=1 TESS1100 INED(I,2)=1 TESS1110 GO TO 12 TESS1120 C CHANGE INEP SO THAT THE 2-ND POINT HAS THE HIGHER NUMBER. TESS1130 7 IF (INED(I,2)-INED(I,1)) 10,8,11 TESS1140 8 WRITE (O,9) I TESS1150 9 FORMAT (' EDGE #',I4,' HAS THE SAME ENDPOINTS. IT WILL BE IGNORED'TESS1160 1) TESS1170 GO TO 12 TESS1180 10 J=INED(I,2) TESS1190 INED(I,2)=INED(I,1) TESS1200 INED(I,1)=J TESS1210 C CALCULATE ANGLES. TESS1220 11 ANGLE(I)=ATAN2(P(INED(I,1),2)-P(INED(I,2),2),P(INED(I,2),1)-P(INEDTESS1230 1(I,1),1)) TESS1240 12 CONTINUE TESS1250 C CALCULATE NEP,NONEP TESS1260 DO 13 I=1,NPOI TESS1270 NONEP(I)=0 TESS1280 13 CONTINUE TESS1290 DO 15 I=1,NED TESS1300 IF (INED(I,1).EQ.INED(I,2)) GO TO 15 TESS1310 DO 14 J=1,2 TESS1320 K=INED(I,J) TESS1330 NONEP(K)=NONEP(K)+1 TESS1340 NEP(K,NONEP(K))=I TESS1350 LNEP(K,NONEP(K))=J.EQ.1 TESS1360 14 CONTINUE TESS1370 15 CONTINUE TESS1380 IF (.NOT.LBUG) GO TO 21 TESS1390 WRITE (O,16) TESS1400 16 FORMAT ('0ANGLES OF LINKS OR EDGES:') TESS1410 WRITE (O,17) (ANGLE(I),I=1,NED) TESS1420 17 FORMAT (' ANGLES:',10G12.5) TESS1430 DO 19 I=1,NPOI TESS1440 K=NONEP(I) TESS1450 WRITE (O,18) I,K,(NEP(I,J),J=1,K) TESS1460 18 FORMAT (' POINT',I3,' IS SURROUNDED BY',I3,' EDGES:',10I4) TESS1470 WRITE (O,20) (LNEP(I,J),J=1,K) TESS1480 19 CONTINUE TESS1490 20 FORMAT ('+',T78,'DO THEY HEAD UP?',10L2) TESS1500 C NPOLY IS THE NUMBER OF THE POLYGON CURRENTLY BEING FOUND. TESS1510 C START A NEW POLYGON. TESS1520 21 NPOLY=NPOLY+1 TESS1530 22 START(NPOLY)=LK+1 TESS1540 DO 23 NSTART=1,NPOI TESS1550 IF (NONEP(NSTART).GT.0) GO TO 25 TESS1560 23 CONTINUE TESS1570 C ALL EDGES FROM ALL POINTS HAVE BEEN USED. TESS1580 NPOLY=NPOLY-1 TESS1590 WRITE (O,24) NPOLY TESS1600 24 FORMAT ('-TESSEL HAS FOUND',I5,' POLYGONS.') TESS1610 RETURN TESS1620 25 NI=NSTART TESS1630 NJ=1 TESS1640 LFIRST=.TRUE. TESS1650 IFIRST=NEP(NI,1) TESS1660 C NK IS THE NUMBER OF VERTICES OF THIS POLYGON THAT HAVE BEEN FOUND.TESS1670 NK=0 TESS1680 C I AM PROCEEDING ALONG THE NJ-TH EDGE FROM THE NI-TH POINT. TESS1690 26 CONTINUE TESS1700 C K IS THE ABSOLUTE NUMBER OF THE NJ-TH EDGE. TESS1710 K=NEP(NI,NJ) TESS1720 NK=NK+1 TESS1730 LK=LK+1 TESS1740 IF (NK.LE.MAXPOI) GO TO 28 TESS1750 LK=LK-1 TESS1760 WRITE (O,27) NPOLY,MAXPOI,POLY(LK) TESS1770 27 FORMAT (' POLYGON',I5,' HAS MORE THAN ',I4,' VERTICES. VERTEX',I5,TESS1780 1' WILL BE DELETED.') TESS1790 NK=MAXPOI TESS1800 28 IF (LK.LE.MAXVER) GO TO 30 TESS1810 WRITE (O,29) NPOLY,MAXVER TESS1820 29 FORMAT ('-ERROR: WHEN TESSEL WAS FINDING POLYGON #',I5,' THE TOTALTESS1830 1 ALLOWABLE NUMBER OF VERTICES =',I5,' WAS EXCEEDED.'/' IT IS USELETESS1840 2SS FOR TESSEL TO CONTINUE. SIMPLIFY DATA OR INCREASE ARRAY SIZE.')TESS1850 RETURN TESS1860 30 POLY(LK)=NI TESS1870 TX(NK)=P(NI,1) TESS1880 TY(NK)=P(NI,2) TESS1890 C FIND ANGLE OF PRESENT EDGE. TESS1900 T=ANGLE(K) TESS1910 IF (LNEP(NI,NJ)) T=PI+T TESS1920 C DELETE THE EDGE THAT HAS JUST BEEN USED UNLESS IT IS THE FIRST TESS1930 C EDGE. TESS1940 IF (LFIRST) GO TO 33 TESS1950 IF (NJ.EQ.NONEP(NI)) GO TO 32 TESS1960 M=NONEP(NI)-1 TESS1970 IF (M.EQ.0) GO TO 42 TESS1980 DO 31 I=NJ,M TESS1990 LNEP(NI,I)=LNEP(NI,I+1) TESS2000 NEP(NI,I)=NEP(NI,I+1) TESS2010 31 CONTINUE TESS2020 32 NONEP(NI)=NONEP(NI)-1 TESS2030 C J IS THE NEW POINT. TESS2040 33 IF (NI.EQ.INED(K,1)) GO TO 34 TESS2050 J=INED(K,1) TESS2060 GO TO 35 TESS2070 34 J=INED(K,2) TESS2080 35 CONTINUE TESS2090 C IS THE POLYGON COMPLETE? TESS2100 IF (NSTART.NE.NI.OR.IFIRST.NE.K) GO TO 36 TESS2110 IF (.NOT.LFIRST) GO TO 39 TESS2120 LFIRST=.FALSE. TESS2130 36 CONTINUE TESS2140 C FIND THE NEXT EDGE. TESS2150 N=NONEP(J) TESS2160 RM=2*PI TESS2170 T=AMOD(T+RM,RM) TESS2180 I=-1 TESS2190 DO 38 M=1,N TESS2200 IF (NEP(J,M).NE.K) GO TO 37 TESS2210 L=M TESS2220 GO TO 38 TESS2230 37 CONTINUE TESS2240 R=T-ANGLE(NEP(J,M)) TESS2250 IF (.NOT.LNEP(J,M)) R=R+PI TESS2260 R=AMOD(R+16*PI+TOLER,2.*PI) TESS2270 IF (R.GE.RM) GO TO 38 TESS2280 I=M TESS2290 RM=R TESS2300 38 CONTINUE TESS2310 NI=J TESS2320 NJ=I TESS2330 C IF I<0, I HAVE COME TO A DEAD END LINE, AND MUST HEAD BACK. TESS2340 IF (I.LT.0) NJ=L TESS2350 GO TO 26 TESS2360 39 IF (LBUG) WRITE (O,40) NPOLY,NK,(POLY(START(NPOLY)-1+I),I=1,NK) TESS2370 40 FORMAT (' POLYGON #',I5,' HAS',I5,' VERTICES:',(T34,20I5)) TESS2380 IF (AREA(TX,TY,NK).GT.0.) GO TO 21 TESS2390 LK=START(NPOLY)-1 TESS2400 IF (LBUG) WRITE (O,41) TESS2410 41 FORMAT (' THE ABOVE POLYGON HAS A NEGATIVE AREA. IT WILL BE IGNORETESS2420 1D.') TESS2430 GO TO 22 TESS2440 42 CONTINUE TESS2450 WRITE (O,43) I,J,K,L,M,N,NI,NJ,NED,NPOI,NSTART,NPOLY,MEV,MPOLY,MEPTESS2460 1,NVER,NONEP,NEP,NK TESS2470 43 FORMAT (' HELP',(12I10)) TESS2480 WRITE (O,44) PI,R,RM,T,TX,TY TESS2490 44 FORMAT (10G12.5) TESS2500 RETURN TESS2510 END TESS2520