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

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,之所以不考虑相等的情况,是因为用不上,而且考虑的话,情况会变得非常复杂):

?

?

?

?

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

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