nestedTriangles.cpp (attached) description:
The program takes as input a pair of triangles, specified be giving the coordinates of each triangle's vertices. It then determines if either triangle is "nested" within the other, meaning that one triangle lies entirely within the interior of the other.
Pseudocode:
One triangle lies within another if and only if all three vertices of the first triangle lie within the interior of the second triangle.
Suppose that we have a triangle with vertices A, B, and C, described by the coordinates (xA, yA), (xB, yB), and (xC, yC), respectively. The sides of the triangle are the line segments AB, BC, and CA.
A line passing through two points (x1, y1) and (x2, y2) can be considered to be the set of points (x,y) satisfying the equation
f(x,y) = 0
where f(x,y) is given as
f(x,y) = (x - x1) (y2 - y1) - (y - y1) (x2 - x1)
One of the interesting things about that f(x,y) is that we can use it to determine which "side" of the line an abitrary point (x,y) is on:
If f(x,y) = 0, the point is exactly on the line.
All points for which f(x,y) > 0 are on one side of the line, and
All points for which f(x,y) < 0 are on the other side
So the problem of determining whether a point (x,y) is on the inside of a trangle can be checking the sign of f(x,y) for each of the three lines making up the triangle.
A complicating factor is that we don't know, for any given triangle, whether those three signs should be all positive, all negative, or some mixture of the two.
The centroid of a triangle can be computed as the "average" of the x and y coordinates of the vertices:
xcen = (xA + xB + xC)/3
ycen = (yA + yB + yC)/3
This point (xcen, ycen) is definitely inside the trangle (unless the triangle is "degenerate" and has no interior points).
The problem of determining whether (x,y) is on the inside of a triangle can therefore be resolved by checking to see if it is on the same side of each of the triangle's line segments as (xcen, ycen).
What I need:
To fill in the missing bodies for the functions eval and areOnSameSideOf, which manipulate line segments. I think calling eval from within areOnSameSideOf will simplify the implementation of the latter.
#include <iostream>
using namespace std;
/**
* 2D Cartesian coordinates
*/
struct Point {
double x;
double y;
};
/**
* A simple triangle, modeled as a collection of 3 vertices
*/
struct Triangle {
Point vertices[3];
};
/**
* A line segment, indicated by its two endpoints
*/
//*** Insert your structure declaration here
/**
* Read a trangle from the input stream.
*
* A triangle is presented as a sequence of 6 floating point values,
* each successive pair of numbers being the x,y coordinates of one vertex.
*
* @param t the triangle being read in
* @param in the input from which it should be read
*/
void readTriangle (Triangle& t, istream& in)
{
for (int i = 0; i < 3; ++i)
{
double x, y;
in >> x >> y;
Point p = {x, y};
t.vertices[i] = p;
}
}
/**
* Evaluate a point with respect to the equation defining the line
* passing through a line segment.
*
* A line is defined as the set of points satisfying f(x,y) = 0
* where f(x,y) is a function of the form ax + by + c. This function
* computes that f(x,y) for an arbitrary point, which might not be
* on that line.
*
* @param line a line segment
* @param p a point at which we ant the line function evaluated
* @return A value that is zero for points on the line, positive for all
* points on one side of the line, and negative for all points
* on the other side of the line.
*/
double eval (LineSegment line, Point p)
{
//*** implement this function
}
/**
* Check two points to see if they lie on the same side of a line
*
* @param p1 a point
* @param p2 another point
* @param line a line segment
* @return true iff p1 and p2 are on the same side of the line
* passing through the given line segment.
* If either or both points lie exactly on the line,
* return false.
*/
bool areOnSameSideOf (Point p1, Point p2, LineSegment line)
{
//*** implement this function
}
/**
* Check to see if a point lies on the interior of a triangle.
*
* @param p a point
* @param t a triangle
* @return true iff p lies in the interior of the trangle t
*/
bool isWithin (Point p, Triangle t)
{
Point centroid = {0.0, 0.0};
for (int i = 0; i < 3; ++i)
{
centroid.x += t.vertices[i].x;
centroid.y += t.vertices[i].y;
}
centroid.x /= 3.0;
centroid.y /= 3.0;
for (int i = 0; i < 3; ++i)
{
LineSegment side = {t.vertices[i], t.vertices[(i+1)%3]};
if (!areOnSameSideOf (p, centroid, side))
return false;
}
return true;
}
/**
* Check to see if one triangle lies entirely within the
* interior of the other.
*
* @param outer
* @param inner
* @return true iff inner lies entirely within the interior of outer
*/
bool contains (Triangle outer, Triangle inner)
{
for (int i = 0; i < 3; ++i)
{
if (!isWithin(inner.vertices[i], outer))
return false;
}
return true;
}
/**
* Check to see if either of two triangles is
* entirely contained within the other.
*
* @param t1
* @param t2
*/
void checkForNesting (Triangle t1, Triangle t2)
{
if (contains(t1, t2) || contains(t2, t1))
cout << "These triangles nest." << endl;
else
cout << "These triangles do not nest." << endl;
}
int main (int argc, char** argv)
{
cout << "Enter the x,y coordinates of three vertices of a triangle: " << flush;
Triangle t1;
readTriangle (t1, cin);
cout << "Enter the x,y coordinates of three vertices of another triangle: " << flush;
Triangle t2;
readTriangle (t2, cin);
checkForNesting (t1, t2);
}
