At this moment, you are not allowed access to the question.

Task 5. Gift Wrapping

Available Marks: 19

Given the cartesian coordinates (x, y) of a set of at least three points, the convex hull of the set is a sequence of a subset of the points that forms a convex polygon enclosing all the other points. A convex polygon has interior angles less than 180 degrees. Thus the convex hull of a star shape comprises the tips rather than the whole outline. The hull encloses the set like wrapping a present.

Several algorithms exist to generate the convex hull, but you are encouraged to use the simplest of them, published by RA Jarvis in 1973. The Jarvis algorithm starts with the leftmost point p₀ and computes the angles to every other point. The one with the smallest angle (relative to an upward vertical line) is the next on the hull. Repeat using the p₀ to p₁ vector to find p₂ and so on (see diagram). The hull is complete when you reach p₀ again.

Your task

Write a program that calculates the convex hull of a set of points. The program must read a file in the following format and output a similar file with valid convex hull section and (for full marks) correct area section. This file format is used by an online mapping application that you can use to view the original data and to verify your results.

title string points x y x y ... convex hull p0 p1 p2 ... area areaofhull end

• Points are pairs of real numbers separated by a space, one pair per line. They are in arbitrary order.
• Points are identified by their position in the list. Indexes start at zero.
• Each point on the convex hull is indicated by its index. The points must be in clockwise order. Indexes are separated by spaces and spread over one or more lines.
• The area of the hull (see below), if included in your result, follows the hull section.

Example

Input:

title Trapezium with central point points 33.1 4 53.7 58.3 45.4 36.3 5.5 51.2 72.1 26.6 end

Output:

title Trapezium with central point points 33.1 4 53.7 58.3 45.4 36.3 5.5 51.2 72.1 26.6 convex hull 3 1 4 0 3 area 2061.57 end

Area Calculation

For 4 marks of the available 19, calculate the area A of the convex hull using the Gauss-Green (or Shoelace) formula below. The formula applies to any n-point polygon, with coordinates indexed 0 to n–1. For the purposes of calculation, point n is the same as point 0.

The area should be displayed with at least 6 significant figures.

Assumptions

• There are no more than 100 points.
• No three points on the hull are collinear (exactly in a straight line). In its simplest form Jarvis' algorithm doesn't deal with collinearity.
• Coordinates and intermediate calculations are all expressible in double precision without overflow.

Test Cases

There are two test cases, the first contains coordinates of buildings and perimeter points on the 40ha UNSW Kensington campus, the second is a roughly circular 100-point cluster.

Test 1		Test 2
title UNSW Kensington Campus points 3360.25 62456.08 3369.57 62456.97 3360.70 62454.75 3364.15 62453.67 3361.80 62458.28 3369.22 62454.28 3365.69 62454.97 3363.40 62457.69 3367.82 62457.45 3359.69 62458.62 3360.81 62456.85 3366.44 62456.83 3366.94 62455.45 3360.25 62458.22 3367.96 62456.44 3369.04 62454.72 3364.19 62456.01 3363.70 62453.29 3363.89 62454.92 3360.72 62453.77 3366.31 62454.97 3361.87 62454.82 3365.36 62452.96 3367.98 62457.35 3368.24 62457.28 3365.25 62452.95 3360.72 62453.77 end		title Cluster 100 points 3937.2 2579.9 4128.1 5160.3 2501.1 3900.7 2058.1 3792.7 5784.5 4456.7 2495.0 4258.2 6444.7 6895.8 3836.9 3711.3 4698.5 2713.9 1963.8 3341.7 7055.1 4802.6 6488.8 1429.1 2185.0 2024.8 5966.3 7293.0 2833.1 2250.8 5804.4 5547.1 2384.0 5385.0 5677.9 4897.5 7321.8 3517.0 7032.0 5483.0 1910.0 6330.1 4579.2 4061.6 4531.6 2181.5 3205.3 2431.5 4139.0 5627.0 1516.4 3047.5 5328.0 5934.1 3372.4 5310.8 1373.5 1460.4 7009.8 5250.8 3196.0 6017.7 5777.5 4677.8 1711.6 1989.4 6716.6 5535.6 2817.8 5453.3 6854.3 6470.0 2468.6 1374.7 3673.3 4601.4 3031.7 4640.9 3709.2 3622.5 1317.1 1877.8 4205.4 4891.3 5542.6 6735.4 5956.5 4213.6 4565.8 3314.1 6710.6 6949.5 5378.2 1093.7 5028.0 6002.0 2440.1 7173.7 3524.7 5062.5 6166.9 6043.8 4433.3 3794.7 2126.7 1126.6 5661.2 2393.7 5781.9 5739.3 2737.5 1918.1 2838.7 6536.2 2434.3 1723.0 2827.5 2566.0 3741.7 4316.9 5707.6 3203.5 4336.1 6787.1 1104.4 5002.4 1122.7 6025.4 7072.5 2370.6 5980.7 5516.1 4092.2 2465.6 6030.1 4060.9 4180.5 1309.1 1389.0 4777.1 5797.9 5845.4 3781.7 2215.5 4764.4 6848.2 1223.0 2365.1 4379.0 4387.5 1323.2 4309.8 3339.5 3168.1 7120.1 1261.3 1917.5 5886.2 7133.7 4407.0 6968.6 6409.5 3156.5 6743.0 4324.6 1143.6 5657.7 2969.4 4783.7 2114.3 6606.6 1616.5 2857.7 7174.7 6667.3 3429.5 2152.7 3643.4 3397.4 3670.7 6224.1 2165.6 2753.6 2602.2 6304.1 6183.1 2941.0 2826.6 6256.3 2857.4 5741.1 3095.1 5830.9 5884.7 3796.5 1968.8 5091.1 6746.8 5101.9 1960.6 end

Step 0

Refresh the browser window if the page has been idle for some time.

Step 1

Cut and paste the output of your program for each of the test cases into the box below:

Test 1 output (complete file): Test 2 output (complete file):

Step 2

Paste the source code for your program into the box below.

Paste your code here.

Step 3

When you are sure all the data has been entered correctly on the form press the submit button below.

You may submit multiple times. Only your most recent submission for each question will be marked.