1. 一種是用矢量叉乘法：
由三個頂點向所求的點引出矢量（注意方向），然后任意用其中兩個矢量形成平面，再用這個平面和剩下的矢量叉乘，得出一個新矢量，方向向里，則在三角形外，反之在里面。
2.用面積方法
#include<stdio.h>
#include<math.h>
struct TPoint 
{
float x;
float y;
};
//求叉積
float mul(struct TPoint p1, struct TPoint p2, struct TPoint p0) {
return ((p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y));
}
/**//*由三個頂點向所求的點引出矢量（注意方向），然后任意用其中兩個矢量形成平面，
* 再用這個平面和剩下的矢量叉乘，得出一個新矢量，方向向里，則在三角形外，反之在里面。
*/
int inside(struct TPoint tr[], struct TPoint p) {
int i;
for (i = 0; i < 3; i++)
if (mul(p, tr[i], tr[(i + 1) % 3]) * mul(p, tr[(i + 2) % 3], tr[(i + 1) % 3]) > 0)
return 0;
return 1;
}
float area(struct TPoint p1, struct TPoint p2, struct TPoint p3) {
return fabs((p1.x - p3.x)*(p2.y - p3.y)-(p2.x - p3.x)*(p1.y - p3.y));
}
//用面積判斷p是否在三角形內
int inside2(struct TPoint tr[], struct TPoint p) {
if (fabs(area(tr[0], tr[1], tr[2]) -
area(p, tr[1], tr[2]) -
area(tr[0], p, tr[2]) -
area(tr[0], tr[1], p)) < 1.0e-20)
return 1;
else
return 0;
}
int main() {
struct TPoint tr[3] = {{-1, 1},{1, 0},{3, 0}}, p = {1, 2};
//方法一
printf("algorithm 1:");
if (inside(tr, p))
printf("In\n");
else
printf("Out\n");
//方法一
printf("algorithm 2:");
if (inside2(tr, p))
printf("In\n");
else
printf("Out\n");
}posted on 2010-10-12 09:40
孟起 閱讀(1903)
評論(0) 編輯 收藏 引用 所屬分類:
計算幾何