判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢?
假如有四个点A(x0,y0),B(x1,y1),C(x2,y2),D(x,y),要你来判断D点是否包含在三角形ABC里面,也许你会想到用
在判断是否构成三角形 之后在用公式计算面积
但给三根线算长度太复杂了 有没有比较好点的算法 比如SIN 或者 点到直线距离.....
也就是 海伦公式 ,这也许不会很难想到毕竟在高中都学过的....
海伦公式:
L = (a+b+c)/2 (L为三角形的半周长)
S = sqrt(L*(L-a)*(L-b)*(L-c)) (S为其面积)
正弦公式
S = (1/2)*a*b*sinα (α是a,b两线夹角)
但是正如所说的那样,计算每一条边是比较麻烦的,而且还容易出现精度问题。而在计算中我们应该避免这一点。
那有没有其他的方法可循呢?
答案很定是有的.....
用行列式(涉及到大学线代里的知识)。
对于 A,B,C
我们有 |x0 y0 1|
2*s = |x1 y1 1|=x0*y1+y0*x2+x1*y2-(x2*y1+x1*y0+y2*x0)
|x2 y2 1|
这样我们就可以求出任意的三角形的有向面积啦!!
如果有一点D,包含于abc里面,那么很定满足下面的条件
然后三角形 Sabc =Sdab+Sdbc+Sdca;
这样所要求的判断就可以得出啦!!
另外附上一则比较重要的知识:
来自百度的....说得非常详细,就不在多说啦!!
http://hi.baidu.com/wayright/item/ad18e4c0c5446b2dee4665c9
如何判断一个点是否在一个多边形内部
- 在多边性的存储中,每一个多边形都是由一系列连续的点组成,例如保存为数组Polygon[5],表示这个多边形是由5个点组成,这5个点顺序地存储在了数组Polygon之中。就如同走路一般地划线,从数组的第一个点连到第五个点,多边行就构造出来了。
- 在图形编程中,坐标的利用是不可忽视的。在这里判断一个点是否在多边行内部(可以包括线上)就要利用到各个点的坐标关系。下面开始讨论具体的方法。
- 对任何事物的分析,我们应该遵守由简入繁的原则,这样才能提高条理性,少犯错误。我们先判断一个点是否在一个三角形内部。一个三角形在一个坐标系(譬如由A、B、C三点组成)中,我们可以通过计算它的有向面积来判断A、B、C三点在坐标系中的顺逆。当然,在此之前我们必须先订立一套计算面积的规则。比如,在笛卡尔坐标系中,我们利用:
- S=((A.x-B.x)*(A.y+B.y)+(B.x-C.x)*(B.y+C.y)+(C.x-A.x)*(C.y+B.y))/2 ---------------------------------- <1>来计算三角形的有向面积。规则即是:从第一点开始,用前一点横坐标减后一点横坐标与两坐标之和的乘积求梯形面积,直到完成多边性的封闭,得到三角形的有向面积。此时,如果求出的值是正的(S>0),则得出A->B->C为逆时针,否则为顺时针。到这里,我们知道如何判断一个三角形的顺逆的方法。
- 对于凸多边形而言(以三角形ABC为例),假设存在一个点D,若这个点在三角形的内部,则以该点为起点,和原多边形的任意两个连续的且尊照多边形组成方向的点(如DAB、DBC、DCA)组成的三角形讲都是一个方向,如DAB和DBC都是顺时针方向。若这个点在三角形的外部,则会出现DAB、DBC、DCA三个三角形方向不一致的情形,即其中有一个不同于另外两个(如一个顺,两个逆)。到这里我们就知道了如何判断一个点在一个三角形内部的算法,总结一下就是通过判断该点同三角形连续两点组成三角形的顺逆性(归于面积的正负)来得到结果的。
- 实际上,对于其他的凸多边性也可以用一样的方法,只是这个时候判断的三角形的数目增加了,不管怎么样,只要点在多边形内部他们的顺逆都是一样的。对于凹多边形而言,情况就要相对复杂一些了。此时,判断一个点是否在其内部的计算量会增加比较多。具体算法如下:此时三角形一个个的判断可能会失效,我们应当两个同时判断。即判断该点是否同时在多边形的连续两个三角形之中,相当于是求两个三角形的交集,直到完成多边形封闭。例如,判断P点是否在多边形ABCD之中,依次判断P是否在ABC-BCD、BCD-CDA、CDA-DAB、DAB-ABC各个成对三角形中,P在ABC-BCD中表示P在ABC-BCD的交集之中。这样就可以判断一个点是否在一个凹多边形内部了。
- 以上说的仅仅是简单多边形而已,在复杂多变形之中(如内洞、飞地等),还要通过多边形的拓扑运算来得到结果。另外,在凸边形中,还可以进行优化:可以以一个点为中心,分裂多边形为最少个数的三角形,从而得到改进。
暂且归纳这多,留着以后继续补充......