OVERLAY PROCEDURE CONVEX_HULL_MENU;

    { This procedure display the driving menu for the convex hull
      algorithm. The CONVEX_HULL procedure is called from this menu. }

PROCEDURE CONVEX_HULL;

  { AN ALGORITHM THAT DETERMINES WHICH POINTS OF A PLANER SET ARE
    VERTICES OF THE CONVEX HULL OF THE SET.

    There is one refinement. The paper giving the algorithm used
    only small population sizes to be analysized. This program
    allows for any number of points in a population by taking the
    points 100 at a time. Vertices are kept between iterations but
    all interior points are dropped. If 25 points from the first pass
    are vertices, then 75 internal points are dropped and 75 points are
    added from the data file. }


  TYPE
    AR1 = ARRAY[1..2,1..100] OF REAL;
    AR3 = ARRAY[1..200]      OF INTEGER;

    INDEXPOINTER = ^INDEXRECORD;

    INDEXRECORD = RECORD
                    INDEXVALUE : INTEGER;
                    NEXT       : INDEXPOINTER;
                  END;

  VAR


    FINAL_PASS : BOOLEAN;    { TRUE WHEN LAST SET OF POINTS HAVE BEEN PROCESSED }
    RETURN_FLAG : BOOLEAN;   { CONTROLS WHEN TO RETURN FROM CONVEX }
    ULFLAG     : BOOLEAN;    { CONTROLS SORTING FOR UPPER OR LOWER CURVE }

    I         : INTEGER;     { A WORK COUNTER }
    IK        : INTEGER;
    J         : INTEGER;     { A WORK COUNTER }
    NCOUNT    : INTEGER;     { THE NUMBER OF POINTS IN THE SAMPLE }
    NUMBER_OF_VERTICIES : INTEGER;
                             { NUMBER OF POINTS ON THE HULL}
    NUM_VERT_M1 : INTEGER;   { TRUE NUMBER OF VERTICES FOR AREA ROUTINES }
    POINTSREAD : INTEGER;
    STARTLOAD : INTEGER;     { INDEX TO START LOADING THE ARRAY IN }

    XX        : AR1;
    INAR      : ARRAY100I;
    VERTEX    : ARRAY100I;   { WAS IH IN ORIGINAL }
    XAR       : ARRAY100R;
    YAR       : ARRAY100R;

    LEFTEND   : INDEXPOINTER;
    RIGHTEND  : INDEXPOINTER;
    PT1       : INDEXPOINTER;
    PT2       : INDEXPOINTER;
    NEWINDEX  : INDEXPOINTER;
    LASTONE   : INDEXPOINTER;
    HEAPTOP   : ^INTEGER;

    PROCEDURE POLY_AREA(VAR X,Y        : ARRAY100R;
                        VAR NUM_POINTS : INTEGER;
                        VAR AREA       : REAL);
      { CALCULATES THE AREA OF THE HOME RANGE BY INTEGRATION.
        FIRST, THE AREA UNDER THE UPPER CURVE OF THE HOME RANGE IS FOUND.
        SECOND, THE AREA UNDER THE LOWER CURVE OF THE HOME RANGE IS FOUND.
        THIRD, THE LOWER AREA IS SUBTRACTED FROM THE UPPER AREA. }

    VAR
      UPPER    : ARRAY50I;               { UPPER POINTS OF THE POLYGON }
      LOWER    : ARRAY50I;               { LOWER POINTS OF THE POLYGON }

      AREA1    : REAL;                   { SECTION AREA FROM CURVE_AREA }
      INTER    : REAL;                   { Y INTERCEPT OF THE LINE }
      SLOPE    : REAL;                   { SLOPE OF THE LINE }
      ZEROVAL  : REAL;                   { ZERO VALUE OF ALL PTS IN THE EQUATION }

      I        : INTEGER;                { A WORK COUNTER }
      LPTR     : INTEGER;                { INDEX INTO LOWER ARRAY }
      UPTR     : INTEGER;                { INDEX INTO UPPER ARRAY }
      XLINDEX  : INTEGER;                { INDEX OF POINT WITH XLOW }
      XHINDEX  : INTEGER;                { INDEX OF POINT WITH XHIGH }

      PROCEDURE BUBBLE(VAR XSORT,YSORT : ARRAY100R;
                       VAR PTRVAL : ARRAY50I;
                       VAR APTR   : INTEGER;
                       VAR ULFLAG : BOOLEAN);

        VAR
          NOSWAP : BOOLEAN;   { SET TO TRUE WHEN SORT IS FINISHED }
          HOLD   : INTEGER;   { WORK AREA TO HOLD PART OF SWAPPED VAR }
          I      : INTEGER;   { A WORK COUNTER }

        BEGIN  { BUBBLE PROCEDURE }

          NOSWAP := FALSE;
          WHILE NOT NOSWAP DO
            BEGIN
              NOSWAP := TRUE;
              FOR I := 2 TO APTR DO
                IF XSORT[PTRVAL[I-1]] > XSORT[PTRVAL[I]] THEN
                  BEGIN
                    HOLD := PTRVAL[I-1];
                    PTRVAL[I-1] := PTRVAL[I];
                    PTRVAL[I] := HOLD;
                    NOSWAP := FALSE;
                  END;  { IF XSORT (I) > XSORT ( I+1 ) }
                IF XSORT[PTRVAL[I-1]] = XSORT[PTRVAL[I]] THEN
                  BEGIN
                    IF ULFLAG THEN       { ULFLAG = TRUE FOR UPPER CURVE }
                      IF YSORT[PTRVAL[I-1]] < YSORT[PTRVAL[I]] THEN
                        BEGIN
                          HOLD := PTRVAL[I-1];
                          PTRVAL[I-1] := PTRVAL[I];
                          PTRVAL[I] := HOLD;
                          NOSWAP := FALSE;
                        END;  { SWAP DUE TO Y VALUES }
                    IF NOT ULFLAG THEN     { ULFLAG = FALSE FOR LOWER CURVE}
                      IF YSORT[PTRVAL[I-1]] > YSORT[PTRVAL[I]] THEN
                        BEGIN
                          HOLD := PTRVAL[I-1];
                          PTRVAL[I-1] := PTRVAL[I];
                          PTRVAL[I] := HOLD;
                          NOSWAP := FALSE;
                        END;  { SWAP DUE TO Y VALUES  - LOWER CURVE }
                  END; { XSORT (I-1) = XSORT(I) }

            END;  { WHILE NOT NOSWAP DO }
        END;  { BUBBLE PROCEDURE }


      BEGIN  { POLY_AREA PROCEDURE }
      XLINDEX := 0;
      XHINDEX := 0;

      { GET LOW AND HIGH X VALUES }

      FOR I := 1 TO NUM_POINTS DO
        BEGIN
          IF ( I = 1 ) OR ( X[I] < X[XLINDEX] ) THEN XLINDEX := I;
          IF ( I = 1 ) OR ( X[I] > X[XHINDEX] ) THEN XHINDEX := I;
        END;

      { GET SLOPE OF CROSSING LINE }

      SLOPE := (Y[XHINDEX] - Y[XLINDEX]) / (X[XHINDEX] - X[XLINDEX]);
      INTER := Y[XLINDEX] - SLOPE*X[XLINDEX];

      { DIVIDE POINTS INTO UPPER OR LOWER ARRAYS }

      UPTR := 0;
      LPTR := 0;

      FOR I := 1 TO NUM_POINTS DO
        BEGIN
          ZEROVAL := Y[I] - SLOPE*X[I] - INTER;
          IF ZEROVAL >= -0.0001 THEN
            BEGIN
              UPTR := UPTR + 1;
             UPPER[UPTR] := I;
            END;
          IF ZEROVAL <= 0.0001 THEN
            BEGIN
              LPTR := LPTR + 1;
              LOWER[LPTR] := I;
            END;
        END;  { FOR I = 1 TO NUM_POINTS }

      { SORT THE TWO ARRAYS IN TO ASCENDING X ORDER }

      ULFLAG := TRUE;
      BUBBLE(X,Y,UPPER,UPTR,ULFLAG);
      ULFLAG := FALSE;
      BUBBLE(X,Y,LOWER,LPTR,ULFLAG);


      { NOW, CALL POINT BY POINT AND GET THE AREAS
        FIRST THE UPPER CURVE }

      AREA := 0;

      FOR I := 1 TO UPTR-1 DO
        BEGIN
          CURVE_AREA(X[UPPER[I]],Y[UPPER[I]],X[UPPER[I+1]],Y[UPPER[I+1]],AREA1);
          AREA := AREA + AREA1;
        END;


      { NOW, SUBTRACT THE LOWER CURVE }

      FOR I := 1 TO LPTR-1 DO
        BEGIN
          CURVE_AREA(X[LOWER[I]],Y[LOWER[I]],X[LOWER[I+1]],Y[LOWER[I+1]],AREA1);
          AREA := AREA - AREA1;
        END;

      END;  { POLY_AREA PROCEDURE }

   PROCEDURE CONVEX(VAR X :AR1;
                    VAR NUMBER_OF_VERTICIES : INTEGER);


    { PROCEDURE TO ACTUALLY DETERMINE WHICH POINTS ARE VERTICES }

    VAR
      MAXE    : BOOLEAN;
      MINE    : BOOLEAN;

      EXTREME_INDEX : INTEGER;    { ARRAY INDEX OF EXTREME POINT IN SET }
      I       : INTEGER;          { A WORK COUNTER }
      J       : INTEGER;          { A WORK COUNTER }
      MIN_X_INDEX : INTEGER;      { EXTREME MIN X POINT IN SET }
      MAX_X_INDEX : INTEGER;      { EXTREME MAX X POINT IN SET }

      HALF : NAME;                { TELLS WHAT PART OF HULL BEING WORKED ON }

  PROCEDURE SINGLE_POINT;

    BEGIN
      WRITE ('SINGLE_POINT');
      NUMBER_OF_VERTICIES := 1;
      NEW(NEWINDEX);
      NEWINDEX^.INDEXVALUE := 1;
      NEWINDEX^.NEXT := NIL;
      RIGHTEND := NEWINDEX;
      LEFTEND  := NEWINDEX;
      RETURN_FLAG   := TRUE;
    END; { SINGLE_POINT PROCEDURE }

  PROCEDURE DOUBLE_POINT;

    BEGIN
      WRITE ('DOUBLE_POINT');
      NEW(NEWINDEX);
      NEWINDEX^.INDEXVALUE := MAX_X_INDEX;
      RIGHTEND := NEWINDEX;

      NEW(NEWINDEX);
      NEWINDEX^.INDEXVALUE := MIN_X_INDEX;
      LEFTEND := NEWINDEX;
      RIGHTEND^.NEXT := NEWINDEX;
      LEFTEND^.NEXT := NIL;

      IF ( X[1,MIN_X_INDEX] = X[1,MAX_X_INDEX] ) AND
         ( X[2,MIN_X_INDEX] = X[2,MAX_X_INDEX] )
           THEN NUMBER_OF_VERTICIES := 1
           ELSE NUMBER_OF_VERTICIES := 2;

      RETURN_FLAG := TRUE;
    END; { DOUBLE_POINT PROCEDURE }

  PROCEDURE VERTICAL_LINE;

    BEGIN
      WRITE ('VERTICAL');
      MAX_X_INDEX := 1;
      MIN_X_INDEX := 1;
      FOR I := 1 TO NCOUNT DO
        BEGIN
          IF X[2,I] > X[2,MAX_X_INDEX] THEN
            MAX_X_INDEX := I;

          IF X[2,I] < X[2,MIN_X_INDEX] THEN
            MIN_X_INDEX  := I;

        END; { FOR I := 1 TO M }

    END; { VERTICAL_LINE PROCEDURE }

  PROCEDURE SPLIT (VAR PT1     : INDEXPOINTER;
                   VAR PT2     : INDEXPOINTER;
                   VAR EXTREME_INDEX : INTEGER;
                   VAR HALF    : NAME);

    { This procedure partitions a subset of array X into two smaller
      subsets. The split is made along a line joining two possible verticies
      of the convex hull containing all points in the full set.

      The point at maximum distance, if it exists, from the splitting line
      is returned to CONVEX. There are two points, one above the line and
      one below the line. }

    VAR
      VERTICAL : BOOLEAN;         { TRUE OF DIVIDING LINE IS VERTICAL }

      DIRECTION : INTEGER;        { SHOWS LINE DIRECTION FOR VERTICAL LINES }
      I       : INTEGER;          { A WORK VARIABLE }
      INDEX1  : INTEGER;          { ARRAY INDEX OF THE FIRST POINT }
      INDEX2  : INTEGER;          { ARRAY INDEX OF THE SECOND POINT }

      EXTREME_VALUE : REAL;       { ZERO_VALUE OF THE EXTREME_POINT }
      INTERCEPT : REAL;           { Y INTERCEPT FOR THE LINE }
      SLOPE     : REAL;           { SLOPE OF THE LINE }
      TOP_X   : REAL;             { X VALUE OF TOP POINT IN A VERTICAL LINE }
      ZERO_VALUE : REAL;          { VALUE OF POINT RELATIVE TO DIVIDING LINE }



    BEGIN  { SPLIT PROCEDURE }

      WRITE (OUTPUT,'+');

      INDEX1 := PT1^.INDEXVALUE;
      INDEX2 := PT2^.INDEXVALUE;

      { CHECK TO SEE IF THE LINE IS VERTICAL }

      VERTICAL := FALSE;

      IF X[1,INDEX2] = X[1,INDEX1] THEN
        BEGIN
WRITELN (' IN SPLIT A VERTICAL LINE');
          TOP_X := X[1,INDEX1];
          IF X[2,INDEX2] > X[2,INDEX1] THEN
            DIRECTION := 1                           { UP }
          ELSE
            DIRECTION := -1;                         { DOWN }
          IF HALF = 'TOP'
            THEN DIRECTION := DIRECTION * 1           { BOTTOM UP }
            ELSE DIRECTION := DIRECTION * -1;         { BOTTOM DOWN }
          VERTICAL := TRUE;
        END
      ELSE
        BEGIN
          SLOPE := ( X[2,INDEX2] - X[2,INDEX1] ) / ( X[1,INDEX2] - X[1,INDEX1] );
          INTERCEPT := X[2,INDEX1] - SLOPE * X[1,INDEX1];
        END;

      EXTREME_INDEX := 0;
      EXTREME_VALUE := 0.0;

      FOR I := 1 TO NCOUNT DO
        BEGIN
          IF VERTICAL
            THEN ZERO_VALUE := DIRECTION * ( X[1,I] - TOP_X )
            ELSE ZERO_VALUE := X[2,I] - SLOPE * X[1,I] - INTERCEPT;

          IF ( ZERO_VALUE > 0.00001 ) AND ( HALF = 'TOP') THEN
            BEGIN

              { THE POINT IS ABOVE THE LINE }

              IF ( I <> INDEX1 ) AND ( I <> INDEX2 ) THEN
              IF ZERO_VALUE > EXTREME_VALUE THEN
                BEGIN
                  EXTREME_INDEX := I;
                  EXTREME_VALUE := ZERO_VALUE;
                END;
             END;  { IF Z > 0 }

          IF ( ZERO_VALUE < -0.00001 ) AND ( HALF = 'BOTTOM') THEN
            BEGIN

              { THE POINT IS BELOW THE LINE AND HALF IS BOTTOM }

              IF ( I <> INDEX1 ) AND ( I <> INDEX2 ) THEN
              IF ZERO_VALUE < EXTREME_VALUE THEN
                BEGIN
                  EXTREME_INDEX := I;
                  EXTREME_VALUE := ZERO_VALUE;
                END;
            END;  { IF Z < -0.00001 AND HALF = 'BOTTOM' }

        END;  { FOR I = 1 TO NCOUNT }

    END;  { SPLIT PROCEDURE }


    BEGIN  { CONVEX PROCEDURE }

      GOTOXY(1,22);
      WRITE(OUTPUT,'.');


      RETURN_FLAG := FALSE;

      IF NOT RETURN_FLAG THEN
        IF NCOUNT = 1 THEN SINGLE_POINT;

      IF NOT RETURN_FLAG THEN
        IF NCOUNT = 2 THEN DOUBLE_POINT;

      IF NOT RETURN_FLAG THEN
      BEGIN                     { IF NOT RETURN_FLAG 4 }
        MAXE    := FALSE;
        MINE    := FALSE;

      { FIND TWO VERTICES OF THE CONVEX HULL FOR THE INITIAL PARTITION }

        MAX_X_INDEX := 1;
        MIN_X_INDEX := 1;

        FOR I := 2 TO NCOUNT DO
          BEGIN

            {  MAXE IS TRUE WHEN THERE ARE MORE THAN ONE MAXIMUM X PTS.}

            IF X[1,I] = X[1,MAX_X_INDEX] THEN MAXE := TRUE;
            IF X[1,I] > X[1,MAX_X_INDEX] THEN
              BEGIN
                MAXE        := FALSE;
                MAX_X_INDEX := I;
              END;

            { MINE IS TRUE WHEN THERE ARE MORE THEN ONE MINIMUM X PTS.}

            IF X[1,I] = X[1,MIN_X_INDEX] THEN MINE := TRUE;
            IF X[1,I] < X[1,MIN_X_INDEX] THEN
              BEGIN
                MINE        := FALSE;
                MIN_X_INDEX := I;
              END;

          END;  { FOR I := 2 TO NCOUNT }

      { PROCESSING FOR TWO VERTICIES. ALL POINTS ARE ALONG ONE LINE. }

        IF MAX_X_INDEX = MIN_X_INDEX THEN
          BEGIN
            VERTICAL_LINE;
            IF MAX_X_INDEX = MIN_X_INDEX
              THEN SINGLE_POINT
              ELSE DOUBLE_POINT;
          END;
      END;                        { IF NOT RETURN_FLAG 4 }


    IF NOT RETURN_FLAG THEN
    BEGIN                         { IF NOT RETURN_FLAG 5 }

   { IF THERE ARE SEVERAL POINTS WITH THE SAME LARGEST FIRST COORDINATE }

      IF ( MAXE ) THEN
        FOR I := 1 TO NCOUNT DO

          IF ( X[1,I] = X[1,MAX_X_INDEX] )
            AND ( X[2,I] > X[2,MAX_X_INDEX] )

              THEN MAX_X_INDEX := I;

   { IF THERE ARE SEVERALPOINTS WITH THE SAME SMALLEST FIRST COORDINATE }

      IF ( MINE ) THEN
        FOR I := 1 TO NCOUNT DO

          IF ( X[1,I] = X[1,MIN_X_INDEX] )
            AND ( X[2,I] < X[2,MIN_X_INDEX] )

              THEN  MIN_X_INDEX := I;

    { THROUGH CHECKING SPECIAL CASES. NOW PROCESS }
    { SET UP THE RECORDS }

    MARK(HEAPTOP);          { MARK MEMORY TO RELEASE }
    LEFTEND  := NIL;
    RIGHTEND := NIL;

    NEW(NEWINDEX);          { FIRST RECORD IS THE EXTREME MAX X POINT }
    NEWINDEX^.INDEXVALUE := MAX_X_INDEX;
    RIGHTEND := NEWINDEX;

    NEW(NEWINDEX);          { SECOND RECORD IS THE EXTREME MIN X_POINT }
    NEWINDEX^.INDEXVALUE := MIN_X_INDEX;
    RIGHTEND^.NEXT := NEWINDEX;
    LEFTEND := NEWINDEX;

    NEW(NEWINDEX);          { THIRD RECORD IS FIRST RECORD - FULL CIRCLE }
    NEWINDEX^.INDEXVALUE := MAX_X_INDEX;
    LEFTEND^.NEXT := NEWINDEX;
    LASTONE       := NEWINDEX;
    LASTONE^.NEXT := NIL;

    PT1 := RIGHTEND;
    PT2 := LEFTEND;
    HALF := 'TOP';
    NUMBER_OF_VERTICIES := 3;

    { BEGIN BY MAKING THE INITIAL DIVISION }

    SPLIT(PT1,PT2,EXTREME_INDEX,HALF);

    WHILE HALF = 'TOP' DO
      BEGIN
        IF EXTREME_INDEX = 0 THEN
          BEGIN
            PT1 := PT1^.NEXT;      { NO VERTEX BETWEEN PT1 AND PT2, }
            PT2 := PT1^.NEXT;      { SHIFT DOWN TO NEXT SET OF POINTS }
          END
        ELSE
          BEGIN

            { INSERT A NEW VERTEX IN THE CHAIN OF HULL POINTS }

            NEW(NEWINDEX);
            NEWINDEX^.INDEXVALUE := EXTREME_INDEX;
            NEWINDEX^.NEXT := PT1^.NEXT;
            PT1^.NEXT := NEWINDEX;
            PT2 := PT1^.NEXT;
            NUMBER_OF_VERTICIES := NUMBER_OF_VERTICIES + 1;
          END;

        { CHECK IF THE TOP HALF IS DONE }

        IF PT1 = LEFTEND THEN HALF := 'BOTTOM';

        SPLIT(PT1,PT2,EXTREME_INDEX,HALF);

      END;  { WHILE HALF = 'TOP' }

    WHILE HALF = 'BOTTOM' DO
      BEGIN
        IF EXTREME_INDEX = 0 THEN
          BEGIN
            PT1 := PT1^.NEXT;      { NO VERTEX BETWEEN PT1 AND PT2, }
            PT2 := PT1^.NEXT;      { SHIFT DOWN TO NEXT SET OF POINTS }
          END
        ELSE
          BEGIN

            { INSERT A NEW VERTEX IN THE CHAIN OF HULL POINTS }

            NEW(NEWINDEX);
            NEWINDEX^.INDEXVALUE := EXTREME_INDEX;
            NEWINDEX^.NEXT := PT1^.NEXT;
            PT1^.NEXT := NEWINDEX;
            PT2 := PT1^.NEXT;
            NUMBER_OF_VERTICIES := NUMBER_OF_VERTICIES + 1;
          END;

        { CHECK IF THE BOTTOM HALF IS DONE }

        IF PT2 = NIL
          THEN HALF := 'DONE'
          ELSE SPLIT(PT1,PT2,EXTREME_INDEX,HALF);

      END;  { WHILE HALF = 'BOTTOM' }

    RETURN_FLAG := TRUE;
    END;                    { IF NOT RETURN_FLAG 5 }

    END; { PROCEDURE CONVEX }


  PROCEDURE DATA_ARRAY;

    { This procedure takes data from the input file and puts it into the
      array INAR. Initially 100 points are loaded. After that, each load
      will replace only interior points of the convex hull. If there are
      100 verticies on the hull, then the program terminates.

      The procedure PACK_ARRAY is called to move all verticies to the front
      of the array. }

    BEGIN { DATA_ARRAY }

      GOTOXY(1,23);
      WRITELN ('LOADING DATA_ARRAY');

      FOR I := STARTLOAD TO 100 DO
        BEGIN
          IF NOT EOF(FILEVAR2) THEN
            BEGIN
              READ (FILEVAR2,FILE2REC);
              WITH FILE2REC DO
                BEGIN
                  XX[1,I] := X;
                  XX[2,I] := Y;
                END;
              NCOUNT := I;
              POINTSREAD := POINTSREAD + 1;
            END
          ELSE
            BEGIN
              XX[1,I] := 0.00;
              XX[2,I] := 0.00;
              FINAL_PASS := TRUE;
            END;

        END; { FOR I = STARTLOAD TO 100 }

      GOTOXY(1,23);
      DELLINE;

    END; { PROCEDURE DATA_ARRAY }


  BEGIN  { CONVEX_HULL PROCEDURE }


    { OPEN AND SET THE FILE }

    ASSIGN (FILEVAR2,FILEOUT);
    RESET  (FILEVAR2);                 { POSITION AT BEGINNING OF FILE }
    SEEK   (FILEVAR2,3);               { POSITION FILE BEYOND HEADERS }

    FINAL_PASS := FALSE;
    STARTLOAD  := 1;                   { INITIAL LOAD WILL GET 100 POINTS }
    NUMBER_OF_VERTICIES := 0;
    POINTSREAD := 0;

    WHILE NOT FINAL_PASS DO
      BEGIN

      DATA_ARRAY;                      { FILL THE ARRAY XX }

      LINE_OUT(1,22,SPACE30);
      LINE_OUT(1,22,'-');

      CONVEX(XX,NUMBER_OF_VERTICIES);

      NEWINDEX := RIGHTEND;
      I := 0;

      WHILE NEWINDEX <> NIL DO
        BEGIN
          J      := NEWINDEX^.INDEXVALUE;
          I := I + 1;
          XAR[I] := XX[1,J];
          YAR[I] := XX[2,J];
          NEWINDEX := NEWINDEX^.NEXT;
        END;


      LINE_OUT(5,2,SPACE79);
      LINE_OUT(1,2,SPACE79);
      LINE_OUT(1,3,SPACE79);
      GOTOXY(5,2);
      WRITE (OUTPUT,'SAMPLE SIZE ',NCOUNT:5,' VERTICIES ',
             NUMBER_OF_VERTICIES:5,' SPLIT ',NCOUNT);
      WRITE (OUTPUT,' NUMBER OF POINTS READ: ',POINTSREAD:5);
      WRITELN;


      IF NOT FINAL_PASS THEN
        BEGIN
          FOR I := 1 TO NUMBER_OF_VERTICIES DO
            BEGIN
              XX[1,I] := XAR[I];
              XX[2,I] := YAR[I];
            END;
          STARTLOAD := NUMBER_OF_VERTICIES + 1;
          WRITELN (OUTPUT,'NUMBER OF VERTICIES CARRIED OVER: ',
            NUMBER_OF_VERTICIES);
        END;  { IF NOT FINAL_PASS }

     RELEASE(HEAPTOP);                 { RELEASE HEAP SPACE FOR NEXT PASS }

    END; { WHILE NOT FINAL_PASS }

  { DISPLAY THE VERTICIES OF THE POLYGON }

  LINE_OUT(1,3,SPACE79);
  GOTOXY(1,3);
  FOR I := 1 TO NUMBER_OF_VERTICIES DO
    WRITELN (OUTPUT,XAR[I]:10:5,YAR[I]:10:5);

  NUM_VERT_M1 := NUMBER_OF_VERTICIES - 1;

  IF PRECISION = 'I' THEN
    BEGIN

      { AREA BY INTEGRATION }

        POLY_AREA(XAR,YAR,NUM_VERT_M1,AREA);

        AREA := AREA * METER_VALUE * METER_VALUE;
        AREAK := AREA / 1000;
        AREAK := AREAK / 1000;
     END;  { AREA BY INTEGRATION }

{*******************************************************************}

     IF PRECISION = 'G' THEN
       BEGIN

         { AREA BY GRID CELL COUNT }

         AREA  := 0.0;
         AREAK := 0.0;

         XGRID_NUM := 0;     { XGRID_NUM HOLDS THE AREA IN GRID SQUARE NUMBERS }
         YGRID_NUM := 0;     { YGRID_NUM IS A WORK VARIABLE }

         WRITELN('Calculating the area by grid cell count.');

{ XHIGH AND XLOW WILL NEED REDEFINING }


{ THIS CODE NEED TO BE DONE. }


       END; { AREA BY GRID CELL COUNT }

{ *****************************************************************}

     IF AREA <= 10000 THEN
       WRITELN('                        AREA: ',AREA:10:5,' Square meters')
     ELSE
       WRITELN('                        AREA: ',AREAK:10:5,' Square kilometers');

      LINE_OUT(1,22,SPACE79);
      KEYBOARD_PAUSE;

      KEYVALUE := 'R';

      IF DRAWCHAR = 'Y' THEN
        BEGIN

          IF STUDYFILE <> '' THEN
            BEGIN
              ASSIGN (FILEVAR3,STUDYFILE);
              RESET  (FILEVAR3);
              STUDYOPEN := TRUE;
            END;

          { DRAW THE POINTS IN THE XAR AND YAR }
          { FIRST, GET THE X AND Y EXTREME VALUES }

          XHIGH := 0;
          XLOW  := 0;
          YHIGH := 0;
          YLOW  := 0;

          FOR I := 1 TO NUMBER_OF_VERTICIES DO
            BEGIN
              IF ( I = 1 ) OR ( XAR[I] < XLOW  ) THEN XLOW  := XAR[I];
              IF ( I = 1 ) OR ( XAR[I] > XHIGH ) THEN XHIGH := XAR[I];
              IF ( I = 1 ) OR ( YAR[I] < YLOW  ) THEN YLOW  := YAR[I];
              IF ( I = 1 ) OR ( YAR[I] > YHIGH ) THEN YHIGH := YAR[I];
            END;  { FOR I = 1 TO NUMBER OF VERTICIES }

          { SAVE THE MIN AND MAX VALUES FROM THE POLYGON }

          SXLOW := XLOW;
          SYLOW := YLOW;
          SZLOW := ZLOW;
          SXHIGH := XHIGH;
          SYHIGH := YHIGH;
          SZHIGH := ZHIGH;

          GRID_CALCULATIONS;

          HIRES;
          HIRESCOLOR(YELLOW);

          LINE_OUT(1,1,'Minimum Convex Polygon');

          FOR I := 1 TO NUMBER_OF_VERTICIES-1 DO
            HIRES_VECTOR(XAR[I],YAR[I],XAR[I+1],YAR[I+1],
                           XOFFSET,YOFFSET,GRIDFACTOR);

          { PUT IN THE FILE INFO }

          LINE_OUT(60,4,'Data file');
          LINE_OUT(64,5,FILEOUT);

          IF STUDYFILE <> '' THEN
            BEGIN
              LINE_OUT(60,7,'Map file:');
              LINE_OUT(64,8,STUDYFILE);
            END;

          IF REPLAYFILE <> '' THEN
            BEGIN
              LINE_OUT(60,10,'Replay File:');
              LINE_OUT(64,11,REPLAYFILE);
            END;

          LINE_OUT(62,13,'AREA:');
          GOTOXY(62,14);
          IF AREA <= 10000 THEN
            BEGIN
              WRITE (AREA:8:4);
              LINE_OUT(62,15,'Sq. meters.');
            END
          ELSE
            BEGIN
              WRITE (AREAK:8:4);
              LINE_OUT(62,15,'Sq. kilometers.');
            END;

          IF (STUDYFILE <> '') THEN
            BEGIN
              LINE_OUT(1,25,SPACE79);
              LINE_OUT(1,25,'Draw the study file area overlay? (Y|N) ');

              YES_NO(STUDYDRAWN);

              LINE_OUT(1,25,SPACE79);

              IF STUDYDRAWN = 'Y' THEN
                BEGIN                       { DRAW THE STUDY AREA }

                  HIRES;
                  HIRESCOLOR(YELLOW);

                  SEEK (FILEVAR3,1);        { MAX AND MINS FOR STUDY AREA  }
                  READ (FILEVAR3,FILE3REC);

                  XLOW := MIN_VAL(XLOW,FILE3REC.X1);
                  YLOW := MIN_VAL(YLOW,FILE3REC.Y1);
                  ZLOW := MIN_VAL(ZLOW,FILE3REC.Z1);
                  XHIGH := MAX_VAL(XHIGH,FILE3REC.X2);
                  YHIGH := MAX_VAL(YHIGH,FILE3REC.Y2);
                  ZHIGH := MAX_VAL(ZHIGH,FILE3REC.Z2);

                  GRID_CALCULATIONS;

                  LINE_OUT(1,1,'Minimum Convex Polygon');

                  SEEK (FILEVAR3,2);        { DATA BEGINS AT THE THIRD RECORD }

                  WHILE NOT EOF(FILEVAR3) DO
                    BEGIN
                      READ(FILEVAR3,FILE3REC);
                      WITH FILE3REC DO
                        HIRES_VECTOR(X1,Y1,X2,Y2,XOFFSET,YOFFSET,GRIDFACTOR);
                    END;

                  FOR I := 1 TO NUMBER_OF_VERTICIES-1 DO
                    HIRES_VECTOR(XAR[I],YAR[I],XAR[I+1],YAR[I+1],
                                 XOFFSET,YOFFSET,GRIDFACTOR);

                  { PUT IN THE FILE INFO }

                  LINE_OUT(60,4,'Data file');
                  LINE_OUT(64,5,FILEOUT);

                  IF STUDYFILE <> '' THEN
                    BEGIN
                      LINE_OUT(60,7,'Map file:');
                      LINE_OUT(64,8,STUDYFILE);
                    END;

                  IF REPLAYFILE <> '' THEN
                    BEGIN
                      LINE_OUT(60,10,'Replay File:');
                      LINE_OUT(64,11,REPLAYFILE);
                    END;

                  LINE_OUT(62,13,'AREA:');
                  GOTOXY(62,14);
                  IF AREA <= 10000 THEN
                    BEGIN
                      WRITE (AREA:8:4);
                      LINE_OUT(62,15,'Sq. meters.');
                    END
                  ELSE
                    BEGIN
                      WRITE (AREAK:8:4);
                      LINE_OUT(62,15,'Sq. kilometers.');
                    END;

                END;  { STUDYDRAWN = Y }

            END;  { IF STUDYFILE <> '' }

          IF REPLAYFILE <> '' THEN
            BEGIN
              LINE_OUT(1,25,SPACE79);
              LINE_OUT(1,25,'Do you want to add this graph to the replay file? (Y|N) ');

              YES_NO(KEYVALUE);

              IF KEYVALUE = 'Y' THEN
                BEGIN

                  IF NOT EXIST(REPLAYFILE) THEN INIT_REPLAY_FILE;

                  ASSIGN (FILEVAR4,REPLAYFILE);
                  RESET  (FILEVAR4);
                  REPLAYOPEN := TRUE;

                  { WRITE OUT THE PLOT. WILL INCLUDE THE CONVEX POLYGON AND MAYBE STUDY FILE }

                  IF STUDYDRAWN = 'Y' THEN
                    IF NOT STUDY_IN_REPLAY THEN
                      ADD_GRAPH('STUDYFILE');    { PUT STUDY AREA IN FILE }

                  { UPDATE THE WHOLE FILE VALUES }

                  SEEK (FILEVAR4,1);
                  READ (FILEVAR4,FILE4REC);

                  FILE4REC.X1 := MIN_VAL(FILE4REC.X1,SXLOW);
                  FILE4REC.Y1 := MIN_VAL(FILE4REC.Y1,SYLOW);
                  FILE4REC.Z1 := MIN_VAL(FILE4REC.Z1,SZLOW);
                  FILE4REC.X2 := MAX_VAL(FILE4REC.X2,SXHIGH);
                  FILE4REC.Y2 := MAX_VAL(FILE4REC.Y2,SYHIGH);
                  FILE4REC.Z2 := MAX_VAL(FILE4REC.Z2,SZHIGH);
                  FILE4REC.LINE_TYPE := FILE4REC.LINE_TYPE + NUMBER_OF_VERTICIES;

                  SEEK (FILEVAR4,1);
                  WRITE(FILEVAR4,FILE4REC);      { WRITE OUT RECORD 2 }
                  READ (FILEVAR4,FILE4REC);      { READ RECORD 3 }

                  FILE4REC.X2 := FILE4REC.X2 + 1;     { NUMBER OF GRAPHS IN FILE }

                  SEEK (FILEVAR4,2);
                  WRITE(FILEVAR4,FILE4REC);

                  { NOW, MODIFY THE GRAPH HEADERS AND WRITE OUT THE POINTS }

                  SEEK (FILEVAR4,FILESIZE(FILEVAR4)-1);
                  READ (FILEVAR4,FILE4REC);

                  FILE4REC.X1 := -3;             { -3 MEANS CONVEX GRAPH }
                  FILE4REC.Y1 := -10;
                  FILE4REC.X2 := -10;
                  FILE4REC.Y2 := -10;

                  SEEK (FILEVAR4,FILESIZE(FILEVAR4)-1);  { LAST RECORD IN FILE }
                  WRITE (FILEVAR4,FILE4REC);

                  { BUILD SECOND GRAPH HEADER }

                  FILE4REC.X1 := SXLOW;
                  FILE4REC.Y1 := SYLOW;
                  FILE4REC.Z1 := SZLOW;
                  FILE4REC.X2 := SXHIGH;
                  FILE4REC.Y2 := SYHIGH;
                  FILE4REC.Z2 := SZHIGH;
                  FILE4REC.LINE_TYPE := NUMBER_OF_VERTICIES;
                  WRITE(FILEVAR4,FILE4REC);

                  FILE4REC.Z1 := 0.0;
                  FILE4REC.Z2 := 0.0;
                  FILE4REC.LINE_TYPE := 1;

                  FOR I := 1 TO NUMBER_OF_VERTICIES-1 DO
                    BEGIN
                      FILE4REC.X1 := XAR[I];
                      FILE4REC.Y1 := YAR[I];
                      FILE4REC.X2 := XAR[I+1];
                      FILE4REC.Y2 := YAR[I+1];
                      WRITE(FILEVAR4,FILE4REC);
                    END;  { FOR I = 1 TO NUMBER OF VERTICIES }

                  { WRITE OUT THE TRAILING RECORD }

                  FILE4REC.X1 := 0.0;
                  FILE4REC.Y1 := 0.0;
                  FILE4REC.X2 := 0.0;
                  FILE4REC.Y2 := 0.0;
                  FILE4REC.LINE_TYPE := 0;
                  WRITE(FILEVAR4,FILE4REC);

                END;  { IF KEYVALUE = 'Y' }

            END;  { IF REPLAYFILE <> '' }

          KEYBOARD_PAUSE;

          IF STUDYOPEN  THEN CLOSE(FILEVAR3);
          IF REPLAYOPEN THEN CLOSE(FILEVAR4);

          KEYVALUE := 'R';

        END; { IF DRAWCHAR = Y }

    CLOSE (FILEVAR2);

    { CHECK AND PRINT RESULTS }

    IF PRINTCHAR IN ['B','P'] THEN
      BEGIN
        WRITELN (LST);
        WRITE (LST,'SAMPLE SIZE ',NCOUNT:5,' VERTICIES ',
               NUMBER_OF_VERTICIES:5,' SPLIT ',NCOUNT);
        WRITELN (LST,' NUMBER OF POINTS READ: ',POINTSREAD:5);
        FOR I := 1 TO NUMBER_OF_VERTICIES DO
          WRITELN (LST,XAR[I]:10:5,YAR[I]:10:5);
        WRITELN (LST);

       IF AREA <= 10000 THEN
         WRITELN(LST,'                        AREA: ',AREA:10:5,' Square meters')
       ELSE
         WRITELN(LST,'                        AREA: ',AREAK:10:5,' Square kilometers');

      END; { IF PRINTCHAR IN ['B','P'] }


   END;  { CONVEX_HULL PROCEDURE }

BEGIN  { CONVEX_HULL_MENU }

  { Display the options menu for the convex hull procedure }

  KEYVALUE := 'R';

  WHILE KEYVALUE = 'R' DO
  BEGIN

  CLRSCR;
  DISPLAY_COLOR(CYAN);

  LINE_OUT(28,2,'(6) Convex Polygon Algorithm');
  LINE_OUT(10,4,'1  Data file:');
  LINE_OUT(10,6,'2  Study area file:');
  LINE_OUT(10,8,'3  Plot replay file:');
  LINE_OUT(10,10,'4  Text output displayed on:');
  LINE_OUT(10,12,'5  Graphics displayed on screen (Y|N):');
  LINE_OUT(10,14,'6  Area accuracy method (I|G):');
  LINE_OUT(10,16,'7  Width of a grid cell in meters:');
  LINE_OUT(10,18,'8  Scale of your map as meters between adjacent coordinates: ');

  TEXTCOLOR(YELLOW);
  LINE_OUT(24,4,FILEOUT);
  LINE_OUT(30,6,STUDYFILE);
  LINE_OUT(31,8,REPLAYFILE);

  CASE UPCASE(PRINTCHAR) OF
    'D' : PRINTSTR := 'DISPLAY ONLY';
    'P' : PRINTSTR := 'PRINTER ONLY';
    'B' : PRINTSTR := 'BOTH DISPLAY AND PRINTER';
  END;

  LINE_OUT(39,10,PRINTSTR);

  IF DRAWCHAR = 'N'
    THEN DRAWSTR := 'NO'
    ELSE DRAWSTR := 'YES';

  LINE_OUT(49,12,DRAWSTR);

  { FOR NOW, THE BUG OF INTRGRATION ONLY *****************}
  PRECISION := 'I';

  IF PRECISION = 'I'
    THEN LINE_OUT(41,14,'Integration')
    ELSE LINE_OUT(41,14,'Grid Cell Count');

  GOTOXY(45,16);
  WRITE (SECTION_VALUE:8:4);

  GOTOXY(71,18);
  WRITE (METER_VALUE:8:4);

  DISPLAY_COLOR(RED);

  LINE_OUT(37,21,'E  Exit to Main Menu');
  LINE_OUT(7,21,'P  Process Data');

  TEXTCOLOR(YELLOW);
  GOTOXY(1,24);

  KEYVALUE := ' ';

  WHILE NOT (UPCASE(KEYVALUE) IN ['E','R']) DO
    BEGIN

      KEYVALUE := ' ';
      WHILE NOT (UPCASE(KEYVALUE) IN ['1'..'8','E','P']) DO
        READ (KBD,KEYVALUE);
      KEYVALUE := UPCASE(KEYVALUE);

      GOTOXY(1,23);
      DELLINE;
      DELLINE;

      CASE KEYVALUE OF
        '1': MENU_CALL(1);        { INPUT DATA FILE }
        '2': MENU_CALL(2);        { STUDY AREA FILE }
        '3': MENU_CALL(3);        { REPLAY FILE }
        '4': MENU_CALL(4);        { TEXT ON B, D, P }
        '5': MENU_CALL(5);        { GRAPHICS ON SCREEN? }
  {     '6': MENU_CALL(6);  }     { TYPE OF AREA ACCURACY }
        '7': MENU_CALL(7);        { WIDTH OF GRID CELL }
        '8': MENU_CALL(8);        { DISTANCE FROM 1.0 TO 2.0 }
        'P': BEGIN
             KEEP_GOING := TRUE;
             STUDYOPEN := FALSE;
             REPLAYOPEN := FALSE;

             PROCESSING_VERIFY;

             IF (KEEP_GOING) AND (SECTION_VALUE <= 0.0) THEN
               BEGIN
                 LINE_OUT(1,23,'A grid cell value greater than 0 must be given.');
                 KEEP_GOING := FALSE;
               END;

             IF (KEEP_GOING) AND (METER_VALUE <= 0.0) THEN
               BEGIN
                 LINE_OUT(1,23,'The distance from 1.0 to 2.0 must be given.');
                 KEEP_GOING := FALSE;
               END;

             IF KEEP_GOING THEN
               BEGIN
                 CLRSCR;
                 CONVEX_HULL;
                 END;

             END; { CASE 'P' }

       END; { CASE KEYVALUE }

       GOTOXY(1,23);

   END; { WHILE NOT (KEYVALUE IN ['E','R'] }

 END; { WHILE KEYVALUE = 'R' }

 KEYVALUE := ' ';
END; { CONVEX_HULL_MENU PROCEDURE }