Theory
- Suppose that we have a square with n vertices: four of them at the
corners, B others along the boundary, and I points in the
interior. Show that in order to triangulate the interior of this
figure, we need to add exactly B + 3I + 1 edges.
- Prove that the complexity of the trapezoidation of a plane polygon with n vertices is linear in n. (The complexity is the total size of the data structure holding the trapezoidation, including vertices, edges and faces.)
Some Definitions
Trapezaoidation of a polygon
Given a polygon in the plane, a trapezoidation of that polygon is obtained by extending from each vertex of the polygon horizontal rays in each direction, until they exit the polygon. An example is shown below, where the red, dotted lines are the rays added to the bold polygon.
Program
Your job is to modify the makeTriangulations() function in this program so that the interior of the square is properly triangulated.
see Kirk.java
Corrected version of Kirk.java
- Changed the formula that created the vertices along the boundaries of the square, spacing them out instead of bundling them at the corner. This is in the section with the comment: "// Build the other boundary points"
- Changed the lower bound of the slider to "8."
- Added code to draw the bounding square.