qt 判断一个点是否落在三角形内(算法) -凯发k8官方网

利用重心法判断一个点是否落在三角形面积内,三角形的三个点在同一个平面上，如果选中其中一个点，其他两个点不过是相对该点的位移而已，比如选择点a作为起点，那么点b相当于在ab方向移动一段距离得到，而点c相当于在ac方向移动一段距离得到。

所以对于平面内任意一点，都可以由如下方程来表示
p = a u * (c – a) v * (b - a) // 方程1
如果系数u或v为负值，那么相当于朝相反的方向移动，即ba或ca方向。那么如果想让p位于三角形abc内部，u和v必须满足什么条件呢？有如下三个条件
u >= 0
v >= 0
u v <= 1
几个边界情况，当u = 0且v = 0时，就是点a，当u = 0,v = 1时，就是点b，而当u = 1, v = 0时，就是点c
整理方程1得到p – a = u(c - a) v(b - a)
令v0 = c – a, v1 = b – a, v2 = p – a，则v2 = u * v0 v * v1，现在是一个方程，两个未知数，无法解出u和v，将等式两边分别点乘v0和v1的到两个等式
(v2) • v0 = (u * v0 v * v1) • v0
(v2) • v1 = (u * v0 v * v1) • v1
注意到这里u和v是数，而v0，v1和v2是向量，所以可以将点积展开得到下面的式子。
v2 • v0 = u * (v0 • v0) v * (v1 • v0) // 式1
v2 • v1 = u * (v0 • v1) v * (v1• v1) // 式2
解这个方程得到
u = ((v1•v1)(v2•v0)-(v1•v0)(v2•v1)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))
v = ((v0•v0)(v2•v1)-(v0•v1)(v2•v0)) / ((v0•v0)(v1•v1) - (v0•v1)(v1•v0))

整理成 qt 的函数形式如下:

// determine whether point p in triangle abc bool pointintriangle(qvector2d a, qvector2d b, qvector2d c, qvector2d p) {qvector2d v0 = c - a;qvector2d v1 = b - a;qvector2d v2 = p - a;float dot00 = qvector2d::dotproduct(v0, v0);float dot01 = qvector2d::dotproduct(v0, v1);float dot02 = qvector2d::dotproduct(v0, v2);float dot11 = qvector2d::dotproduct(v1, v1);float dot12 = qvector2d::dotproduct(v1, v2);float inverdeno = 1 / (dot00 * dot11 - dot01 * dot01);float u = (dot11 * dot02 - dot01 * dot12) * inverdeno ;if (u < 0 || u > 1) // if u out of range, return directly{return false;}float v = (dot00 * dot12 - dot01 * dot02) * inverdeno ;if (v < 0 || v > 1) // if v out of range, return directly{return false;}return u v <= 1; }

(以上算法来自于网络,由我整理成 qt 可用的函数)

总结

以上是凯发k8官方网为你收集整理的qt 判断一个点是否落在三角形内(算法)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。