再论向量在游戏中的应用(2) Point In Polygon (PIP)

问题概述

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

角度二 课堂教学

详情参见Y2B视频 平面向量-直線的參數式說明

角度三 看图说话

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
2
3
4
if (p.x < v1.x + (p.y - v1.y) / (v2.y - v1.y) * (v2.x - v1.x))
{
crossNumber += 1;
}

文章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问题中 向量其实没有起到什么作用,但是对于一般线段相交的求解公式,使用向量去做 要比 方程式求解方法 简单许多

坚持原创技术分享,您的支持将鼓励我继续创作!