CS 100: Programming Assignment P7A and P7B
Solution
Part A.
Correctness + Style Partial Credit Guidelines:
Regular polygon constructor: 1+1
General Constructor: 1+1
Centroid: 2+1 (-1 if return centroid of relative polygon)
Normalization: 1+1
Intersect: 2+1 (-1 if correct but work with relative vertices.)
// An instance of this class is a polygon
public class polygon extends closedPolyline
{
// The Constructors
// Constructs a regular polygon with nSides sides, radius r, and center alpha_point.
public polygon(point alpha_point, int nSides, double r)
{
n = nSides;
alpha = alpha_point;
relVertex = new point[n];
double mu = 2*Math.PI/n;
for (int k=0;k < n;k++)
relVertex[k] = new point(r*Math.cos(k*mu),r*Math.sin(k*mu));
}
// Let n = theta.length = r.length and assume n>=3. Constructs a polygon with n sides.
// The k-th vertex is
//
// (alpha_point.x + r[k]*cos(theta[k]) , alpha_point.y + r[k]*sin(theta[k])).
//
// It is assumed that the vertices are distinct and that
//
// 0<=theta[0]<=theta[1]<=...<=theta[n-1]<=2pi
//
// and that theta[0] + pi < theta[n-1].
public polygon(point alpha_point, double[] theta, double[] r)
{
n = theta.length;
alpha = alpha_point;
relVertex = new point[n];
for (int k=0;k < n;k++)
relVertex[k] = new point(r[k]*Math.cos(theta[k]),r[k]*Math.sin(theta[k]));
}
// Yields the centroid of the polygon.
public point centroid()
{
point origin = new point(0,0);
point Ck;
double Ak;
double A = 0;
double xSum = 0;
double ySum = 0;
for(int k=0;k < n;k++)
{
Ak = point.triangleArea(origin,relVertex[k],relVertex[(k+1)%n]);
Ck = point.triangleCentroid(origin,relVertex[k],relVertex[(k+1)%n]);
xSum = xSum + Ak*Ck.get_x();
ySum = ySum + Ak*Ck.get_y();
A = A + Ak;
}
return new point(alpha.get_x()+xSum/A,alpha.get_y()+ySum/A);
}
// Translates the polygon so its centroid is at (0,0).
public void normalize()
{
point theCentroid = centroid();
translate(-theCentroid.get_x(),-theCentroid.get_y());
}
// Yields true if the boundary of this polygon intersects the boundary of P.
public boolean intersect(polygon P)
{
point[] v1 = this.get_absVertex();
point[] v2 = P.get_absVertex();
for(int i=0;i< v1.length;i++)
for (int j=0;j < v2.length;j++)
if (point.intersect(v1[i],v1[(i+1)%v1.length],v2[j],v2[(j+1)%v2.length]))
return true;
return false;
}
}
Part B
8 points total.
2 points overall for style
2 points if one of the four horizontal/vertical searches is correct. 3points if they all work and Rook-Queen threats processed OK
2 points if one of the four diagonal searches works. 3 points if they all work and Bishop-Queen threats procesed OK.
Other types of deductions:
Everything correct but the loop starting values are wrong: -2.
Everything correct but the post loop calculations wrong: -2
Everything correct but overall logic wrong, e.g., return false without checking all 8 search directions: -3
// Yields true if position (r,c) is threatened by a Queen, a Rook, or a Bishop.
public boolean qrbThreat(int r, int c)
{
int r0,c0; // Row and column indices.
// Look left along the row.
c0=c-1;
while (onBoard(r,c0) && pieceBoard[r][c0].equals(""))
c0=c0-1;
if(onBoard(r,c0) && (pieceBoard[r][c0].equals("Q")||pieceBoard[r][c0].equals("R")))
return true;
// Look right along the row.
c0=c+1;
while (onBoard(r,c0) && pieceBoard[r][c0].equals(""))
c0=c0+1;
if(onBoard(r,c0) && (pieceBoard[r][c0].equals("Q")||pieceBoard[r][c0].equals("R")))
return true;
// Look up along the column.
r0=r-1;
while (onBoard(r0,c) && pieceBoard[r0][c].equals(""))
r0=r0-1;
if(onBoard(r0,c) && (pieceBoard[r0][c].equals("Q")||pieceBoard[r0][c].equals("R")))
return true;
// Look down along the column.
r0=r+1;
while (onBoard(r0,c) && pieceBoard[r0][c].equals(""))
r0=r0+1;
if(onBoard(r0,c) && (pieceBoard[r0][c].equals("Q")||pieceBoard[r0][c].equals("R")))
return true;
// Look along the northeast diagonal
r0=r-1;
c0=c+1;
while (onBoard(r0,c0) && pieceBoard[r0][c0].equals(""))
{
r0=r0-1;
c0=c0+1;
}
if(onBoard(r0,c0) && (pieceBoard[r0][c0].equals("Q")||pieceBoard[r0][c0].equals("B")))
return true;
// Look along the southeast diagonal
r0=r+1;
c0=c+1;
while (onBoard(r0,c0) && pieceBoard[r0][c0].equals(""))
{
r0=r0+1;
c0=c0+1;
}
if(onBoard(r0,c0) && (pieceBoard[r0][c0].equals("Q")||pieceBoard[r0][c0].equals("B")))
return true;
// Look along the southwest diagonal
r0=r+1;
c0=c-1;
while (onBoard(r0,c0) && pieceBoard[r0][c0].equals(""))
{
r0=r0+1;
c0=c0-1;
}
if(onBoard(r0,c0) && (pieceBoard[r0][c0].equals("Q")||pieceBoard[r0][c0].equals("B")))
return true;
// Look along the northwest diagonal
r0=r-1;
c0=c-1;
while (onBoard(r0,c0) && pieceBoard[r0][c0].equals(""))
{
r0=r0-1;
c0=c0-1;
}
if(onBoard(r0,c0) && (pieceBoard[r0][c0].equals("Q")||pieceBoard[r0][c0].equals("B")))
return true;
// If you reach this point then none of the eight searches found a qrb threat.
return false;
}
Here is an implementation that exploits the similarities that you see in the above eight searches.
// Yields true if position (r,c) is threatened by a Queen, a Rook, or a Bishop.
public boolean qrbThreat(int r, int c)
{
boolean diagSearch; // True if looking along one of the four diagonal directions.
int r0,c0;
for(int dr=-1;dr<=1;dr++)
// dr is the row search step (-1, 0, or +1)
for(int dc=-1;dc <=1;dc++)
// dc is the column search step (-1, 0, or +1)
if (Math.abs(dr)+Math.abs(dc)>0)
// Always do the following unless dr = 0 and dc = 0.
{
r0 = r+dr;
c0 = c+dc;
while (onBoard(r0,c0) && pieceBoard[r0][c0].equals(""))
{
r0 = r0+dr;
c0 = c0+dc;
}
diagSearch = Math.abs(dr)+Math.abs(dc)==2;
if (onBoard(r0,c0) && diagSearch && (pieceBoard[r0][c0].equals("Q") || pieceBoard[r0][c0].equals("B")))
// Found a bishop or queen on a diagonal search.
return true;
else if (onBoard(r0,c0) && !diagSearch && (pieceBoard[r0][c0].equals("Q") || pieceBoard[r0][c0].equals("R")))
// Found a rook or queen on a row/column search.
return true;
}
return false;
}