多边形占用格子算法
最近，需要做这个功能，然后找到一个非常好的论文[1]，把代码实现了一下，基本算是解决问题了。论文自己搜一下吧，我也放了一份在[CSDN下载]里面。
基本原理
-
1.先找出多边形的边界，同时设置这些已经找出来的格子的状态，ODD和EVEN这两个就够了，后面用来填充中间的格子，以及如果多边形中间有镂空也是考这个状态的。
-
2.然后按列扫描格子，把两个格子中间的填充，根据状态可以算出来是否镂空。
-
3.最终每一列就得到一个范围表，如果没有镂空那么那一列就是从最上到最小一个范围。如果有镂空，那么从上到下就会有一个或者多个范围。
-
4.把这些范围所在的格子加起来就是最终这个多边形占用的格子了。
-
镂空的也是效果如下
线段相交
参考[1]中提到的求一条线段相对格子相交有四个状态：左，上，右，下。但是文中提及的参考书籍，我是没看到啥头绪，就在网上从新找到一个线段求交的算法[2]。
代码实现
用lua实现了一份代码，因为项目是用lua，而且没有用到复杂的计算，所以就lua做了。线段求交是放在C++的，感觉方便一点。参考[3]
参考
[1]A SIMPLE ALGORITHM FOR FINDING FAST, EXACTLY TILES INTERSECT WITH POLYGONS.Nam V. Nguyen1, Nam M. Nguyen1, Bac H. Le2
[2]How to check if two line segments intersect
[3]tile intersect
版权声明：本文为匿名原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。