主题:三角形内部点的判别问题!!~~
zoucheng151785
[专家分:0] 发布于 2010-05-18 19:48:00
请高手指点算法
如何判断一个点在三角形内部!~~
小弟要做一个关于这个判断的程序!~~
回复列表 (共7个回复)
沙发
雪光风剑 [专家分:27190] 发布于 2010-05-18 20:09:00
给定三个顶点,就会有3个直线方程
求出这三个直线方程之后求出其围成的区域即可
板凳
zoucheng151785 [专家分:0] 发布于 2010-05-18 20:13:00
说的还是有点笼统啊!!~~这样也不是很好判断啊 !~~呵呵 !
能不能具体一点!~~
3 楼
NTFNTF123 [专家分:100] 发布于 2010-05-18 21:27:00
算法:1、利用area=sqrt(s*(s-a)*(a-b)*(s-c))公式 定义一个面积函数area!
2、用两点间的距离公式算出要求的点与三角线三定点的距离。
3、将要求的点与三定点之间的连线组成的3个小三角形分别求出面积。
4、if(这三个小三角形的面积之和==大三角形的面积)
printf(“该点在三角形内部!”);
else
printf(“该点不在三角形内部!”);
4 楼
强强 [专家分:4740] 发布于 2010-05-18 21:29:00
去看解析几何
5 楼
mo_0820 [专家分:50] 发布于 2010-05-19 21:36:00
3楼正解,用海伦公式。关键就怕误差会不会影响判断。
下面我编了个判断程序,用严格相等得不到正确结果,可以试一下。用差值很小判断会好一点,但也有误差。用1楼的方法可能会好点,你可以参考下高中数学中线性规划里面确定区域的方法。
#include<stdio.h>
#include<math.h>
main()
{
int i;
double a,b,c,d,e,f,s,area,area1,p[4][2];
printf("点输入格式:x,y回车\n请输入三顶点:\n");
for(i=0;i<3;i++)
scanf("%lf,%lf",&p[i][0],&p[i][1]);
a=sqrt(pow(p[0][0]-p[1][0],2)+pow(p[0][1]-p[1][1],2));
b=sqrt(pow(p[0][0]-p[2][0],2)+pow(p[0][1]-p[2][1],2));
c=sqrt(pow(p[2][0]-p[1][0],2)+pow(p[2][1]-p[1][1],2));
s=(a+b+c)/2;
area=sqrt(s*(s-a)*(s-b)*(s-c));
for(;;)
{
printf("请输入判断点:\n");
scanf("%lf,%lf",&p[3][0],&p[3][1]);
d=sqrt(pow(p[3][0]-p[0][0],2)+pow(p[3][1]-p[0][1],2));
e=sqrt(pow(p[3][0]-p[1][0],2)+pow(p[3][1]-p[1][1],2));
f=sqrt(pow(p[3][0]-p[2][0],2)+pow(p[3][1]-p[2][1],2));
s=(a+d+e)/2;
area1=sqrt(s*(s-a)*(s-d)*(s-e));
s=(b+d+f)/2;
area1+=sqrt(s*(s-b)*(s-d)*(s-f));
s=(c+e+f)/2;
area1+=sqrt(s*(s-c)*(s-e)*(s-f));
printf("判断点是否在三角形内:");
//if(area==area1)
if(fabs(area-area1)<1e-12)
printf("yes!\n");
else
printf("no!\n");
}
}
6 楼
雪光风剑 [专家分:27190] 发布于 2010-05-19 21:58:00
海伦公式的话近似的次数太多了,很容易出差错
7 楼
eastcowboy [专家分:25370] 发布于 2010-05-19 21:59:00
有多种方法。
方法一:(解析几何)
假设已知的三个点为A, B, C,则平面上任何一点P都可以表示为:
P = A + m(B - A) + n(C - A)
其中m和n是未知数。
如果是二维平面,上述方程可以分开得到两个方程:
P.x = A.x + m(B.x - A.x) + n(C.x - A.x)
P.y = A.y + m(B.y - A.y) + n(C.y - A.y)
除了m,n,其它都是已知的,解这个二元一次方程组,得到m和n的值。如果m和n的值都在(0, 1)区间,则P在三角形内部。
三维平面也可以类似处理,因为所有点都在同一平面上,仍然可以解出m, n。
方法二:(线性代数)
已知四个点A, B, C, P,且在同一平面。如果P同时在BA, CB, AC的顺时针方向,或者P同时在BA, CB, AC的逆时针方向,则P在三角形ABC内
根据线性代数的知识,问题转化为:如果CPXCB、BPXBA、APXAC这三次叉乘均有定义,并且结果向量的方向相同,则P在三角形ABC内。
其中:叉乘可以直接使用向量叉乘公式,判断方向是否相同,可以把向量点乘之后看正负号。
在编程时,不必考虑叉乘是否有定义,如果两个向量的方向相同(叉乘无定义),则代入叉乘公式计算结果为零,仍然可以继续点乘,不影响最终的判断。
我在实际工作中使用了第二种方法,而DirectX提供的函数则倾向于第一种方法的思路。
DirectX提供了一个函数,用于检查三维空间中一条射线是否射中了一个三角形。如果射中,则求出射中的点坐标,并且求出“方法一”中所描述的m, n的值。
NTFNTF123在4楼的方法应该也是可以的,但是有几处涉及到开平方,计算量恐怕要大一些。
我来回复