[演示] 判断点是否处于三角形内的算法分析

http://bbs.wow8.org/thread-94298-1-1.html

 

由于某些特殊需求,有时候需要判断一个点是不是在某一个三角形内面.虽然这样的情况很少,而且不是必须的,但既然有人提到了,还是说说相应的解决方法.

在接触问题之前,有必要先复习一下初中的平面解析几何知识:直线的代数解析式.
(1)斜截式 y=Kx+b
(2)点斜式 y-y1=K(x-x1)
(3)两点式 y-y1=(y2-y1)/(x2-x1)*(x-x1)=(x-x1)*(y2-y1)/(x2-x1)   (x1!=x2) 
其中,在式(1)中,K代表直线的斜率,b代表直线在Y坐标轴上的截距,也就是直线与Y轴交点的纵坐标;
在式(2)中,(x1,y1)是直线经过的一个点,K是直线的斜率;
在式(2)中,(x1,y1)和(x2,y2)是直线经过的两个点,且x1不等于x2;

在平面解析几何中,常常要判断一点与一条直线的位置关系.说到位置关系,无外乎三种:在直线上,在直线上方,在直线下方.
在数学上,判断这种关系的方法是将点的坐标带入直线解析式,然后观察结果正负.
步骤(1):将直线解析式稍微做个变换,将所有项都移动到左边,例如: y-Kx+b=0; y-y1-K(x-x1)=0; y-y1-(x-x1)*(y2-y1)/(x2-x1)=0
步骤(2):将点的坐标值带入上面的式子,计算结果;
步骤(3):如果最终结果等于0,说明点在直线上;如果最终结果大于0,说明点在直线上方;如果最终结果小于0,说明点在直线下方;

在Jass中,上面的过程可以写成这样的函数(Lx1!=Lx2,之所以不考虑相等的情况,是因为用不上,而且考虑的话,情况会变得非常复杂):

 + Shingo Jass Highlighter 0.41

//参数意义: 
//(Lx1,Ly1),(Lx2,Ly2)是成对的,L前缀表示这是直线上的点的坐标,因为在WE中,我们很多情况都是通过点来确定直线的,直接使用斜率的相对较少 
//(checkX,checkY),顾名思义,这就是要检测的点的坐标值 

//判断是否在直线上 
function IsOn takes real Lx1, real Ly1, real Lx2, real Ly2, real checkX, real checkY returns boolean 
    if (checkY-Ly1-(checkX-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))==0 then 
        return true 
    endif 
    return false 
endfunction 

//判断是否在函数上方 
function IsAbove takes real Lx1, real Ly1, real Lx2, real Ly2, real checkX, real checkY returns boolean 
    if (checkY-Ly1-(checkX-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))>0 then 
        return true 
    endif 
    return false 
endfunction 

//判断是否在函数下方 
function IsBelow takes real Lx1, real Ly1, real Lx2, real Ly2, real checkX, real checkY returns boolean 
    if (checkY-Ly1-(checkX-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))<0 then 
        return true 
    endif 
    return false 
endfunction

当然,真正用的时候,我们不可能写三个分散的函数,而是用一个代替: 

 + Shingo Jass Highlighter 0.41

function GetPositionRelation takes real Lx1, real Ly1, real Lx2, real Ly2, real checkX, real checkY returns integer 
    //为了避免误使用Lx1==Lx2来调用这个函数,我们对数据稍微做下改变 
    if Lx1==Lx2 then 
        set Lx2=Lx2+1       //偏移一下下,看不出来的 
    endif 

    if (checkY-Ly1-(checkX-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))>0 then 
        return 1 
    elseif (checkY-Ly1-(checkX-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))<0 then 
        return -1 
    else 
        return 0 
    endif 
endfunction

函数返回1,说明在直线上方,返回-1,说明在直线下方,返回0,说明在直线上. 

对于固定的一个三角形,要判断一个点在不在它里面很简单:将点的坐标带入三条边的代数解析式计算,然后根据结果正负值即可知其位置关系.但是若三角形不确定(可以自由旋转或者可以改变大小),那么再带入计算,你就会发现....需要考虑的情况太多了!!!

在一个平面上,任意两两相交的直线把平面分成7个区域,假设三个交点分别是(x1,y1),(x2,y2),(x3,y3),三条直线分别为L12,L23,L13.
假设有一个点是(x,y),我们设三个整数变量,分别等于

 + Shingo Jass Highlighter 0.41

local integer I12=GetPositionRelation(x,y,x1,y1,x2,y2) 
local integer I23=GetPositionRelation(x,y,x2,y2,x3,y3) 
local integer I13=GetPositionRelation(x,y,x1,y1,x3,y3)

 

那么I12*I23*I13的值也是三种情况:等于0,等于1,或者等于-1.
对于不同的三角形,不同的位置关系,这个值是不定的.
对于不同的三角形,即使位置关系相同,这个值也不一定相等,关键还得看三角形本身.
这样一来,通过F(x,y)=I12*I23*I13来确定点和三角形位置关系的想法破灭了,我们只能从长计议..
尽管如此,我们可以肯定的一点是:当一个点位于三角形三个角所对的区域时,函数F(x,y)的值等于点在三角形内时的值.
(很遗憾,由于某种不明的原因,我始终不能上传图片....也许这里有些地方讲得不是很清楚,你们还是自己在纸上画一下吧.)

下面结合一个具体的例子来讲讲我的两种解法:判断任意一个点是否在一个可以自由旋转角度和改变大小的等腰三角形里面.

困难在哪里:假如说这个三角形是等边三角形,原来有一个顶角竖直向上,底边与X轴平行.这时候来判断三角形内部的点的坐标的话,应该是在底边上方,而在两个侧边下方.如果将三角形绕底边的终点顺时针旋转45°,再来判断会是怎样的呢?囧了,这时候是底边和右侧边上方,左侧边下方了... 复杂之处不仅仅在这一个象限,如果将三角形的顶角转到指向第二象限,你会发现同样的情况,然后还有第三,第四象限....Oh,my god!!!越来越复杂了...

[ 本帖最后由 cctvfive 于 2009-3-27 20:05 编辑 ]

 

 

 

 

 

方法一:旋转法

对于一个等腰三角形,如果都能将其底边转到与X轴平行,而且顶角朝上,那么事情就变得简单了:点位于底边上方,两条侧边下方.下面就开始我们的旋转算法.

假设一点A(x,y),坐标原点为O,那么将向量OA(抱歉,没法画上面那个箭头)沿顺时针方向旋转α角度之后,新的A'点坐标为(x',y').

1. L=(x*x+y*y)^0.5
   
2. x=L*Cosθ
   
3. y=L*Sinθ
   
4. x'=L*Cos(θ-α)=L*Cosθ*Cosα+L*Sinθ*Sinα=x*Cosα+y*Sinα
   
5. y'=L*Sin(θ-α)=L*Sinθ*Cosα-L*Cosθ*Sinα=y*Cosα-x*Sinα

复制代码

如果不是绕原点旋转的,那么上面的x和y都是相对坐标,使用时要切换到绝对坐标.
假设旋转中心坐标为M(Xm,Ym),旋转前点A坐标为(Ax,Ay),旋转后为B(Bx,By).
那么在上面的式子中,

1. x=Ax-Mx
   
2. y=Ay-My
   
3. x'=Bx-Mx
   
4. y'=By-My
   
5. 于是有:
   
6. Bx-Mx=(Ax-Mx)*Cosα+(Ay-My)*Sinα
   
7. By-My =(Ay-My)*Cosα-(Ax-Mx)*Sinα

复制代码

看起来很复杂....不过还好,我们这里用的时候会化简..

 + Shingo Jass Highlighter 0.41

function IsInTriangle takes real startX, real startY, real face, real L, real H ,real checkX, real checkY returns boolean 
    local real angle=face-90       //要旋转的角度,旋转后三角形处于最容易分析的角度 
     
    //Left_Point 
    //Ax-Mx=-L*SinBJ(face) 
    //Ay-My= L*CosBJ(face) 
    //local real Leftx=startX-L*SinBJ(face) 
    //local real Lefty=startY+L*CosBJ(face) 
     
    local real Left_x=startX-L*SinBJ(face)*CosBJ(angle)+L*CosBJ(face)*SinBJ(angle) 
    local real Left_y=startY+L*CosBJ(face)*CosBJ(angle)+L*SinBJ(face)*SinBJ(angle) 
     
    //Right_Point 
    //Ax-Mx= L*SinBJ(face) 
    //Ay-My=-L*CosBJ(face) 
    //local real Rightx=startX+L*SinBJ(face) 
    //local real Righty=startX-L*CosBJ(face) 
     
    local real Right_x=startX+L*SinBJ(face)*CosBJ(angle)-L*CosBJ(face)*SinBJ(angle) 
    local real Right_y=startY-L*CosBJ(face)*CosBJ(angle)-L*SinBJ(face)*SinBJ(angle) 
     
    //Top_Point 
    //Ax-Mx=H*CosBJ(face) 
    //Ay-My=H*SinBJ(face) 
    //local real Topx=startX+H*CosBJ(face) 
    //local real Topy=startY+H*SinBJ(face) 
     
    local real Top_x=startX+H*CosBJ(face)*CosBJ(angle)+H*SinBJ(face)*SinBJ(angle) 
    local real Top_y=startY+H*SinBJ(face)*CosBJ(angle)-H*CosBJ(face)*SinBJ(angle) 
     
    //Check_Point 
    //Ax-Mx=checkX-startX 
    //Ay-My=checkY-startY 
    local real Check_x=startX+(checkX-startX)*CosBJ(angle)+(checkY-startY)*SinBJ(angle) 
    local real Check_y=startY+(checkY-startY)*CosBJ(angle)-(checkX-startX)*SinBJ(angle) 

    if GetPositionRelation(Left_x,Left_y,Right_x,Right_y,Check_x,Check_y)>=0 and GetPositionRelation(Left_x,Left_y,Top_x,Top_y,Check_x,Check_y)<=0 and GetPositionRelation(Right_x,Right_y,Top_x,Top_y,Check_x,Check_y)<=0 then 
        return true 
    endif 
    return false 
endfunction

方法二:未命名~~~

上面那个方法稍微有点复杂,下面介绍个更加简单的..

在等腰三角形的底边上的高上任取一点P,那么P点必定在三角形内面,这点毋庸质疑.如果给定一个点,它与点P处于三角形三条边的同侧,那么我们可以肯定,这个点也在三角形内部...基本思路就是这些,下面是函数实现方法,为了方便计算,我们取p为高的中点.

 + Shingo Jass Highlighter 0.41

//(Lx1,Ly1),(Lx2,Ly2)为直线通过的两个点的坐标,因为魔兽中使用直线都是通过点来确定的 
//(Px,Py)为要检测的点的坐标,返回值表示了该点与直线的位置关系 
function GetPositionRelation takes real Lx1, real Ly1, real Lx2, real Ly2, real Px, real Py returns integer 
    //为了防止误使用Lx1==Lx2的参数来调用这个函数,对这种情况的数值做个小小的处理 
    if Lx1==Lx2 then 
        set Lx2=Lx2+1.0     //微小的偏移在魔兽中感觉不出来 
    endif 

    if (Py-Ly1-(Px-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))>0 then               //如果在直线上方,则返回1 
        return 1 
    elseif (Py-Ly1-(Px-Lx1)*(Ly2-Ly1)/(Lx2-Lx1))<0 then        //如果在直线下方,则返回1 
        return -1 
    else                                                                                  //如果在直线上,则返回0 
        return 0 
    endif 
endfunction 

//(Lx1,Ly1),(Lx2,Ly2)为直线通过的两个点的坐标,(Px1,Py1),(px2,Py2)是要判断的两个点 
//返回值为TRUE说明两个点在直线同侧,返回FALSE说明点在直线两侧(在直线上被划分到同侧的范围) 
function IsSameSide takes real Lx1, real Ly1, real Lx2, real Ly2, real Px1, real Py1, real Px2, real Py2 returns boolean 
    if Lx1==Lx2 then         //竖直方向的直线  
        if (Px1-Lx1)*(Px2-lx1)>=0 then    //直线同一侧  
            return true 
        endif 
        return false 
    endif 
    return GetPositionRelation(Lx1,Ly1,Lx2,Ly2,Px1,Py1)==GetPositionRelation(Lx1,Ly1,Lx2,Ly2,Px2,Py2) 
endfunction 

//(startX,startY)是三角形底边中点坐标,L是向两侧延伸的距离,也就是底边长度的一半,H是向前方延伸的距离,也就是底边上的高 
//(checkX,checkY)为要检测的点,函数返回TRUE说明点(checkX,checkY)在三角形内,返回FALSE说明在三角形之外 
//点在三角形上包含在之内 
function IsInTriangle takes real startX, real startY, real face, real L, real H ,real checkX, real checkY returns boolean 
    local real Mid_x     =startX+0.5*H*CosBJ(face) 
    local real Mid_y     =startY+0.5*H*SinBJ(face) 
    local real Left_x   =startX-L*SinBJ(face) 
    local real Left_y   =startY+L*CosBJ(face) 
    local real Right_x  =startX+L*SinBJ(face) 
    local real Right_y  =startY-L*CosBJ(face) 
    local real Top_x    =startX+H*CosBJ(face) 
    local real Top_y    =startY+H*SinBJ(face) 
    local boolean B12=IsSameSide(Left_x,Left_y,Right_x,Right_y,Mid_x,Mid_y,checkX,checkY) 
    local boolean B13=IsSameSide(Left_x,Left_y,Top_x,Top_y,Mid_x,Mid_y,checkX,checkY) 
    local boolean B12=IsSameSide(Right_x,Right_y,Top_x,Top_y,Mid_x,Mid_y,checkX,checkY) 
    return (B12 and b13 and B23)  
endfunction 

//简化参数,u是施法单位,L和H意义同上,testUnit为一任意单位,如果该单位在三角形内(或之上),返回TRUE,否则返回FALSE 
function IsUnitInUnitTriangle takes unit u, real L, real H, unit testUnit returns boolean 
    return  IsInTriangle(GetUnitX(u),GetUnitY(u),GetUnitFacing(u),L,H,GetUnitX(testUnit),GetUnitY(testUnit)) 
endfunction

 

 

 

 

方法还有几种,例如向量乘法,判断镜像点距离...考虑到Jass和编图者的承受能力,就不一一列出了.如果你还想到了更好更简便的方法,欢迎发上来大家一起交流.

附件的演示是对单位正前方三角形区域内