Wednesday, January 17, 2007

如何判断一个点在不在三角形内部

用MEEP做计算时,初始化epsilon,想做一个三角形,这就需要判断这个点在不在三角形的内部。
写了一小段C++代码来判断一个点是不是在三角形内部。
基本思想:
这个点和三角形三个顶点构成了三个小三角形,
比较这三个小三角形的面积之和与原三角形的面积,如果相等,说明这个点落在三角形内部。
如果三个小三角形的面积之和大于原三角形的面积,则说明这个点落在三角形的外面。

技术细节:
1、已知三角形三个顶点的坐标,求三角形的面积。1/2*|axb|即是三角形的面积。
a和b分别是两条边。
2、判断大小时,要注意数值误差,也就是1e-6的作用。

double area(const vec p, const vec p2, const vec p3)
{
double x = p2.x() - p.x();
double y = p2.y() - p.y();

double x2 = p3.x() - p.x();
double y2 = p3.y() - p.y();

double s = abs(x*y2 - x2*y)/2.;
return s;
}

bool inside(const vec insert, const vec corner, const vec corner2, const vec corner3)
{
double s = area(corner, corner2, corner3);
double ss = area(insert, corner, corner2);
double ss2 = area(insert, corner2, corner3);
double ss3 = area(insert, corner, corner3);

if ( ss + ss2 + ss3 - s > 1e-6 ) return false;

return true;
}