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

时间:2021-04-08 10:25:22

之前有了解过这方面的东西,在图形编辑器中也用到了这个判断,当时总结出来的结果是要4次向量叉乘。同时在网上粗略的搜了一下,貌似也没找到有更好的方法了(也许是自己没找到,^-^).下面先说一下用4次向量叉乘的方法:

设三角形三点A(x1,y1)B(x2,y2)C(x3,y3),已知点M(x,y),

1,先求出三个向量MA,MB,MC. 

2,计算MA*MB,MA*MC; MB*MC,MB*MA;

3,如果此两组的向量叉乘的结果都是异号的,即方向相反的,则说明是在三角形内部,否则在三角形外部!

当然还可以计算三角形面积的方法,其实面积就是向量叉乘的意思,本质上是一样的。最后说一下只用3次叉乘就ok的方法(昨天找下学期做毕业设计的老师,她让我做计算几何算法用并行计算实现方面的东东,因此突然间回忆了一下以前看的比较郁闷的计算几何方面的东东,嘿嘿),

只需依次计算MA*MB,MB*MC,MC*MA,如果此3结果都是同号(或都正,或都负),则说明点M在三角形每条边的同侧,即内部。否则必在外部!