=========================preview======================
(COMP151)midterm_s2004.pdf
Back to COMP151 Login to download
======================================================
CS 151: Object Oriented Programming
Spring Semester 2004
Midterm Exam
Instructor: Chi-Keung Tang
Thursday, March 4, 2004
7:00 C 9:00pm
at LTB or LTC
This is a CLOSED-BOOK-CLOSED-NOTES exam consisting of two (2) problems. Follow the instructions carefully.
Please write legibly in the boxes provided. Any space outside the boxes are for sketching and will not be graded. Keep the
exam booklet stapled.
Hint: THINK CAREFULLY! All correct answers are SIMPLE, but not necessarily easy.
KEY
Problem
Points
your score
1 POLYGON
5
2 REGISTER
10
Total
15
1 Polygon
Figure 1: Polygon examples
A
A
F
B
B
F
E
C
E
C
D
current_pointer
D Doubly linked list representation
Polygon of the Polygon
Figure 2: Polygon representation
In this question, you are required to implement two member functions for a class Polygon to manipulate a 2D polygon.
For example, Figure 1 shows some typical polygons. Actually, a polygon can be represented by a circular doubly linked list
(see Figure 2). An edge connecting a node (Point) A and B is represented by a next-pointer in node A and a previous-pointer
in node B.
As the result, the Polygon class contains a circular doubly linked list that stores the points or vertices of a polygon.
Here is the structure of a Point for a 2D point or vertex:
struct Point{
int x; // x.coordinate
int y; // y.coordinate
}
And, here is the de.nition of the Polygon class:
class Polygon{
public:
Polygon(); // default constructor
~Polygon(); // destructor
// It take an array of points and form a polygon
void setPolygon( Point pts[], int size)
{
vertexList.clear();
for( int i=0; i<size; i++ )
{
vertexList.insertToNext( pts[i] );
vertexList.pointToNext();
}
}
// To be implemented
Polygon* splitPolygon();
// To be implemented
bool isCollide( Polygon& inPolygon );
// The input edge is defined by 2 end points . ptA and ptB
// This function return true if the input edge intersect
// or touch this polygon. Otherwise, it return false.
bool isEdgeIntersect( const Point& ptA, const Point& ptB );
private:
LinkedList vertexList; // The circular doubly linked list
};
As you can see, the polygon class contains a private variable called vertexList which is a LinkedList object. This is the circular doubly linked list.
The de.nition of the LinkedList is de.ned as follow:
class LinkedList{
public:
LinkedList(); // default constructor
~LinkedList(); // destructor
int getSize() const; // return the number of elements(node) of the linked list
bool isEmpty() const; // return true if the list is empty
void clear(); // make the circular doubly linked list empty
void deleteCurrentNode(); // delete the current node. The current pointer will
// point to the next node of the deleted node
void pointToNext(); // make the current_pointer point to the next node
void pointToPrev(); // make the current_pointer point