Python代写:COMP9021-Polygons

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 dierent) 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 diers 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).

Assessment

The request is worth 10 marks. the automarking script will allocate 30 seconds to each run of your program.

Late requests 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.

The outputs of your programs should be exactly as indicated.

Examples

First example

Given a file named polys_1.txt whose contents is

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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

your program when run as python3 polygons.py –file polys_1.txt should output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
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 rotations: 4
Depth: 8
Polygon 10:
Perimeter: 49.6
Area: 153.76
Convex: yes
Nb of invariant rotations: 4
Depth: 9
Polygon 11:
Perimeter: 46.4
Area: 134.56
Convex: yes
Nb of invariant rotations: 4
Depth: 10
Polygon 12:
Perimeter: 43.2
Area: 116.64
Convex: yes
Nb of invariant rotations: 4
Depth: 11
Polygon 13:
Perimeter: 40.0
Area: 100.00
Convex: yes
Nb of invariant rotations: 4
Depth: 12
Polygon 14:
Perimeter: 36.8
Area: 84.64
Convex: yes
Nb of invariant rotations: 4
Depth: 13
Polygon 15:
Perimeter: 33.6
Area: 70.56
Convex: yes
Nb of invariant rotations: 4
Depth: 14
Polygon 16:
Perimeter: 30.4
Area: 57.76
Convex: yes
Nb of invariant rotations: 4
Depth: 15
Polygon 17:
Perimeter: 27.2
Area: 46.24
Convex: yes
Nb of invariant rotations: 4
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

and when run as python3 polygons.py -print –file polys_1.txt should produce some output saved in a file named polys_1.tex, which can be given as argument to pdflatex to produce a file named polys_1.pdf that views as follows.

Detailed description

Input

The input is expected to consist of ydim lines of xdim 0’s and 1’s, where xdim and ydim are at least equal to 2 and at most equal to 50, with possibly lines consisting of spaces only that will be ignored and with possibly spaces anywhere on the lines with digits. If n is the xth digit of the yth line with digits, with 0 < x < xdim and 0 < y < ydim, then n is to be associated with a point situated x 0.4 cm to the right and y 0.4 cm below an origin.

Output

The program should be run as either

1
python3 polygons.py --file filename.txt

or as

1
python3 polygons.py -print --file filename.txt

(where filename.txt is the name of a file that stores the input). You can study the program ascii_art.py from Lecture 7 to find out how this can be done.

If the input is incorrect, that is, does not satisfy the conditions spelled out in the previous section, then the program should print out a single line that reads

1
Incorrect input.

and immediately exit.

When the program is run without -print as command-line argument

If the input is correct, then the program should output a first line that reads one of

1
Cannot get polygons as expected.

in case it is not possible to use all 1’s in the input and make them the contours of polygons of depth d, for any natural number d, as defined in the general presentation.

Otherwise, the program should output a first line that reads

1
Polygon N:

with N an appropriate integer at least equal to 1 to refer to the N’th polygon listed in the order of polygons with highest point from smallest value of y to largest value of y, and for a given value of y, from smallest value of x to largest value of x, a second line that reads one of

1
2
3
Perimeter: a + b*sqrt(.32)
Perimeter: a
Perimeter: b*sqrt(.32)

with a an appropriate strictly positive floating point number with 1 digit after the decimal point and b an appropriate strictly positive integer, a third line that reads

1
Area: a

with a an appropriate floating point number with 2 digits after the decimal point, a fourth line that reads one of

1
2
Convex: yes
Convex: no