EECS2011-Assignment 1 Solved

This assignment is about the polygon hierarchy shown in the figure below. 

 
We use double precision coordinates for vertices of the polygon. So, our Polygon interface is different from the java.awt.Polygon class in the Java API (which uses int-coordinate vertices) . 3

 

•     Page 2 gives some preliminary descriptions.

•     Page 3 shows some useful facts that you may use.

•     Page 4 shows a summary of the interface and classes you are assigned to build and test.

                           You may use additional types or members as you deem necessary in your design.

•     Page 5 gives a small sample of input polygons you should test your program against.  

                           You should also use a number of other, larger, test cases of your own.

•     Page  5 also lists  what files you should submit.

•     Page  6 describes an extra credit and optional work.

 

Click  here   to see  the code templates  and  their  Javadocs.

Preliminaries: 

An 𝑛-sided polygon  𝑃  (𝑛 ≥ 3) is a cyclic sequence  𝑣0, 𝑣1, ⋯ , 𝑣𝑛−1  of vertices as we walk around the polygon boundary. Each vertex 𝑣𝑖  (the 𝑖th vertex) is a point in the plane represented by its 𝐝𝐨𝐮𝐛𝐥𝐞 𝑥 and 𝑦 coordinates.  The line-segment  𝑒𝑖 between vertex 𝑣𝑖 and the next vertex

 𝑣 𝑖+1 𝑚𝑜𝑑 𝑛 (in cyclic order around the boundary)  is called the 𝑖th edge of 𝑃, for 𝑖 = 0. . 𝑛 − 1.    You may use the  Point2D.Double  class  in the  java.awt.geom package of the Java API to represent polygon vertices.

 The polygon is said to be simple if no two non-adjacent pair of edges intersect. That is, two edges 𝑒𝑖 and 𝑒𝑗 are completely disjoint from each other whenever  1 < 𝑗 − 𝑖 < 𝑛 − 1.  

            A simple polygon is said to be convex if the internal angle of every vertex is at most 180°.  Equivalently, the simple polygon is  convex if every turn is consistently in the same orientation (not clockwise or not counter-clockwise) as we walk around the polygon boundary. This latter condition is computationally more useful (see the description of the Delta Test on the next page).     The main methods we are interested in is polygon perimeter and  area. Note that polygon area may not be well defined if the polygon is  non-simple, since the notion of polygon “interior” may not be well defined in that case. We obviously need the boolean methods  isSimple and isConvex as well.   


Extra Credit and Optional work: 

The last page talks about the contains(p) method which determines whether the polygon contains the given point p inside. The precondition is that the polygon is simple (otherwise, “inside” may not be well defined). This method can be implemented more efficiently on convex polygons than on simple polygons. Some hints are provided on how to implement this method.

 

Useful Facts: 

 

•     Delta Test:  

Suppose we are given an ordered sequence of three points     each point given by its   and   coordinates (e.g.,   and  ). We want to know what is the orientation as we go from   to   to   and back to  :  is it clockwise (i.e., right turn), counter-clockwise (i.e., left turn), or collinear?  The answer is given by the determinant of the     matrix shown below:

                                                                                                                      𝑥𝑎     𝑦𝑎      1

                                                                     𝑑𝑒𝑙𝑡𝑎 𝑎, 𝑏, 𝑐     = 𝑑𝑒𝑡𝑥𝑏            𝑦𝑏         1

                                                                                                                    𝑥𝑐      𝑦𝑐      1

 

This expression can be computed in  time with arithmetic operations on the xy-coordinates of the three given points and is a very useful quantity with many geometric applications.  (It is analogous to the  compareTo  method on  Comparable  types.)  So, it’s worth providing a static helper method to compute  .

 

•    Triangle Signed Area:

The signed area of the oriented triangle  ,  where the sign is positive, negative, or zero if the orientation is  counter-clockwise, clockwise, or collinear, respectively.

 

•    Line-Segment Disjointness Test:

A line-segment can be represented by a pair of delimiting points. We want to know whether a given pair of (closed) line segments  a are disjoint. The possible cases are depicted in the figure below.

 

This test can be done in  time (e.g., using the Delta Test).  (How?) You would need repeated use of such a test in the polygon simplicity checking method.  So, it’s worth providing a static helper method for line-segment disjointness  test.      Note: You must implement this method yourself. You are not allowed to use the  line intersection method provided by the Java API. Exercise your logical and analytical thinking and problem solving skills. 

 

•    Polygon Area:

Consider the simple polygon     , where we denote the xy-coordinates of vertex   by the pair  .   For notational simplicity,  we assume      and       

(i.e., index arithmetic is modulo n).    Then the area of the simple polygon is:

 

                             21  𝑛𝑖=−01  𝑑𝑒𝑙𝑡𝑎(𝑜, 𝑣𝑖, 𝑣𝑖+1)     =    21  𝑛𝑖=−01 𝑥𝑖  𝑦𝑖+1 − 𝑦𝑖−1   ,

 

where  denotes the origin.   

(Note: it’s absolute value of the sum, not the sum of absolute values!)

This expression can be evaluated in  time using arithmetic operations.

 

Interface  Polygon: 
 

 getSize()            returns n, the number of edges of the polygon.

 

 getVertex(i)       returns the 𝑖th vertex of the polygon with  precondition 0 ≤ 𝑖 < 𝑛.

                           Throws  IndexOutOfBoundsException  if the precondition is violated.

             

 perimeter()       returns the sum of the lengths of the edges of the polygon.

 

area()               returns area of the interior of the polygon if this notion is well defined;                throws an exception if it’s not.
Class SimplePolygon  (implements Polygon): 
 

getNewPoly()  constructs & returns a polygon, initialized by user provided data  in  O(n) time. toString()        returns a String representation of the polygon in O(n) time.

 

delta(a,b,c)       returns twice the signed area of oriented triangle (a,b,c) in O(1) time.

 disjointSegments (a,b,c,d)    returns true iff  closed line-segments (𝑎, 𝑏) and (𝑐, 𝑑) are disjoint.

                                                Runs in 𝑂(1) time.   

 disjointEdges(i, j)       returns true iff edges 𝑒𝑖 and 𝑒𝑗 of the polygon are disjoint.  

                                      Runs in 𝑂(1) time.

 

 isSimple() returns true iff the polygon is  simple. Running time is 𝑂 𝑛2 .

 

area()               returns area of the interior of the polygon with precondition that the  polygon is              simple. Throws  NonSimplePolygonException if the polygon is not simple (since in              that case the polygon “interior” may not be well defined). Runs in 𝑂(𝑛) time, not              counting the simplicity test.
Class ConvexPolygon  (extends SimplePolygon): 
             

isConvex()   returns true iff the polygon is convex, with precondition that the polygon is simple.              This method runs in 𝑂(𝑛) time. If the polygon is non-simple, the correctness of the              returned result is not guaranteed.
Class NonSimplePolygonException  (extends Exception): 
 

Thrown to indicate that the polygon is non-simple.
Class PolygonTester: 
 

This class has a main method that allows the user to input a variety of polygons and thoroughly test all aspects of the above types and methods, and displays or logs informative input-output.
Sample polygon input format:  

Below are some sample input polygons listed by the xy-coordinates of the vertices in sequence around the polygon boundary. You should test your program against these samples. You should also test it against many other larger and carefully chosen polygons as well. 

 

[ Format: n, followed by xy-coordinates of n boundary vertices in sequence. ] 

 

Poly1:   5   8.9 21.8 29.1 8.8 39.2 20.3 14 11 28 25 

 

Poly2:   7   28 2 31 5 28 10 14 14 5 10 8 4 18 1 

 

Poly3:   9   6 10 20 3 23 3 23 8 27 3 30 3 20 15 16 5 20 14 

 

Poly4:  13   5 6 13 2 12 6 20 2 16 12 17 11 19 5 13 11 19 15 8 12 14 7 5 11 9 6 

 

Poly5:  13   5 6 13 2 12 6 20 2 18 12 17 11 19 5 13 11 19 15 8 12 14 7 5 11 9 6 

 

Poly6:  22   14 7 15 8 17 7 17 5 15 6 14 4 12 6 11 9 15 11 7 12 8 11 7 9 10 11 8 6 10 5         11 3 16 3 18 4 19 8 16 9 14 9 13 8 

 

Poly7:   4   6 1 9 5 5 8 2 4 

 
This text file records  the Input/Output results of your test cases. Use copy-&-paste from the Java program console to this text file. It should clearly show that you have tested at least 7 different polygons (non-simple, simple, convex), and for each of them you have thoroughly tested the corresponding class methods.  

 

This method is now inherited by the ConvexPolygon class.

Now you override that method in the ConvexPolygon class, so that it runs in O(log n) time.

 

Hints on how to implement this method:

•    SimplePolygon.contains(p):  

Conceptually shoot a ray emanating from point p in a direction of your choice (e.g., in the direction of the x-coordinate axis) and count how many times does that ray “cross” the boundary of the polygon. If that count is odd, then p is inside. If that count is even, then p is outside the polygon. If point p lies on any edge or vertex, then it is considered inside too.

 

You can treat that ray as a sufficiently long line-segment, and use the disjointSegments test against edges of the polygon to count the number of crossings. Be careful to count properly if the ray passes through a vertex or is aligned with an edge of the polygon. Resolve the ambiguity by conceptually perturbing the ray with a slight angular rotation so that it does not pass through any vertex of the polygon.

 

•    ConvexPolygon.contains(p):

Can be done by a rotational binary search on the vertex sequence around the convex polygon boundary  (using the Delta Test for orientation) …