32
多边形占用格子算法
source link: http://pkxpp.github.io/2020/10/17/多边形占用格子算法/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[TOC]
最近，需要做这个功能，然后找到一个非常好的论文[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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK