如何判断任意点p在三角形内部?

taojackson

已知一个三角形的三个顶点a, b, c,  以及任意一点p, 编写一个函数判断点p是否在三角形内部,要求算法最优, 请大家多多指教, 谢谢!

cO_olWinD

设 p1p2 表示从点p2到点p1的向量。 例如： pa表示从三角形顶点a到点p的向量， ba表示从三角形顶点a到定点b的向量。
设 cross(p1p2， p3p4)表示向量p1p2和向量p3p4的叉乘。
设 normalize(vector)表示向量单位化.

则：
(1) pa ＝ p - a; pb = p - b; pc = p - c; ba = b - a; cb = c - b; ac = a - c;
(2) V1 = normalize(cross(ba, pa));  V2 = normalize(cross(cb, pb)); V3 = normalize(cross(ac, pc));
如果 normalize(V1) = normalize(V2) = normalize(V3), 则点p在三角形abc的内部， 否则点p在三角形之外。

优化: 其中cross求差乘中只是些浮点数乘法和加法, 对效率影响不大, 如果还不满意, 可以使用SSE指令集加速。

normalize中需要求平方根, 是开销最大的地方, 优化方法是改为比较两个向量是否成比例。 如:
如果 V1.x / V2.x = V1.y / V2.y = V1.z / V2.z 则 V1 = V2.

yjangel

平方根开销比较大..直接用泰勒展开式求平方根..这样的开销小很多..
这类问题归结到计算几何这一学科...买本计算几何书看看..就OK..

Enigmaya

cO_olWinD: Re:如何判断任意点p在三角形内部?

设 p1p2 表示从点p2到点p1的向量。 例如： pa表示从三角形顶点a到点p的向量， ba表示从三角形顶点a到定点b的...

前面叉乘，但是后面不用比较是否相等，所以不用normalize，只需要点积，只要任意两个符号相反，就可判定点在三角形外部。否则点就在内部或边上。

算法最优的话，好像有一个行列式的方法。不过记不大清了。

monkeykane

下面的代码是我以前写碰撞检测模块时看到的，觉得效率不错，不过前提条件是：点必须要在三角形所在屏幕上面
typedef unsigned int uint32;
#define in(a) ((uint32&) a)
bool checkPointInTriangle(const VECTOR& point,
const VECTOR& pa,const VECTOR& pb, const VECTOR& pc)
{
VECTOR e10=pb-pa;
VECTOR e20=pc-pa;
float a = e10.dot(e10);
float b = e10.dot(e20);
float c = e20.dot(e20);
float ac_bb=(a*c)-(b*b);
VECTOR vp(point.x-pa.x, point.y-pa.y, point.z-pa.z);
float d = vp.dot(e10);
float e = vp.dot(e20);
float x = (d*c)-(e*b);
float y = (e*a)-(d*b);
float z = x+y-ac_bb;
return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000);
}

辐射

满足
ab连接线90度线的前方
bc连接线90度线的前方
cd连接线90度线的前方

就是三角内了

a--------b
|           |
|           |
|           |
    p在这里，并三个连接点都满足就是三角内


下班前临时想的算法

辐射

要怎么算在两个点形成的直线的左边还是右边呢.........=_=

p1

a-b

p2




怎么区分 p1 跟p2 ....的方向问题.   [em7]

辐射

好像这样也可以

a
      p
b   c


a跟p相连，与bc焦点在b跟c以内
b跟p相连，与ac焦点在a跟c以内
c跟p相连，与ab焦点在a跟b以内

想不起来怎么算两坐标以内的证明方法了 [em10]