# Convex Hull in Commodore Basic

Published on 15 October 2023 (Updated: 15 October 2023)

Welcome to the Convex Hull in Commodore Basic page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

``````10 DIM A(99), P(99, 1), H(99, 1)
15 REM Get x values
20 GOSUB 2000
30 IF V = 0 OR C <> -1 THEN GOTO 200: REM invalid or not end of value
40 NP = NA
50 FOR I = 0 TO NA - 1
60     P(I, 0) = A(I)
70 NEXT I
75 REM Get y values
80 GOSUB 2000
90 IF V = 0 OR C >= 0 THEN GOTO 200: REM invalid or not end input/value
100 FOR I = 0 TO NA - 1
110    P(I, 1) = A(I)
120 NEXT I
125 REM Validate number of x and y values
130 IF NP <> NA OR NP < 3 THEN GOTO 200
135 REM Perform convex hull and show results
140 GOSUB 3000
150 GOSUB 3500
160 END
200 Q\$ = CHR\$(34): REM quote
210 PRINT "Usage: please provide at least 3 x and y coordinates as separate ";
220 PRINT "lists (e.g. "; Q\$; "100, 440, 210"; Q\$; ")"
230 END
1000 REM Read input value one character at a time since Commodore BASIC
1001 REM has trouble reading line from stdin properly
1002 REM NR = number
1003 REM V = 1 if valid number, 0 otherwise
1004 REM C = -2 if end of input, -1 if end of value,
1005 REM   32 if whitespace, ASCII code of last character otherwise
1006 REM Initialize
1010 NR = 0
1020 V = 0
1030 S = 1
1035 REM Loop while leading spaces
1040 GOSUB 1500
1050 IF C = 43 OR C = 45 THEN GOTO 1100: REM + or -
1060 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1070 IF C = 32 THEN GOTO 1040: REM whitespace
1080 RETURN: REM other character
1085 REM Loop while sign
1090 GOSUB 1500
1100 IF C = 43 THEN GOTO 1090: REM +
1110 IF C >= 48 AND C <= 57 THEN GOTO 1150: REM 0 to 9
1120 IF C <> 45 THEN RETURN: REM not -
1130 S = -S
1140 GOTO 1090
1145 REM Set valid flag
1150 V = 1
1155 REM Loop while digits
1160 NR = (ABS(NR) * 10 + C - 48) * S
1170 GOSUB 1500
1180 IF C >= 48 AND C <= 57 THEN GOTO 1160: REM 0 to 9
1185 REM Loop while trailing spaces
1190 IF C < 0 OR C <> 32 THEN RETURN: REM end character or not whitespace
1200 GOSUB 1500
1210 GOTO 1180
1500 REM Get input character
1501 REM A\$ = input character
1502 REM C = One of the following:
1502 REM - -1 if end of value
1503 REM - -2 if end of input
1504 REM - 32 if whitespace
1505 REM - ASCII code otherwise
1510 GET A\$
1520 C = ASC(A\$)
1530 IF C = 13 THEN C = -1
1540 IF C = 255 THEN C = -2
1550 IF C = 9 OR C = 10 THEN C = 32
1560 RETURN
2001 REM A contains array value
2002 REM NA contains length of array
2003 REM V = 1 if valid number, 0 otherwise
2004 REM C = -2 if end of input, -1 if end of value,
2005 REM   32 if whitespace, ASCII code of last character otherwise
2006 REM Initialize
2010 NA = 0
2020 GOSUB 1000: REM Read input value
2030 IF V = 0 THEN RETURN: REM invalid
2040 A(NA) = NR
2050 NA = NA + 1
2060 IF C < 0 THEN RETURN: REM end of input or value
2070 IF C = 44 THEN GOTO 2020: REM comma, get next value
2080 V = 0
2090 RETURN
3000 REM Find Convex Hull using Jarvis' algorithm
3001 REM Source:
3002 REM https://www.geeksforgeeks.org/
3003 REM convex-hull-using-jarvis-algorithm-or-wrapping/
3004 REM Inputs:
3005 REM - P contains points
3006 REM - NP contains number of points
3007 REM Outputs:
3008 REM - H contains hull points
3009 REM - NH contains number of hull points
3010 REM Initialize hull points
3020 NH = 0
3030 REM The first point is the leftmost point with the highest y-coord in the
3040 REM event of a tie
3050 LI = 0
3070 FOR I = 1 TO NP - 1
3080     IF P(I, 0) < P(LI, 0) THEN GOTO 3100
3090     IF P(I, 0) <> P(LI, 0) OR P(I, 1) <= P(LI, 1) THEN GOTO 3110
3100     LI = I
3110 NEXT I
3120 PI = LI
3125 REM Store hull point
3130 H(NH, 0) = P(PI, 0)
3140 H(NH, 1) = P(PI, 1)
3150 NH = NH + 1
3155 REM Update end point if point found is more counter-clockwise
3160 QI = PI + 1
3170 IF QI >= NP THEN QI = QI - NP
3180 FOR J = 0 TO NP -1
3181     REM Determine orientation:
3182     REM - 0 means points in a line
3183     REM - > 0 means points are clockwise
3184     REM - < 0 mean points are counter-clockwise
3190     O = (P(J, 1) - P(PI, 1)) * (P(QI, 0) - P(J, 0))
3200     O = O - (P(J, 0) - P(PI, 0)) * (P(QI, 1) - P(J, 1))
3210     IF O < 0 THEN QI = J
3220 NEXT J
3225 REM Repeat until wrapped to first hull point
3230 PI = QI
3240 IF PI <> LI THEN GOTO 3130
3250 RETURN
3500 REM Display hull points
3501 REM Inputs:
3502 REM - H contains hull points
3503 REM - NH contains number of hull points
3510 IF NA < 1 THEN GOTO 3590
3520 FOR I = 0 TO NH - 1
3530    SX\$ = STR\$(H(I, 0))
3540    IF H(I, 0) >= 0 THEN SX\$ = MID\$(SX\$, 2): REM strip leading space
3550    SY\$ = STR\$(H(I, 1))
3560    IF H(I, 1) >= 0 THEN SY\$ = MID\$(SY\$, 2): REM strip leading space
3570    PRINT "("; SX\$; ", "; SY\$; ")"
3580 NEXT I
3590 RETURN

``````

Convex Hull in Commodore Basic was written by:

• rzuckerm

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.