nestedTriangles.cpp（附）说明：
该程序将一对三角形作为输入，指定为给出每个三角形顶点的坐标。然后它会确定其中一个三角形是否“嵌套”在另一个三角形内，这意味着一个三角形完全位于另一个三角形的内部。
伪代码：
当且仅当第一个三角形的所有三个顶点都位于第二个三角形的内部时，一个三角形位于另一个三角形内。假设我们有一个三角形，其顶点为 A、B 和 C，分别由坐标 (xA, yA)、(xB, yB) 和 (xC, yC) 描述。三角形的边是线段 AB、BC 和 CA。通过两个点 (x1, y1) 和 (x2, y2) 的线可以被认为是满足方程 f(x,y) = 0 的点 (x,y) 的集合，其中 f(x,y) 是给出 f(x,y) = (x - x1) (y2 - y1) - (y - y1) (x2 - x1) 关于 f(x,y) 的一个有趣的事情是我们可以用它来确定任意点 (x,y) 位于直线的哪一侧：
如果 f(x,y) = 0，则该点正好在线上。f(x,y) > 0 的所有点都在直线的一侧，而 f(x,y) < 0 的所有点都在另一侧 所以判断一个点 (x,y) 是否存在的问题) 位于三角形的内部，可以检查构成三角形的三条线中的每条线的 f(x,y) 的符号。一个复杂的因素是，对于任何给定的三角形，我们不知道这三个符号是否应该全部为正、全部为负，或两者兼而有之。
三角形的质心可以计算为顶点的 x 和 y 坐标的“平均值”： xcen = (xA + xB + xC)/3 ycen = (yA + yB + yC)/3 这个点 (xcen, ycen) 肯定在三角形内部（除非三角形是“退化的”并且没有内部点）。因此，确定 (x,y) 是否在三角形内部的问题可以通过检查它是否与 (xcen, ycen) 位于每个三角形线段的同一侧来解决。
我需要的：
为 LineSegment 填充缺少的结构类型，我需要每个线段有两个字段，称为“endPoint1”和“endPoint2”，每个字段类型均为 Point。Point 类型已声明。然后我想为函数 eval 和 areOnSameSideOf 填充缺失的主体，它们操纵线段。我认为从 areOnSameSideOf 内部调用 eval 将简化后者的实现。
#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
*/
struct LineSegment
{
Point endPoint1;
Point endPoint2;
};
/**
* 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)
{
//*** see "What I need"
}
/**
* 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)
{
//*** see "What I need"
}
/**
* 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);
}