Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 2

COMP9021, Trimester 1, 2022

1.  General matter

1.1. Aims. The purpose of the assignment is to:

design and implement an interface based on the desired behaviour of an application program; practice the use of Python syntax;

develop problem solving skills.

1.2. Submission. Your program will be stored in a file named polygons .py.  After you have developed and tested your program, upload it using Ed (unless you worked directly in Ed).  Assignments can be submitted more than once; the last version is marked. Your assignment is due by April 25, 10:00am.

1.3. Assessment. The assignment is worth 13 marks. It is going to be tested against a number of input files. For each test, the automarking script will let your program run for 30 seconds.

Late assignments will be penalised: the mark for a late submission will be the minimum of the awarded mark and 10 minus the number of full and partial days that have elapsed from the due date.

1.4. Reminder on plagiarism policy. You are permitted, indeed encouraged, to discuss ways to solve the assignment with other people.   Such discussions must be in terms of algorithms, not code.   But you must implement the solution on your own. Submissions are routinely scanned for similarities that occur when students copy and modify other people’s work, or work very closely together on a single implementation. Severe penalties apply.

2.  General presentation

You will design and implement a program that will

extract and analyse the various characteristics of (simple) polygons, their contours being coded and stored in a file, and

either display those characteristics:  perimeter, area, convexity, number of rotations that keep the polygon invariant, and depth (the length of the longest chain of enclosing polygons)

– or output some Latex code, to be stored in a file, from which a pictorial representation of the polygons can be produced, coloured in a way which is proportional to their area.

Call encoding any 2-dimensional grid of size between between 2 2 and 50 50  (both dimensions can be different) all of whose elements are either 0 or 1.

Call neighbour of a member m of an encoding any of the at most eight members of the grid whose value is 1 and each of both indexes differs from m’s corresponding index by at most 1.  Given a particular encoding, we inductively define for all natural numbers d the set of polygons of depth d (for this encoding) as follows. Let a natural number d be given, and suppose that for all d0  < d, the set of polygons of depth d0 has been defined. Change in the encoding all 1’s that determine those polygons to 0. Then the set of polygons of depth d is defined as the set of polygons which can be obtained from that encoding by connecting 1’s with some of their neighbours in such a way that we obtain a maximal polygon (that is, a polygon which is not included in any other polygon obtained from that encoding by connecting 1’s with some of their neighbours).

3. Examples

3.1. First example. The file polys_1 .txt has the following contents:

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

11111111111111111111111111111111111111111111111111

Here is a possible interaction:

$  python3

...

>>>  from  polygons  import  *

>>>  polys  =  Polygons('polys_1 .txt')

>>>  polys .analyse()

Polygon  1:

Perimeter:  78 .4

Area:  384 .16

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  0

Polygon  2:

Perimeter:  75 .2

Area:  353 .44

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  1

Polygon  3:

Perimeter:  72 .0

Area:  324 .00

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  2

Polygon  4:

Perimeter:  68 .8

Area:  295 .84

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  3

Polygon  5:

Perimeter:  65 .6

Area:  268 .96

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  4

Polygon  6:

Perimeter:  62 .4

Area:  243 .36

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  5

Polygon  7:

Perimeter:  59 .2

Area:  219 .04

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  6

Polygon  8:

Perimeter:  56 .0

Area:  196 .00

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  7

Polygon  9:

Perimeter:  52 .8 Area:  174 .24

Convex:  yes        Nb  of  invariant Depth:  8

Polygon  10:                Perimeter:  49 .6 Area:  153 .76

Convex:  yes        Nb  of  invariant Depth:  9

Polygon  11:                Perimeter:  46 .4 Area:  134 .56

Convex:  yes        Nb  of  invariant Depth:  10

Polygon  12:                Perimeter:  43 .2 Area:  116 .64

Convex:  yes        Nb  of  invariant Depth:  11

Polygon  13:                Perimeter:  40 .0 Area:  100 .00

Convex:  yes        Nb  of  invariant Depth:  12

Polygon  14:                Perimeter:  36 .8 Area:  84 .64

Convex:  yes        Nb  of  invariant Depth:  13

Polygon  15:                Perimeter:  33 .6 Area:  70 .56

Convex:  yes        Nb  of  invariant Depth:  14

Polygon  16:                Perimeter:  30 .4 Area:  57 .76

Convex:  yes        Nb  of  invariant Depth:  15

Polygon  17:                Perimeter:  27 .2 Area:  46 .24

Convex:  yes        Nb  of  invariant

Depth:  16

Polygon  18:

Perimeter:  24 .0

Area:  36 .00

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  17

Polygon  19:

Perimeter:  20 .8

Area:  27 .04

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  18

Polygon  20:

Perimeter:  17 .6

Area:  19 .36

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  19

Polygon  21:

Perimeter:  14 .4

Area:  12 .96

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  20

Polygon  22:

Perimeter:  11 .2

Area:  7 .84

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  21

Polygon  23:

Perimeter:  8 .0

Area:  4 .00

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  22

Polygon  24:

Perimeter:  4 .8

Area:  1 .44

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  23

Polygon  25:

Perimeter:  1 .6

Area:  0 .16

Convex:  yes

Nb  of  invariant  rotations:  4

Depth:  24

>>>  polys .display()

The effect of executing polys .display() is to produce a file named polys_1 .tex that can be given as argument to pdflatex to produce a file named polys_1 .pdf that views as follows.

3.2. Second example. The file polys_2 .txt has the following contents:

00000000000000000000000000000000000000000000000000

01111111111111111111111111111111111111111111111110

00111111111111111111111111111111111111111111111100

00011111111111111111111111111111111111111111111000

01001111111111111111111111111111111111111111110010

01100111111111111111111111111111111111111111100110

01110011111111111111111111111111111111111111001110

01111001111111111111111111111111111111111110011110

01111100111111111111111111111111111111111100111110

01111110011111111111111111111111111111111001111110

01111111001111111111111111111111111111110011111110

01111111100111111111111111111111111111100111111110

01111111110011111111111111111111111111001111111110

01111111111001111111111111111111111110011111111110

01111111111100111111111111111111111100111111111110

01111111111110011111111111111111111001111111111110

01111111111111001111111111111111110011111111111110

01111111111111100111111111111111100111111111111110

01111111111111110011111111111111001111111111111110

01111111111111111001111111111110011111111111111110

01111111111111111100111111111100111111111111111110

01111111111111111110011111111001111111111111111110

01111111111111111111001111110011111111111111111110

01111111111111111111100111100111111111111111111110

01111111111011111111110011001111111111011111111110

01111111111111111111100111100111111111111111111110

01111111111111111111001111110011111111111111111110

01111111111111111110011111111001111111111111111110

01111111111111111100111111111100111111111111111110

01111111111111111001111111111110011111111111111110

01111111111111110011111111111111001111111111111110

01111111111111100111111111111111100111111111111110

01111111111111001111111111111111110011111111111110

01111111111110011111111111111111111001111111111110

01111111111100111111111111111111111100111111111110

01111111111001111111111111111111111110011111111110

01111111110011111111111111111111111111001111111110

01111111100111111111111111111111111111100111111110

01111111001111111111111111111111111111110011111110

01111110011111111111111111111111111111111001111110

01111100111111111111111111111111111111111100111110

01111001111111111111111111111111111111111110011110

01110011111111111111111111111111111111111111001110

01100111111111111111111111111111111111111111100110

01001111111111111111111111111111111111111111110010

00011111111111111111111111111111111111111111111000

00111111111111111111111111111111111111111111111100

01111111111111111111111111111111111111111111111110

00000000000000000000000000000000000000000000000000

Here is a possible interaction:

$  python3

...

>>>  from  polygons  import  *

>>>  polys  =  Polygons('polys_2 .txt')

>>>  polys .analyse()

Polygon  1:

Perimeter:  37 .6  +  92*sqrt( .32)

Area:  176 .64

Convex:  no

Nb  of  invariant  rotations:  2

Depth:  0

Polygon  2:

Perimeter:  17 .6  +  42*sqrt( .32)

Area:  73 .92

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  1

Polygon  3:

Perimeter:  16 .0  +  38*sqrt( .32)

Area:  60 .80

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  2

Polygon  4:

Perimeter:  16 .0  +  40*sqrt( .32)

Area:  64 .00

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  0

Polygon  5:

Perimeter:  14 .4  +  34*sqrt( .32)

Area:  48 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  3

Polygon  6:

Perimeter:  16 .0  +  40*sqrt( .32)

Area:  64 .00

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  0

Polygon  7:

Perimeter:  12 .8  +  30*sqrt( .32)

Area:  38 .40

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  4

Polygon  8:

Perimeter:  14 .4  +  36*sqrt( .32)

Area:  51 .84

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  1

Polygon  9:

Perimeter:  11 .2  +  26*sqrt( .32)

Area:  29 .12

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  5

Polygon  10:

Perimeter:  14 .4  +  36*sqrt( .32)

Area:  51 .84

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  1

Polygon  11:

Perimeter:  9 .6  +  22*sqrt( .32)

Area:  21 .12

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  6

Polygon  12:

Perimeter:  12 .8  +  32*sqrt( .32)

Area:  40 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  2

Polygon  13:

Perimeter:  8 .0  +  18*sqrt( .32)

Area:  14 .40

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  7

Polygon  14:

Perimeter:  12 .8  +  32*sqrt( .32)

Area:  40 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  2

Polygon  15:

Perimeter:  6 .4  +  14*sqrt( .32)

Area:  8 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  8

Polygon  16:

Perimeter:  11 .2  +  28*sqrt( .32)

Area:  31 .36

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  3

Polygon  17:

Perimeter:  4 .8  +  10*sqrt( .32)

Area:  4 .80

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  9

Polygon  18:

Perimeter:  11 .2  +  28*sqrt( .32)

Area:  31 .36

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  3

Polygon  19:

Perimeter:  3 .2  +  6*sqrt( .32)

Area:  1 .92

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  10

Polygon  20:

Perimeter:  9 .6  +  24*sqrt( .32)

Area:  23 .04

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  4

Polygon  21:

Perimeter:  1 .6  +  2*sqrt( .32)

Area:  0 .32

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  11

Polygon  22:

Perimeter:  9 .6  +  24*sqrt( .32)

Area:  23 .04

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  4

Polygon  23:

Perimeter:  8 .0  +  20*sqrt( .32)

Area:  16 .00

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  5

Polygon  24:

Perimeter:  8 .0  +  20*sqrt( .32)

Area:  16 .00

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  5

Polygon  25:

Perimeter:  6 .4  +  16*sqrt( .32)

Area:  10 .24

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  6

Polygon  26:

Perimeter:  6 .4  +  16*sqrt( .32)

Area:  10 .24

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  6

Polygon  27:

Perimeter:  4 .8  +  12*sqrt( .32)

Area:  5 .76

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  7

Polygon  28:

Perimeter:  4 .8  +  12*sqrt( .32)

Area:  5 .76

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  7

Polygon  29:

Perimeter:  3 .2  +  8*sqrt( .32)

Area:  2 .56

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  8

Polygon  30:

Perimeter:  3 .2  +  8*sqrt( .32)

Area:  2 .56

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  8

Polygon  31:

Perimeter:  1 .6  +  4*sqrt( .32)

Area:  0 .64

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  9

Polygon  32:

Perimeter:  1 .6  +  4*sqrt( .32)

Area:  0 .64

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  9

Polygon  33:

Perimeter:  17 .6  +  42*sqrt( .32)

Area:  73 .92

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  1

Polygon  34:

Perimeter:  16 .0  +  38*sqrt( .32)

Area:  60 .80

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  2

Polygon  35:

Perimeter:  14 .4  +  34*sqrt( .32)

Area:  48 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  3

Polygon  36:

Perimeter:  12 .8  +  30*sqrt( .32)

Area:  38 .40

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  4

Polygon  37:

Perimeter:  11 .2  +  26*sqrt( .32)

Area:  29 .12

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  5

Polygon  38:

Perimeter:  9 .6  +  22*sqrt( .32)

Area:  21 .12

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  6

Polygon  39:

Perimeter:  8 .0  +  18*sqrt( .32)

Area:  14 .40

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  7

Polygon  40:

Perimeter:  6 .4  +  14*sqrt( .32)

Area:  8 .96

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  8

Polygon  41:

Perimeter:  4 .8  +  10*sqrt( .32)

Area:  4 .80

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  9

Polygon  42:

Perimeter:  3 .2  +  6*sqrt( .32)

Area:  1 .92

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  10

Polygon  43:

Perimeter:  1 .6  +  2*sqrt( .32)

Area:  0 .32

Convex:  yes

Nb  of  invariant  rotations:  1

Depth:  11

>>>  polys .display()


The effect of executing polys .display() is to produce a file named polys_2 .tex that can be given as argument to pdflatex to produce a file named polys_2 .pdf that views as follows.