Introduction
2019 Semester 1
COMP20007 Design of Algorithms School of Computing and Information Systems The University of Melbourne
Assignment 1: Convex Hull Due: 11:59 PM Thursday April 11th
A set S in the plane is called convex if it satisfies the following property: for every pair of points p, q S the line segment between them pq is also in the set S (i.e., pq S).
One problem that comes up time and time again in areas such as computational geometry is the problem of finding the smallest convex set S which contains all points in some other set X. This set is called the convex hull of X.
When given some set of points we can describe the convex hull S by listing the points which make up the vertices in the boundary of the convex hull.
Figure 1: A set of points and the boundary of their corresponding convex hull, which is coloured in grey.
Levitin Section 3.3: Closest-Pair and Convex-Hull Problems by Brute Force provides a more compre- hensive description and discussion of the convex hull problem.
In this assignment you will implement an algorithm to compute the convex hull of a given set of points.
The assignment consists of 3 (three) coding tasks (Part A, Part C and Part F) and 4 (four) analysis tasks (Part B, Part D, Part E and Part G).
1
Tasks
Part A: Point Orientation
Let p0,p1,p2 be three points in the plane. If p2 is left of the line segment p0p1, then we write Left(p0, p1, p2). If p2 is right of the line segment p0p1, then we write Right(p0, p1, p2). If three points are on the same straight line, then we say that (p0,p1,p2) are collinear.
p3
p1 p3
p1
(a)
p2
p0
(b)
p2
Figure 2:
are all collinear points, so we say that each 3-subset of the four points are collinear e.g., p0, p2 and p3 are collinear.
Your task is to complete the implementation of orientation() in convex-hull.c which takes three points (p0, p1 and p2) and returns l if p2 is Left of p0p1, r if p2 is Right of p0p1 or c if p0,p1 and p2 are Collinear.
Your function must run in O(1) time.
Hint: check out Appendix A which describes a number of useful vector operations.
Part B: Checking for Convexity
Let P = (p0, . . . , pn1) be a sequence of n points in the Euclidean plane (R2). Assume you have been given the following algorithm:
function isConvex(p0, . . . , pn1) for i 0 to n 1 do
if Right(pi, p(i+1) mod n, p(i+2) mod n) then return false
return true
Update: the return true was previously incorrectly indented so that it was inside the for loop. This
has been corrected.
Does the algorithm above correctly determine if P is the boundary of a convex polygon in counter- clockwise order? Explain your answer.
The Inside Hull Algorithm
A polygon is called simple if it has no self intersections.
We describe a convex hull algorithm, called InsideHull and abbreviated with IH, that computes the convex hull of a simple polygon P = (p0,p1,,pn1), with points pi R2 and its corresponding edges pipi+1. The points are ordered in counterclockwise order.
(a) In this example p2 is Left of p0p1, while p3 is Right of p0p1. (b) Here p0,p1,p2 and p3
p0
2
Although our definition of a simple polygon doesnt exclude successive points being collinear, Inside- Hull assumes that this is not the case.
InsideHull uses a double ended queue abstract data type to represent the convex polygon it constructs. A double ended queue is abbreviated to deque and it has the following operations:
push to the top of the deque
pop from the top of the deque
insert to the bottom of the deque
remove from the bottom of the deque
The top and bottom of a deque c are indexed by ct and cb respectively. In the following algorithm the deque c gives rise to the convex hull C = cb, cb+1, . . . , ct1, ct.
The algorithm is as follows. Parts of the algorithm denoted by . . . are not complete and will require you to fill them in.
function InsideHull(Polygon) confirm the input is valid if Left(p0, p1, p2) then
C new deque p2, p0, p1, p2 else
C new deque p2, p1, p0, p2
while i < n doGet next point piif Left(ct1, ct, pi) and Left(cb, cb+1, pi) thenii+1Continuewhile Right(ct1, ct, pi) doPop ct from CPush pi to Cwhile Right(cb, cb+1, pi) doRemove cb from C Insert pi into C ii+1…Note that during the algorithm, the deque C contains the points of the partial convex hull (which is completed by the end of the algorithm) in counter-clockwise order. At the beginning of each outer while loop cb and ct refer to the same point, and this point will always be the most recent point added to C.Part C: Deque Data StructureImplement a Deque abstract data structure and complete the definitions of the following functions in deque.c: new deque() free deque() deque push() deque insert()3 deque pop() deque remove() deque size()It is up to you to decide on which underlying data structure will be used for your Deque. All of the operations described above must run in constant (O(1)) time1.Update: free deque() may run in linear (O(n)) time. Part D: Deque AnalysisExplain your deque implementation and the decisions you made. Describe the time complexities of the four main operations (push, pop, insert, remove) and how these time complexities are achieved.Part E: Inside Hull TracingRun the following example by hand and provide the points contained in the deque at each step of the algorithm. Be clear about which end of your deque is the top and which is the bottom.The points are provided to InsideHull in alphabetic order, starting with point A.HABPart F: Inside Hull ImplementationG FD E C Implement the C function inside hull() that takes a polygon consisting of n points and computes the points of its convex hull.The polygon will be provided as an array of n points named points, and the points will appear in counter-clockwise order.Your function should store the points which make up the convex hull in the array hull, which will have enough memory for at least n points. These points should be stored in counter-clockwise order, and the first and last points should not be the same. This will mean the number of points in hull will be one fewer than the size of the deque C at the end of the algorithm.The number of points stored in hull should be returned. If an error occurs return INSIDE HULL ERROR. If three consecutive points are collinear return COLLINEAR POINTS and dont complete the algorithm (make sure you free any memory you have allocated before you return).Note: You may assume that the input we will use to test your program will either have collinear points occurring consecutively or no collinear points at all. Note that the points across the array boundary (e.g., P olygon[n 1], P olygon[0], and P olygon[1]) are considered consecutive.1We require constant case on average, i.e., constant amortised runtime. This means you may choose to use some sort of resizable array, as long as the resizing isnt being performed during each operation 4Part G: Inside Hull AnalysisThe best algorithms we have for computing convex hulls for a general set of n points are O(n log n), if they are not output sensitive2.Identify the basic operations in the InsideHull algorithm and use this to determine the time complexity of InsideHull, give your answer in Big-Oh notation. Explain how you arrived at this answer.Does this contradict the statement about runtimes above? Explain why it does or does not.Completing the Coding TasksWe have provided the skeleton for this project which includes the following files: main.c The entry point to the program, and the functionality which deals with command lineinput and output. Do not change this file. point.h, point.c Provides the Point struct and related functions. You may add to thismodule if you need additional functionality, but dont change existing code. convex-hull.h, convex-hull.c Here is where you will implement orientation() and inside hull(). You may add to the header file dont change existing function signatures. deque.h deque.c Here is where you will implement your Deque data structure. You may add to the header file dont change existing function signatures. Makefile provides make targets all (to compile the program), clean (to delete the .o files and the executable) and submit (which creates submission.zip including all files in the directory). You should add to this Makefile if you want us to compile your program in another way, or if you add other files.To compile the program run make. This will create an executable a1.Feel free to add any additional .c/.h files, but make sure you add these to your Makefile as well.For information about how the program a1 runs, and the command line options, please see Appendix B: Using The Command Line Tool.Your code will be compiled and tested on the School of Engineerings Linux Servers so make sure you compile and test your code thoroughly on dimefox before submission. For information on how to login to dimefox see the Workshops section of the LMS. Please try this early and often, being unable to access dimefox is not grounds for an extension or other considerations.Completing the Analysis TasksYou should create a PDF file analysis.pdf with your answers to Parts B, D, E and G. You should aim to write no more than 2 pages.Justify all your answers and provide answers as asymptotic complexity classes (e.g., O,,). To receive full marks the bounds should be tight, for example if an algorithm is an n2 algorithm O(n2) will receive full marks, while O(n3), O(2n), O(n!), etc. will not.MarkingThe total number of available marks for this assignment is 10 (ten), and this assignment is worth 10% of your grade in this subject.2An output sensitive algorithms runtime depends on the size of the output as well as the size of the input, in this context it would mean that the runtime is dependent on the number of points which are part of the convex hull.5There are 5 available marks for the coding tasks, and 5 available marks for the analysis tasks. The breakdown is as follows: Coding Tasks PartA1Mark PartC2Mark PartF2Mark Analysis Tasks PartB1Mark PartD1Mark PartE1Mark PartG2MarkC code with poor coding style, lack of comments, poor functional decomposition, memory leaks and/or large chunks of duplicate code may have up to 1 mark deducted.Compilation warnings may result in up to 1 mark being deducted.We will compile and test your code automatically, so failure to compile on dimefox (see the Submission section) may result in an overall mark of 0 for the coding tasks.To receive full marks your analysis must be consistent with your C implementation.To receive full marks for the coding tasks the algorithms must meet the time complexity requirements (i.e., all operations in Parts A and C must be constant time) and follow the prescribed algorithm correctly (in the case of Part F).SubmissionThe Makefile provides the make submit command which zips up the assignment directory and creates submission.zip.Make sure that all C code required to compile and execute your program are included. We will open assignment submissions next week.Code Usage and Academic HonestyYou may make use of code provided as part of this subjects workshops or their solutions (with proper attribution), however you may not use code sourced from the Internet or elsewhere. Using code from the Internet is grounds for academic misconduct.All work is to be done on an individual basis. All submissions will be subject to automated similarity detection. Where academic misconduct is detected, all parties involved will be referred to the School of Engineering for handling under the University Discipline procedures. Please see the Subject Guide and the Academic Integrity section of the LMS for more information.6Appendix A: Vector OperationsIn this assignment we will be dealing with points in the plane, i.e., vectors in R2.Sometimes we view a pair of points (x, y) as a position vector and sometimes as a direction vector. The first two operations we will describe are vector addition and subtraction, as in the figure below. bba aqp+q p(0, 0) As we can see, the line segment ab is given by b a.For a = (xa, ya), b = (xb, yb) addition and subtraction are given bya + b = (xa + xb, ya + yb), a b = (xa xb, ya yb).The dot product a b is given byThe result of a dot product is a scalar.a b = xaxb + yayb.The dot product ab can give us the magnitude of the projection of a onto the line between the origin(0, 0) and b. a ab|b|b(0, 0)If a projected onto b was in the opposite direction of the line from the origin to b then the dot productwill be negative.The cross product between two vectors a and b is given bya b = xayb yaxb.The cross product gives the signed area of the parallelogram with vertices (0, 0), a, b and a + b.b(0, 0)a+bArea = a ba7The sign of the area is given by the right hand rule, if youve taken first year physics you should be familiar with this. That is to say, if the angle from a to b travelling clockwise around the origin is between 0 and 180 then the cross product is negative, and positive otherwise. Hence the cross product in the example above is positive. On the other hand b a would be negative.Appendix B: Using The Command Line ToolRunning a1 without any command line options, or by using the -h or –help options will print the following usage message:usage: ./a1 [options] <
options:
-o | orientationTest the orientation() function
-d | dequeTest deque functionality
-i | inside-hullTest the inside_hull() function
-h | help Print this help message
The three options (orientation, deque and inside-hull) test the three coding tasks respec- tively.
Note: you do not need to implement the input/output for these command line options, this is done for you in main.c you just need to implement the functions described in the Tasks section.
orientation expects three points in the following format:
x0 y0
x1 y1
x2 y2
And outputs the result of orientation(p0, p1, p2). For example if input.txt contains:
0.0 0.0
1.0 1.0
1.0 0.0
Then the output will be:
$ ./a1 orientation < input.txtp0: 0.00 0.00p1: 1.00 1.00p2: 1.00 0.00p2 is to the right of the line p0p1Input to –deque is some number of commands (push x y, insert x y, pop, remove, size) to stdin.For example if input.txt contains:push 1 1insert 0 0sizepush 2.5 2.5push 3 2sizepop pop8remove popThen the output will be:$ ./a1 –deque < input.txt243.00 2.002.50 2.500.00 0.001.00 1.00Input to –inside-hull is in the format:nx1 y1…xn ynThese points are read into a polygon and inside hull() is called. For example if input.txt contains:50020221.5 0.5 02Then the output will be:$ ./a1 –inside_hull < input.txt0.00 2.000.00 0.002.00 0.002.00 2.00 9
Reviews
There are no reviews yet.