top of page
Search
Aug 18, 2020

Machine Learning Project Assignment Help - How to Draw the polygon with minimum Area Using Points

Updated: Mar 25, 2021

Summary description and objectives for the assessment


POLY


Given a set of points in the XY-plane, find a (non-self-intersecting) polygon that covers ALL points trying to reduce the area it spans. The vertices of the computed polygon MUST belong to the set points. Examples of invalid and valid cases are shown in Figure 1.



Figure 1. (a) An example of an input set of points (10 points). (b) An invalid polygon solution for (a) as its vertices are not points of the input data. (c) An invalid polygon solution for (a) as one of its vertices is not a point of the input data. (d) An invalid polygon solution for (a) as not all points of the input data are covered. (e) A valid polygon solution for (a) as all input points are covered and the vertices are all part of the input data. (f) A better valid solution for (a) as the resulting area is less than that in (e) and all conditions are met. Please observe that self-intersecting polygons are not valid.


This individual project will be assessed through your code and a test. The test will use one input set of up to 1000 points to check whether your proposed algorithm generates valid solutions. You are provided with three Python scripts, namely, ‘main.py’, ‘test.py’, and ‘utils.py’, to examine your algorithm in similar conditions to those in the test. These scripts also provide useful tools such as a function to check whether a solution is valid, and a visualization tool to display a solution. The Python scripts are available here. Simple mock examples of invalid and valid solutions are provided in the scripts. It is your responsibility to familiarize with the use of the provided scripts, so please start as soon as possible!


OBJECTIVES


The main objective for this assignment is to verify that you are capable of

  • Applying algorithm analysis techniques to determine the running time of algorithms and how a programme performs and scales with problem size.

  • Explaining the basic principles and foundational techniques for designing algorithmic solutions for unseen problems.

  • Using general design methods for devising programmes that are asymptotically efficient.

  • Implement well-known, high-level algorithms and adapt them efficiently to new applications.

  • Designing, implementing, and analyzing your own algorithms and data structures.


Submission requirements

  • Failure to comply with any of the requirements below will result in the assignment being marked 0%.

  • You are required to submit a ZIP file that includes the source code of your proposed solution in Python 3. The main script of the algorithm should be called ‘main.py’ which includes the main solution function called ‘poly’ as described in subsection CODE


SUBMISSION FORMAT


The ZIP file needs to be sent via email to the module leader (Nicolas Rojas, n.rojas@imperial.ac.uk) before Tue 1 Sep 2020 4pm UK time.

The module leader will acknowledge the receipt of your submission by replying to your email. It is your responsibility to keep a copy of this confirmation.


CODE SUBMISSION FORMAT


The main script of your proposed solution should be called ‘main.py’ which must include a main function called ‘poly’ as shown below: 



def poly(points): 
        """ This function uses the input set of points, and finally 
        outputs your polygon 
        :param points: set of points :return: solution polygon 
        covering the input set of points 
        """ your code … 
        return solution

This ‘poly’ function takes an arbitrary set of points of the xy-plane points as input, and then generates and returns a polygon solution as output. Specifically, points is a list of coordinates provided by the module leader to represent the set of points to be covered. Each element in the list points represents a xy-coordinate using a tuple (x, y). For example, in Figure 1(a), the set of points is represented as:


points = [(72, 69), (67, 30), (88, 58), (94, 15), (18, 77), (14, 6), (42, 11), (83, 21), (13, 20), (22, 1)]

Based on the input set of points points, the ‘poly’ function will need to generate and return a list of coordinates solution to represent a polygon that covers the set. The coordinates in solution must be coordinates of points (i.e., the vertices of the computed polygon MUST belong to the set points). Moreover, the first and last coordinate in the list must be the same.

For example, the solution polygon in Figure 1(c) is represented as:


solution = [(22, 1), (14, 6), (13, 20), (18, 77), (72, 69), (95, 60), (94, 15), (22, 1)]

which is invalid as one vertex (coordinate) of the polygon, namely (95, 60), is not part of the input set of points points. Similarly, the solution polygon in Figure 1(e) is represented as:

solution = [(22, 1), (14, 6), (13, 20), (18, 77), (72, 69), (88, 58), (94, 15), (22, 1)]

which is a valid solution. USE OF EXTERNAL LIBRARIES Python external libraries (e.g., NumPy, matplotlib) can be used in the proposed solution. However, appropriate comments explaining the use of functions/methods from these libraries have to be included in the code (where their call occurs). Please also include a statement at the top of the


‘main.py’ file summarising the external libraries and functions/methods used (if any). TEST POLICY The number of points of the input set will never exceed 1000. The running time of your algorithm MUST NOT exceed 10 minutes; if the algorithm cannot find a solution within that time in the test, the result will count as invalid.



contact us at: cotact@codersarts.com to get any project or assignment related help at here with and affordable prices.


Comments

bottom of page