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
