Problem: A convex polygon
in the plane is a simple
polygon with the property that the line segment determined by any of its
two vertices falls entirely within it. Here are some examples of the simplest convex
polygons: a triangle, a trapezoid, and a pentagon.
Write a program to compute the perimeter and the area of a convex polygon whose vertices are specified in a file. In so doing, make use of the class Vector we developed.
Step U. Understanding the problem.
The problem calls for the construction
of convex polygon and the computation of perimeter and area. It requires that
we make use of the class Vector we developed earlier. Precisely, the vertices
of the polygon are points in the plane, which are readily represented as 2-d
vectors. Immediately, we see that some more functions or member function of the
vector are needed. For example, the length of a side is the length of the
difference of two vectors representing its two end points.
In computing the perimeter, it is important to note that the vertices of the convex polygon are traversed in the right order:
The perimeter is correctly computed for the rectangle (a convex quadrilateral) on the left by traversing the vertices in the order of A, B, C, D and A. However, the polygon on the right, which is neither convex nor simple, has a longer perimeter than the rectangle.
Step D. Devising a plan.
Here are the tasks.
T1. Create a convex polygon given a list of
vertices, assuming its vertices are ordered correctly.
T2. Create a convex polygon given a list of
vertices, assuming its vertices may not be ordered correctly.
T3. Compute the perimeter. (Look here for a discussion of delegation)
T4. Compute the area.
T5. Write the main to interact with user.
Task T1 is a simplified version of Task T2. We could
have listed Task T2 only, but that seems more difficult. In particular, if not
already correctly ordered, how do we arrange the vertices in a correct order? Listing T1 as a task helps us to concentrate on the design of the object
representation of a convex polygon. Furthermore, it can be easily seen that when
we can do T1, T2 can be accomplished by finding some way to arrange the
vertices.
Note that although I have omitted the unit
tests as specific tasks, it should always be remembered that they are part of a
task. In fact, be reminded that unit tests should be the first thing you do in
carrying out a task.
The Task T4, computation of area, is not
obvious. We know how to do this for the triangle: for example, assuming that
the three sides are of lengths a, b, and c, the area of the triangle can
be computed with the Heron’s formula by
where
With this, the area can be achieved by
decomposing the polygon into a number of triangles, for example:
With this we add the following task:
T6. Compute the area enclosed by three
vectors.
Note that the task list does not impose an
order of the task execution. Therefore you don’t have to rearrange the task
numbers.
Step
C. Carrying out the plan.
Let us look at the implementation of T2 in some detail. One way to make sure that the vertices of a polygon are ordered correctly is to sort them the around the centroid. To do this, first, find the centroid. Let V1, V2, ...Vn be the vertices of a convex polygon. The centroid O is (V1 + V2 + ... + Vn)/n. Then, locate the vertex with the largest x-coordinate value. When there are multiple vertices tie with the largest x-coordinate value, break the tie by finding the one with the largest y-coordinate. Call this vertex V, and define the reference vector R as the vector V-O. In the pentagon below, the vertex A is the largest X-coordinate value.
With centroid O and the reference vector R=V-O determined, the angle a vertex U forms with the reference vector R around the centroid O is
since the range of arc cosine in degrees is [0,180] rather than [0,360], we shall take angle to be
if the cross product vector of R, U-O is pointing out, and to be 360- if the the cross product vector is pointing in. Since we are dealing with vectors in the plane, the cross product of [u1,v1] and [u2,v2] is simply (u1*v2-u2*v1)[0,0,1].
Sorting the vertices of the polygon by the angles they form with the reference vector around the centroid, we ensure that the vertices are ordered correctly for the computation of perimeter and area.
The following is an example.
The polygon (a regular pentagon) has the vertices A,B,C,D, and E. O is the computed centroid. R = A-O is the reference vector. The angles the vertices form with the reference vector R around the centroid O are computed as follows:
Thus, even if the constructor of Polygon is given a list of vertices in an arbitrary order, we can make sure that they are brought to a correct order by sorting them around the centroid with respect to the reference vector. In the example above, the vertices are ordered counter-clockwise.
As can be seen, the need to sort vertices requires support from many places: from the Vector class, we need to add an overloading subtraction operator - for subtracting vectors, a function to compute the angle between two vectors, a function to calculate the length of a vector, a function to decide if the cross product vector of two given vectors is pointing out or pointing in, and so on. Also, we need a function to sort the vertices as defined above. This can be done with a function from the standard template library called std::sort.
If you check the documentation for std::sort, you will find that the sort function works with array (as well as other containers in the standard template library, but we won't get into that here.) However, it requires you to specify how you compare two objects stored in the array to be sorted. This can be done with the a C-style function or a class object with a member function overloading the function call operator (). For more details, check it out on std::sort.
In the example above, we have
Vector vs[5] = {B,D,C,E,A};
Polygon p(vs,5);
Note how the vertices of the polygon p are initially incorrectly ordered (one of the correct orderings would be A,B,C,D, and E).
In order to sort the vertices, we need to supply a comparator to be used by std::sort. In our case, since the comparator needs to remember the centroid and the reference vector, we will create a class comparator called angleLT (which stands for angle less than) as follows:
to sort the vertices of a polygon P, we do
std::sort(vs,vs+5,angleLT(p.centroid(),p.refVector()));
where Polygon::centroid() and Polygon::refVector() are member functions to compute the centroid and the reference vector, respectively.
Here is the working program including unit tests. The production program is left to you as an exercise.
Step L. Looking back.
In solving the problem of computing the area of a convex polygon, we were able to reuse and make enhancements to the class Vector. As can be seen, the existence of the class Vector makes easy the representation of polygon and the computations of perimeter and area. This is what we normally expect from an object-oriented language like C++: to construct multiple levels of abstraction so that the problem on hand comes closer to its solution. To see the benefit of this, imagine if you are asked to program the solution to this problem in C. You'll be dealing with lots arrays of doubles at different levels of abstraction. The arrays all look homogeneous in not having a clearly identifiable description and it is your task to remember their different levels of abstraction. Very taxing indeed.
In looking back, we see that the unit tests are lumped together, and there are more than 600 lines of code of them. It is highly recommended that they be restructured into several files, one file for the unit tests for each of the important classes. This is left as an exercise.
© Y C Cheng, 2013, 2014. All rights reserved.
Let us look at the implementation of T2 in some detail. One way to make sure that the vertices of a polygon are ordered correctly is to sort them the around the centroid. To do this, first, find the centroid. Let V1, V2, ...Vn be the vertices of a convex polygon. The centroid O is (V1 + V2 + ... + Vn)/n. Then, locate the vertex with the largest x-coordinate value. When there are multiple vertices tie with the largest x-coordinate value, break the tie by finding the one with the largest y-coordinate. Call this vertex V, and define the reference vector R as the vector V-O. In the pentagon below, the vertex A is the largest X-coordinate value.
With centroid O and the reference vector R=V-O determined, the angle a vertex U forms with the reference vector R around the centroid O is
since the range of arc cosine in degrees is [0,180] rather than [0,360], we shall take angle to be
Sorting the vertices of the polygon by the angles they form with the reference vector around the centroid, we ensure that the vertices are ordered correctly for the computation of perimeter and area.
The following is an example.
The polygon (a regular pentagon) has the vertices A,B,C,D, and E. O is the computed centroid. R = A-O is the reference vector. The angles the vertices form with the reference vector R around the centroid O are computed as follows:
Thus, even if the constructor of Polygon is given a list of vertices in an arbitrary order, we can make sure that they are brought to a correct order by sorting them around the centroid with respect to the reference vector. In the example above, the vertices are ordered counter-clockwise.
As can be seen, the need to sort vertices requires support from many places: from the Vector class, we need to add an overloading subtraction operator - for subtracting vectors, a function to compute the angle between two vectors, a function to calculate the length of a vector, a function to decide if the cross product vector of two given vectors is pointing out or pointing in, and so on. Also, we need a function to sort the vertices as defined above. This can be done with a function from the standard template library called std::sort.
If you check the documentation for std::sort, you will find that the sort function works with array (as well as other containers in the standard template library, but we won't get into that here.) However, it requires you to specify how you compare two objects stored in the array to be sorted. This can be done with the a C-style function or a class object with a member function overloading the function call operator (). For more details, check it out on std::sort.
In the example above, we have
Vector vs[5] = {B,D,C,E,A};
Polygon p(vs,5);
Note how the vertices of the polygon p are initially incorrectly ordered (one of the correct orderings would be A,B,C,D, and E).
In order to sort the vertices, we need to supply a comparator to be used by std::sort. In our case, since the comparator needs to remember the centroid and the reference vector, we will create a class comparator called angleLT (which stands for angle less than) as follows:
to sort the vertices of a polygon P, we do
std::sort(vs,vs+5,angleLT(p.centroid(),p.refVector()));
where Polygon::centroid() and Polygon::refVector() are member functions to compute the centroid and the reference vector, respectively.
Here is the working program including unit tests. The production program is left to you as an exercise.
Step L. Looking back.
In solving the problem of computing the area of a convex polygon, we were able to reuse and make enhancements to the class Vector. As can be seen, the existence of the class Vector makes easy the representation of polygon and the computations of perimeter and area. This is what we normally expect from an object-oriented language like C++: to construct multiple levels of abstraction so that the problem on hand comes closer to its solution. To see the benefit of this, imagine if you are asked to program the solution to this problem in C. You'll be dealing with lots arrays of doubles at different levels of abstraction. The arrays all look homogeneous in not having a clearly identifiable description and it is your task to remember their different levels of abstraction. Very taxing indeed.
In looking back, we see that the unit tests are lumped together, and there are more than 600 lines of code of them. It is highly recommended that they be restructured into several files, one file for the unit tests for each of the important classes. This is left as an exercise.
© Y C Cheng, 2013, 2014. All rights reserved.
