网络寻租

Programmer, Gamer, Hacker

求视线范围的算法

| Comments

前段时间看到有一个游戏,玩家必须保持自己在监控设备的视线范围内。 画面上面展示的效果是高亮出监视器的视线范围。如图:

我思考了一下如何做到这点。首先定义问题: 给出墙壁的边,以及若干监控点,需要实时渲染出监控点的可视范围 (可以用一系列的三角形表示)。

求视线范围的三角形列表,可以从房间所有墙壁的顶点往监控点做视线线段, 找视线线段和墙壁边的连接中距离监控点最近的点, 然后可视范围就是这些点和监控点组成的三角形了。

填充三角形,可以用扫描线算法。把三角形根据水平线拆分成2个, 然后从顶点往下做扫描线,求扫描线和两条边的交点,然后填充里面的区域。 如下图所示:

求线段相交点的算法网上搜索一下就可以得到。

估计一下算法复杂度,墙壁边是m(4<m<240),求交点是m*m,应该是上界。 常数应该比较大,包括求交点,找出距离监控点最近的点。 可以优化一下参数,比如变形求交点算法(做垂线),快速找到距离监控点最近的点。

大家想想看有什么更好的解法?

Comments