问题概述
PIP 问题 应用很广,也是很基础的图形学问题. 一句话描述就是如何判断一个点p 是否在给定的一个 任意多边形(Polygon)之内.
解法概述
我知道的主流方法有两种, 一种就是射线法,一种是风向法.
风向法没有研究,看着比较复杂. 主要看了一下 射线法.
射线法 就是 以p点 随意向一个方向发射一条射线(因为计算简便,所以目前大家都是向右侧发射一条射线,但其实可以向任意方向发射的)
判断这条射线最终和多边形的交点数量,如果是偶数则这个点在 多边形外,如果为奇数则在多边形内
From Wiki
This algorithm is sometimes also known as the crossing number algorithm or the even–odd rule algorithm, and is known as early as 1962.[3] The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two “border crossings” the moving point goes outside. This observation may be mathematically proved using the Jordan curve theorem.
问题拆解
首先把这个问题拆分出来.
- 将多边形拆解为若干条边
- 通过某种算法可以判断 通过P点的射线和每条边是否相交,相交则计数+1
- 统计最终计数奇偶性,从而判断出P点是否在多边形内
所以其实这个问题的核心就是
如何判断 过P点 向右侧的射线是否和某一个线段相交
在解决这个问题上 我绕了一个大弯子. 不过这个弯子我觉得绕的挺值的. 涨了不少知识.
判断两个线段是否相交
我把这个射线问题错误的简化为了线段问题. 所以我首先研究的是
如何判断 线段AB 和 线段CD 是否相交
把这个问题说的已经非常明白了. 但是有三个预备知识 需要先了解下才可以.
前两个是 叉积的反交换律 和 零向量
这个前面已经说过了.
另外一个就是
直线的参数式(点向式) 表达法
这个初期理解起来比较难. 可以通过多角度去理解这个问题.
角度一 PDF教材
直接摘抄自一份PDF
角度二 课堂教学
角度三 看图说话
O 点是 二维坐标系的 (0,0)点 , 向量 OM 就是对应的 视频中的 b 向量, OA 对应的是 a向量, AB 也就是对应的 方向向量r
所以对于 线段AB上的一点M
M点 也就是 OM向量,因为 O点是原点 所以M点的坐标 比如(3,5) 你可以把他理解为一个点 也可以理解为一个向量
可以用向量方式表达就是 如图了.
公式推导
流程同视频. 方块t 和 方块v 表示标量t,v. 小写的a,b,c,d均为向量. 其中 点为点乘 x 为 叉乘.
注意公式的限制是在2D平面内, 因为一个向量叉乘一个向量仍旧是一个向量, 而一个向量 除以 一个向量 无数学意义.
这里我也不是很理解, 不过在2D平面时候 r x s 才可以展开为 r.x s.y - r.y s.x
2D中叉乘公式:
V1(x1, y1) V2(x2, y2)
V1 x V2 = x1y2 – y1x2
判断射线和线段相交问题
研究明白了 线段相交问题,本以为P点射线问题 应该迎刃而解才对. 后来 Google了几篇PIP求解文章.给出的公式核心部分均是
1 | if (p.x < v1.x + (p.y - v1.y) / (v2.y - v1.y) * (v2.x - v1.x)) |
文章1 : 里面有几种Fast 优化方式,不过核心判断都是上面这个代码.
我把这个公式和我推导出的公式做比较,发现有些莫名其妙.辗转反侧的研究了大半天. 后来发现其实是我之前把问题想复杂了.绕了一个大弯儿.
直线方程法 求解
对于过P点的射线 是否和 线段AB相交. 直接用两点式 直线方程求解 交点即可. 最后判断 给定的P点 x 坐标是否比交点坐标的x要小
比如对于 射线s 和 线段l
- 已知 A点(Ax,Ay) B点(Bx,By) 是线段l上的两个端点
- P点(Px,Py)是需要判断的点
- M点(Mx,My)是射线s 和 线段l 的交点
- P’ 和 P’’ 是 交点左右两侧的两个点
向量法 求解
虽然疑惑解开了,但是向量不能白研究啊. 以上这个射线问题 我觉得应该也可以用向量法求解(我自己没有试)
就是 只要取出Math.Max(Ax,Bx),然后直接确定一点N使得 N = Math.Max(Ax,Bx)+1 , 然后直接判断 线段PN 和 线段AB 是否相交即可.
小结
虽然 PIP问题中 向量其实没有起到什么作用,但是对于一般线段相交的求解公式,使用向量去做 要比 方程式求解方法 简单许多
