如何判断一个点是否在三角形内

时间:2022-04-30 10:26:16
在二维坐标系中,已知三角形三顶点坐标,对于坐标系中任意一点如何判断其是否在三角形内(包括边上)?

25 个解决方案

#1


数学题么?

#2


额,这个结帖率是101.52%是怎么回事~~~~

#3


叉乘,结果正负号都相同

#4


http://topic.csdn.net/t/20021027/11/1128714.html

#5


设三角形三个点
A(a1,a2),B(b1,b2),C(c1,c2)
三条边方程
BC:fa(x,y)=0
AC:fb(x,y)=0
AB:fc(x,y)=0
以BC为例,在三角形内的点必须与点A在BC的同侧
所以对于点D(x,y)
在三角形内首先要满足fa(x,y)*fa(a1,a2)>0
其他边也同理
所以只要比较
fa(x,y)*fa(a1,a2)
fb(x,y)*fb(b1,b2)
fc(x,y)*fc(c1,c2)
这三个数的正负性
1三个数都是正数:D在三角形内
2至少有一个负数:D在三角形外
3有且只有一个0,另两个为正数:在三角形边上
4有且只有一个0,一个正数一个负数:在三角形边的延长线上,也算在三角形外,因为满足2
5有二个0:在三角形的顶点上
6不可能出现3个0,或3个负数,或一个0两个负数的情况

#6


有没有更简单点的解决方法呢

#8


http://blog.csdn.net/dracularking/article/details/2217180

#9


类似开线形规划?

#10


计算机几何

#11



鄙人很懒,就唠叨两句思路吧:

输入坐标  (X,Y)

既然是个三角形  那么3边也就是有3个方程式....三角区域可以理解为3个不等式

那么就有思路了   包括边线  意思就是  <=  或 >= 不等式

也就是说同时满足3个不等式的情况下,才算在三角形内

#12


大家都很厉害!

#13


用面积比较感觉比较爽,并且直观。

#14


从已知的三个点中可以两两确定一条直线, 这时可以根据 (y1-y2)/(x1-x2) 分别求出条直线的斜率,分别
等于tan1, tan2, tan3. 这时 再根据要判断的点(x0, y0), 分别与三角形的三个点分别求相应的斜率。
如何它,都在任意的两个斜率之间的,它就是在三角形内。

typedef struct {
   double  x;
   double  y;
} Point;

double tan(Point p1, Point p2)
{
    return (p1.y - p2.y)/(p1.x - p2.x);
}

double maxOmin(double t1, double t2, bool MaxFlag) {
   return (MaxFlag ? (t1 < t2 ? t2 : t1) : (t1 < t2 ? t1 : t2));
}

bool isIn(Point p1, Point p2, Point p3, Point z)
{
   double min, max;
   double t12 = tan(p1, p2);
   double t13 = tan(p1, p3);
   max = maxOmin(t12, t13, true);
   min = maxOmin(t12, t13, false);
   if (min <= tan(p1, z) && tan(p1, z) <= max)
    ....
   继续比较下去
}

没证明过

#15


利用面積來判斷
假設:△ABC, 則D點是否在三角形內?
IF △ABC面積=△ABD+△BCD+△ACD(面積)
即是在△內或△上。
定義說明:△ABC各點分別為(X1,Y1),(X2,Y2)(X3,Y3) D點(PX,PY)
以下是用VB語法寫成~剛好最近有寫到~就分享囉!!
'===============================================================
        Dim X1,X2,X3,Y1,Y2,Y3,PX,PY As Single
        Dim ABC, ADB, BDC, CDA As Single         '面積
        Dim ab, bc, ac, ad, bd, cd As Single     '線段
        Dim s As Single
      
             '畢氏定理 求線段長 (x1,y1)到(x2,y2)
                     '(x1-x2)^2+(y1-y2)^2 開根號
            ab = Math.Sqrt((X1 - X2) ^ 2 + (Y1 - Y2) ^ 2)    
            bc = Math.Sqrt((X2 - X3) ^ 2 + (Y2 - Y3) ^ 2)             
            ac = Math.Sqrt((X1 - X3) ^ 2 + (Y1 - Y3) ^ 2)
            ad = Math.Sqrt((X1 - PX) ^ 2 + (Y1 - PY) ^ 2)
            bd = Math.Sqrt((X2 - PX) ^ 2 + (Y2 - PY) ^ 2)
            cd = Math.Sqrt((X3 - PX) ^ 2 + (Y3 - PY) ^ 2)


            '海龍公式  △ABC 邊長為a,b,c  
            '          s=(a+b+c)/2
            '         面積 = s(s-a)(s-b)(s-c)開根號
            s = (ab + bc + ac) / 2                             
            ABC = Math.Sqrt(s * (s - ab) * (s - bc) * (s - ac)) 
        
            s = (ab + bd + ad) / 2                                     
            ADB = Math.Sqrt(s * (s - ab) * (s - bd) * (s - ad))

            s = (bc + cd + bd) / 2
            BDC = Math.Sqrt(s * (s - bc) * (s - cd) * (s - bd))

            s = (ac + ad + cd) / 2
            CDA = Math.Sqrt(s * (s - ac) * (s - ad) * (s - cd))

            If ABC >= ADB + BDC + CDA - 0.05 And ABC <= ADB + BDC + CDA + 0.05 Then
              msgbox("D點在△內")    '因為有開過根號,所以加上一個極小的誤差值
            Else

搞定!!

#16


对啊~ 怎么没人问了?lz,解释下呗~
好久不学数学了,怀念呢!
这么多方法哦~!

引用 2 楼 xiaoguangzaia 的回复:
额,这个结帖率是101.52%是怎么回事~~~~

#17


不会,汗

#18


高中数学,向量。

#19


引用 2 楼 xiaoguangzaia 的回复:
额,这个结帖率是101.52%是怎么回事~~~~

#21


O,C是否在AB同侧 
O,A是否在BC同侧 
O,B是否在AC同侧 
都成立就通过

#22


根据面积,如果在内部,三个小三角面积=大三角形面积
外部不等

#23


LZ的结贴率。。。

#24


该回复于2012-01-11 16:20:08被版主删除

#25


个人觉得用斜率比较有缺陷,如果将三角形任意两边延长第三条边平移到延长的交线上,这样的斜率依然是无法判断额。。。。还是觉得先用三角形的面积比较合适,

#1


数学题么?

#2


额,这个结帖率是101.52%是怎么回事~~~~

#3


叉乘,结果正负号都相同

#4


http://topic.csdn.net/t/20021027/11/1128714.html

#5


设三角形三个点
A(a1,a2),B(b1,b2),C(c1,c2)
三条边方程
BC:fa(x,y)=0
AC:fb(x,y)=0
AB:fc(x,y)=0
以BC为例,在三角形内的点必须与点A在BC的同侧
所以对于点D(x,y)
在三角形内首先要满足fa(x,y)*fa(a1,a2)>0
其他边也同理
所以只要比较
fa(x,y)*fa(a1,a2)
fb(x,y)*fb(b1,b2)
fc(x,y)*fc(c1,c2)
这三个数的正负性
1三个数都是正数:D在三角形内
2至少有一个负数:D在三角形外
3有且只有一个0,另两个为正数:在三角形边上
4有且只有一个0,一个正数一个负数:在三角形边的延长线上,也算在三角形外,因为满足2
5有二个0:在三角形的顶点上
6不可能出现3个0,或3个负数,或一个0两个负数的情况

#6


有没有更简单点的解决方法呢

#7


#8


http://blog.csdn.net/dracularking/article/details/2217180

#9


类似开线形规划?

#10


计算机几何

#11



鄙人很懒,就唠叨两句思路吧:

输入坐标  (X,Y)

既然是个三角形  那么3边也就是有3个方程式....三角区域可以理解为3个不等式

那么就有思路了   包括边线  意思就是  <=  或 >= 不等式

也就是说同时满足3个不等式的情况下,才算在三角形内

#12


大家都很厉害!

#13


用面积比较感觉比较爽,并且直观。

#14


从已知的三个点中可以两两确定一条直线, 这时可以根据 (y1-y2)/(x1-x2) 分别求出条直线的斜率,分别
等于tan1, tan2, tan3. 这时 再根据要判断的点(x0, y0), 分别与三角形的三个点分别求相应的斜率。
如何它,都在任意的两个斜率之间的,它就是在三角形内。

typedef struct {
   double  x;
   double  y;
} Point;

double tan(Point p1, Point p2)
{
    return (p1.y - p2.y)/(p1.x - p2.x);
}

double maxOmin(double t1, double t2, bool MaxFlag) {
   return (MaxFlag ? (t1 < t2 ? t2 : t1) : (t1 < t2 ? t1 : t2));
}

bool isIn(Point p1, Point p2, Point p3, Point z)
{
   double min, max;
   double t12 = tan(p1, p2);
   double t13 = tan(p1, p3);
   max = maxOmin(t12, t13, true);
   min = maxOmin(t12, t13, false);
   if (min <= tan(p1, z) && tan(p1, z) <= max)
    ....
   继续比较下去
}

没证明过

#15


利用面積來判斷
假設:△ABC, 則D點是否在三角形內?
IF △ABC面積=△ABD+△BCD+△ACD(面積)
即是在△內或△上。
定義說明:△ABC各點分別為(X1,Y1),(X2,Y2)(X3,Y3) D點(PX,PY)
以下是用VB語法寫成~剛好最近有寫到~就分享囉!!
'===============================================================
        Dim X1,X2,X3,Y1,Y2,Y3,PX,PY As Single
        Dim ABC, ADB, BDC, CDA As Single         '面積
        Dim ab, bc, ac, ad, bd, cd As Single     '線段
        Dim s As Single
      
             '畢氏定理 求線段長 (x1,y1)到(x2,y2)
                     '(x1-x2)^2+(y1-y2)^2 開根號
            ab = Math.Sqrt((X1 - X2) ^ 2 + (Y1 - Y2) ^ 2)    
            bc = Math.Sqrt((X2 - X3) ^ 2 + (Y2 - Y3) ^ 2)             
            ac = Math.Sqrt((X1 - X3) ^ 2 + (Y1 - Y3) ^ 2)
            ad = Math.Sqrt((X1 - PX) ^ 2 + (Y1 - PY) ^ 2)
            bd = Math.Sqrt((X2 - PX) ^ 2 + (Y2 - PY) ^ 2)
            cd = Math.Sqrt((X3 - PX) ^ 2 + (Y3 - PY) ^ 2)


            '海龍公式  △ABC 邊長為a,b,c  
            '          s=(a+b+c)/2
            '         面積 = s(s-a)(s-b)(s-c)開根號
            s = (ab + bc + ac) / 2                             
            ABC = Math.Sqrt(s * (s - ab) * (s - bc) * (s - ac)) 
        
            s = (ab + bd + ad) / 2                                     
            ADB = Math.Sqrt(s * (s - ab) * (s - bd) * (s - ad))

            s = (bc + cd + bd) / 2
            BDC = Math.Sqrt(s * (s - bc) * (s - cd) * (s - bd))

            s = (ac + ad + cd) / 2
            CDA = Math.Sqrt(s * (s - ac) * (s - ad) * (s - cd))

            If ABC >= ADB + BDC + CDA - 0.05 And ABC <= ADB + BDC + CDA + 0.05 Then
              msgbox("D點在△內")    '因為有開過根號,所以加上一個極小的誤差值
            Else

搞定!!

#16


对啊~ 怎么没人问了?lz,解释下呗~
好久不学数学了,怀念呢!
这么多方法哦~!

引用 2 楼 xiaoguangzaia 的回复:
额,这个结帖率是101.52%是怎么回事~~~~

#17


不会,汗

#18


高中数学,向量。

#19


引用 2 楼 xiaoguangzaia 的回复:
额,这个结帖率是101.52%是怎么回事~~~~

#20


#21


O,C是否在AB同侧 
O,A是否在BC同侧 
O,B是否在AC同侧 
都成立就通过

#22


根据面积,如果在内部,三个小三角面积=大三角形面积
外部不等

#23


LZ的结贴率。。。

#24


该回复于2012-01-11 16:20:08被版主删除

#25


个人觉得用斜率比较有缺陷,如果将三角形任意两边延长第三条边平移到延长的交线上,这样的斜率依然是无法判断额。。。。还是觉得先用三角形的面积比较合适,