1. Engineering
  2. Computer Science
  3. write a java program within the given template and read...

Question: write a java program within the given template and read...

Question details

Write a java program within the given template and read the instruction below:

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 (clockwise or 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.

Useful information:

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 3 ร— 3 matrix shown below: ๐‘‘๐‘’๐‘™๐‘ก๐‘Ž (๐‘Ž, ๐‘, ๐‘) = ๐‘‘๐‘’๐‘ก [๐‘ฅ๐‘Ž ๐‘ฆ๐‘Ž 1 ๐‘ฅ๐‘ ๐‘ฆ๐‘ 1 ๐‘ฅ๐‘ ๐‘ฆ๐‘ 1] This expression can be computed in ๐‘‚(1) 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 (๐‘Ž, ๐‘, ๐‘) is 1/2 ๐‘‘๐‘’๐‘™๐‘ก๐‘Ž (๐‘Ž, ๐‘, ๐‘) , 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 (๐‘Ž, ๐‘) and (๐‘, ๐‘‘) are disjoint. The possible cases are depicted in the figure below.

This test can be done in (1) 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 ๐‘ฃ0, ๐‘ฃ1, โ‹ฏ , ๐‘ฃ๐‘›โˆ’1 , where we denote the xy-coordinates of vertex ๐‘ฃ๐‘– by the pair ๐‘ฅ๐‘– , ๐‘ฆ๐‘– . For notational simplicity, we assume ๐‘ฃ๐‘›โ‰ก ๐‘ฃ0 and ๐‘ฃโˆ’1 โ‰ก ๐‘ฃ๐‘›โˆ’1 (i.e., index arithmetic is modulo n). Then the area of the simple polygon is: 1/2 ๐‘‘๐‘’๐‘™๐‘ก(๐‘œ, ๐‘ฃ๐‘– , ๐‘›โˆ’1 ๐‘–=0 ๐‘ฃ๐‘–+1) = 1/2 ๐‘ฅ๐‘– ๐‘ฆ๐‘–+1 โˆ’ ๐‘ฆ๐‘–โˆ’1 ๐‘›โˆ’1 ๐‘–=0 , where ๐‘œ = (0,0) 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.

The template is given in the link below, please see it, thank you

Please use the template given in the link: https://mega.nz/#!B08i0Srb!WKE-MaQFYPo_aZIOoA15xufMyuPLz1QOztho0rQ77oc

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution