快速判断点在2D三角形内
[ 2007-01-10 18:30:49 | 作者: Admin ]
伪代码(Pseudocode) 如下:
评论Feed: http://www.azure.com.cn/feed.asp?q=comment&id=235
bool pointIn2DTri(vec2 p, vec2 a, vec2 b, vec2 c)
{
vec2 v1, v2;
float area[3];
bool zero_area[3];
v1 = b - a;
v2 = p - a;
//2D向量叉乘的几何意义在于,等于V1,V2向量组成三角形面积的两倍
area[0] = crossproduct(v1,v2);
//判断浮点数是否等于0
zero_area[0] = realequal(area[0], 0.0);
v1 = c - b;
v2 = p - b;
area[1] = crossproduct(v1, v2);
zero_area[1] = realequal(area[1], 0.0);
if(!zero_area[0] && !zero_area[1] &&
sign(area[0])!=sign(area[1])) //一个是正面积一个是负面积
{
return false;
}
v1 = a - c;
v2 = p - c;
area[2] = crossproduct(v1, v2);
zero_area[2] = realequal(area[2], 0.0);
//和相临的边再判断
if((!zero_area[0] && !zero_area[2] && sign(area[0])!=sign(area[2])) ||
(!zero_area[1] && !zero_area[2] && sign(area[1])!=sign(area[2])))
{
return false;
}
return true;
}
{
vec2 v1, v2;
float area[3];
bool zero_area[3];
v1 = b - a;
v2 = p - a;
//2D向量叉乘的几何意义在于,等于V1,V2向量组成三角形面积的两倍
area[0] = crossproduct(v1,v2);
//判断浮点数是否等于0
zero_area[0] = realequal(area[0], 0.0);
v1 = c - b;
v2 = p - b;
area[1] = crossproduct(v1, v2);
zero_area[1] = realequal(area[1], 0.0);
if(!zero_area[0] && !zero_area[1] &&
sign(area[0])!=sign(area[1])) //一个是正面积一个是负面积
{
return false;
}
v1 = a - c;
v2 = p - c;
area[2] = crossproduct(v1, v2);
zero_area[2] = realequal(area[2], 0.0);
//和相临的边再判断
if((!zero_area[0] && !zero_area[2] && sign(area[0])!=sign(area[2])) ||
(!zero_area[1] && !zero_area[2] && sign(area[1])!=sign(area[2])))
{
return false;
}
return true;
}
[最后修改由 Admin, 于 2007-01-11 10:39:49]
评论Feed: http://www.azure.com.cn/feed.asp?q=comment&id=235
这篇日志没有评论.










