Learning Outcomes
Each section of input
npoints poly id xval0
yval0
xval1
yval1
… xvalnpoints−1 yvalnpoints−1
for your program will have the following structure:
the number of boundary points in this polygon
an identifying value for this polygon
the x coordinate of the first point, in meters relative to the origin the y coordinate of the first point, in meters relative to the origin the x coordinate of the second point, in meters relative to the origin the y coordinate of the second point, in meters relative to the origin
the x coordinate of the last point of this polygon the y coordinate of the last point of this polygon
Department of Computing and Information Systems
COMP20005 Engineering Computation Semester 1, 2015
Assignment 1
In this project you will demonstrate your understanding of loops and if statements by writing a program that sequentially processes a file of text data. You are also expected to make use of functions; and in the third stage of the project, will need to make use of arrays (covered in Weeks 6 and 7, and in Chapter 7).
Spatial Data
Spatial data is very important for planning and optimization purposes. Think about how useful Google maps is for navigation and path-finding, and imagine how chaotic the world would become if we didn’t have accurate records of who owned what pieces of land. In this project you will work with (highly simplified) data that represents parcels of land, stored as two-dimensional polygons referenced against an underlying grid.
The points will always be listed in a “clockwise” order relative to points “inside” the polygon.
There may be multiple sections in the input file, describing multiple polygons. In each section, npoints and poly id will be presented as ints, all of the x and y coordinates will be doubles, and all values will be separated by whitespace (so that reading them using “%d” and “%lf” respectively will work just fine). An npoints value of zero will be used to indicate that there are no more polygons in the
input file. For example, the input file test0.txt (available on the LMS)
3 12867 1.0 2.0 1.0 5.0 4.0 5.0
5 15643 1.0 2.0 4.0 5.0 7.8 3.5 5.0 0.4 1.0 0.4
4 18674 1.0 0.4 0.4 0.4 0.4 3.6 1.0 3.6
0
describes three polygons: an isosceles triangle, then an irregular pentagon; and finally a rectangle. Fig- ure 1 shows these three polygons. (If they were actual parcels of land, the numbers would be bigger, of course. A typical suburban house block in Melbourne is around 15.0 × 45.0 meters.) Where it is necessary to do so, you may assume that no polygon will have more than 100 points on its boundary. You may further assume that the input will contain at most 100 polygons in total. In this first example, all of the points are in the first quadrant. You may not assume that this will be true for all inputs, and your program must handle the case when polygons have vertices in all four quadrants, and/or at the origin.
1
5 4 3 2 1
Stage 1 – Processing a Polygon (marks up to 5/10)
You can complete this stage without requiring the use of arrays. However, you may also make use of arrays in this stage if you are confident that you will be proceeding right through to Stage 3.
Write a program that reads the first polygon in the input file, and prints out the points on its perime- ter, together with the length of its perimeter (in meters), the area it covers (in square meters), and its eccentricity (unitless); where eccentricity is defined as the square of the perimeter, divided by the area, and then divided by 4π. A circle has eccentricity (2πr)2/(πr2)/4π = 1.0 (and is the smallest value of eccentricity possible), a square has eccentricity 4/π ≈ 1.27, and so on.
To compute the perimeter, you need to calculate the length of each edge in the usual manner, and add them up. Don’t forget the last edge that closes off the polygon, from ⟨xvalnpoints−1, yvalnpoints−1⟩ back to ⟨xval0, yval0⟩. Working out the area requires a bit more thought. Figure 2 gives some guidance as to how this can be done, and with care, it should be possible to calculate the area as a sum of npoints values (Ai in the diagram), each of which is computed from two adjacent points, ⟨xvali, yvali⟩ and ⟨xvali+1, yvali+1⟩.
For example, this stage should produce:
mac: ./my-ass1 < test0.txt
Stage 1
=======
First polygon is 12867
12867
15643
x_val 1.0 1.0 4.0
y_val 2.0 5.0 5.0
perimeter area eccentricity = 1.86
12345678
Figure 1: Example input with three polygons.
= 10.24 m = 4.50 m^2
As this example illustrates, the best way to get data into your program is to edit it in to a text file (with a .txt extension, jEdit can do this too), and then execute your program from the command-line, feeding the data in via input redirection (using <). You should also construct other test inputs too, of course.
Because all input data will come from a file (including during our post-submission testing), you should not print any prompts at all. You may assume that the input file will always be correctly formatted and will contain at least one correctly described polygon.
2
18674
55 44 33 22
AAA 014
11A2
12345678 12345678
Figure 2: Computing the area of the polygon 15643 in Figure 1 as A0 + A1 + A2 + A3 + A4, where A0 >0,A1 >0,A2 <0,A3 <0,andA4 =0,withAi theareaofatrapezoidalregiontothex-axis.
Stage 2 – Wrapping Another Iteration (marks up to 7/10)
You can also complete this stage without requiring the use of arrays. However, you may use arrays if you are confident that you will be proceeding right through to Stage 3.
Now modify your program so that all of the input polygons are summarized in a table of values: On the same example input file the additional output should be:
Stage 2
=======
+-------+-------+-------+-------+-------+
| id | nval | perim | area | eccen |
+-------+-------+-------+-------+-------+
|
A 3 |
|12867|
|15643|
|18674| +——-+——-+——-+——-+——-+
3|10.24| 4.50| 1.86| 5|18.11|19.59| 1.33| 4| 7.60| 1.92| 2.39|
Note that one of the purposes of this stage is to encourage you to use functions effectively. A complete output file showing all output stages is linked from the LMS page, to make it clear what is required from your program.
Stage 3 – Overall Reporting (marks up to 10/10)
To complete this stage you will need to make use of arrays. If you have completed Stages 1 and 2 without arrays, you should be sure to save a copy of that version of your program in to a separate file, as an insurance policy that can be submitted again later if you are unable to get your Stage 3 solution operational.
The additional output from this stage is a listing of the points of the polygon with the largest area of the ones that were in the input. In the case of ties of area, the largest-area polygon with the smallest poly id should be selected and output.
Stage 3
=======
Largest polygon is 15643
x_val y_val
1.0 2.0
4.0 5.0
3
7.8 3.5
5.0 0.4
1.0 0.4
Hint: you don’t need to use a two-dimensional array. But you will need to employ one or more one- dimensional arrays to correctly compute the required output.
Wherever appropriate, code should be shared between the stages through the use of functions. In particular, there shouldn’t be long (or even short) stretches of repeated or similar code appearing in different places in your program.
Further examples showing the full output that is required are provided on the LMS.
Purely for Fun (and not for submission)
If you aren’t exhausted yet, and don’t have any work to do in other subjects, try this (quite tricky) problem – if these polygons really do represent parcels of land, then it is fine for them to share boundaries (as is shown in Figure 1). But they mustn’t overlap. Add functionality in to your program that pairwise tests the input polygons and provides an error message if any polygons overlap with each other. But please don’t submit these programs.
The boring stuff…
This project is worth 10% of your final mark. A rubric explaining the marking expectations will be provided on the LMS.
You need to submit your program for assessment; detailed instructions on how to do that will be posted on the LMS once submissions are opened. Submission will not be done via the LMS; instead you will need to log in to a Unix server and submit your files to a software system known as submit. You can (and should) use submit both early and often – to get used to the way it works, and also to check that your program compiles correctly on our test system, which has some different characteristics to the lab machines. Failure to follow this simple advice is highly likely to result in tears. Only the last submission that you make before the deadline will be marked.
You may discuss your work during your workshop, and with others in the class, but what gets typed into your program must be individual work, not copied from anyone else. So, do not give hard copy or soft copy of your work to anyone else; do not “lend” your memory stick to others; and do not ask others to give you their programs “just so that I can take a look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions in “compare every pair” mode. See https://academichonesty.unimelb.edu.au for more information.
Deadline: Programs not submitted by 10:00am on Monday 27 April will lose penalty marks at the rate of two marks per day or part day late. Students seeking extensions for medical or other “outside my control” reasons should email ammoffat@unimelb.edu.au as soon as possible after those circum- stances arise. If you attend a GP or other health care professional as a result of illness, be sure to take a Health Professional Report form with you (get it from the Special Consideration section of the Stu- dent Portal), you will need this form to be filled out if your illness develops in to something that later requires a Special Consideration application to be lodged. You should scan the HPR form and send it in connection with any non-Special Consideration assignment extension requests.
Marks and a sample solution will be available on the LMS by Monday 11 May.
And remember, programming is fun!
4