二维多边形线性扫掠：滑动覆盖区域的点归属检测算法问询
嘿，这个问题很实用啊！先明确下需求：你有一个无自交的简单2D多边形，它沿着向量V=(A,B)对应的线段滑动（也就是做线性扫掠），现在想判断任意平面点P=(x,y)是否落在这个扫掠出来的区域里，对吧？
下面给你梳理几个可行的实现思路，都是工程里验证过的：
方法一：构造扫掠区域多边形，用经典点-in-多边形算法
扫掠出来的区域本质是一个多边形带：把原多边形记为Poly，滑动后的多边形记为Poly'（每个顶点都加上向量V），扫掠区域就是这两个多边形之间所有点的集合。这个区域的边界可以直接构造：
- 取原多边形的顶点列表
v₁, v₂, ..., vₙ，滑动后的顶点列表v₁', v₂', ..., vₙ' - 按顺序拼接成新的闭合多边形：
v₁, v₂, ..., vₙ, vₙ', vₙ₋₁', ..., v₁'，这样就能把两个多边形的对应顶点用线段连接，形成完整的扫掠区域边界
构造好这个新多边形后，直接用成熟的**射线法或者winding number算法**判断点P是否在内部即可。
注意：如果原多边形的边与滑动方向的边存在重叠，可能导致新多边形出现自交，这时候需要先把自交多边形拆分为多个简单多边形，再分别判断点是否在其中任意一个内部。
方法二：无构造直接判断，效率更高
这个思路不用生成整个扫掠区域，适合实时检测或多边形顶点较多的场景：
扫掠区域的定义可以转化为：存在原多边形内的点Q，使得P在Q到Q+V的线段上，也就是P = Q + t*V，其中Q ∈ Poly，t ∈ [0,1]。
我们可以把问题转化为：是否存在t ∈ [0,1]，使得P - t*V落在原多边形内部？具体步骤如下：
- 对原多边形的每条边，把点
P - t*V = (x - t*A, y - t*B)代入边对应的线性不等式（比如某条边的不等式为a*x + b*y + c ≤ 0，根据多边形朝向确定不等号方向） - 整理不等式得到关于
t的约束（比如t ≥ k或t ≤ k，分母正负会影响不等号方向） - 把所有约束合并，得到
t的可行区间，看这个区间是否与[0,1]有交集
如果有交集，说明存在符合条件的t，点P就在扫掠区域内；反之则不在。
方法三：基于Minkowski和的理论思路
从集合论角度，扫掠区域其实是原多边形与线段[0, V]的Minkowski和（即所有Q + t*V的集合，Q∈Poly，t∈[0,1]）。判断点P是否在这个和里，等价于判断P与线段[0, -V]的Minkowski和是否与原多边形相交——这个思路和方法二本质是一致的，只是从数学理论层面描述。
特殊情况处理
如果向量V是零向量（A=0且B=0），扫掠区域就是原多边形本身，直接用点-in-多边形算法判断即可。
备注：内容来源于stack exchange，提问作者aSpagno
