回 帖 发 新 帖 刷新版面

主题:三角形内部点的判别问题!!~~

请高手指点算法


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

小弟要做一个关于这个判断的程序!~~

回复列表 (共7个回复)

沙发

给定三个顶点,就会有3个直线方程
求出这三个直线方程之后求出其围成的区域即可

板凳


说的还是有点笼统啊!!~~这样也不是很好判断啊 !~~呵呵 !

能不能具体一点!~~

3 楼


算法:1、利用area=sqrt(s*(s-a)*(a-b)*(s-c))公式 定义一个面积函数area!

      2、用两点间的距离公式算出要求的点与三角线三定点的距离。
     
      3、将要求的点与三定点之间的连线组成的3个小三角形分别求出面积。
  
      4、if(这三个小三角形的面积之和==大三角形的面积)
           printf(“该点在三角形内部!”);
         else 
           printf(“该点不在三角形内部!”);

4 楼

去看解析几何

5 楼

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 楼

海伦公式的话近似的次数太多了,很容易出差错

7 楼

有多种方法。

方法一:(解析几何)
假设已知的三个点为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楼的方法应该也是可以的,但是有几处涉及到开平方,计算量恐怕要大一些。

我来回复

您尚未登录,请登录后再回复。点此登录或注册