5

多边形占用格子算法

 收集于6天前 阅读数 5
以下为 快照 页面,建议前往来源网站查看,会有更好的阅读体验。
原文链接: http://pkxpp.github.io/2020/10/17/多边形占用格子算法/

[TOC]

最近,需要做这个功能,然后找到一个非常好的论文[1],把代码实现了一下,基本算是解决问题了。论文自己搜一下吧,我也放了一份在[CSDN下载]里面。

基本原理

  • 1.先找出多边形的边界,同时设置这些已经找出来的格子的状态,ODD和EVEN这两个就够了,后面用来填充中间的格子,以及如果多边形中间有镂空也是考这个状态的。

rUfaEfy.jpg!mobile

  • 2.然后按列扫描格子,把两个格子中间的填充,根据状态可以算出来是否镂空。
  • 3.最终每一列就得到一个范围表,如果没有镂空那么那一列就是从最上到最小一个范围。如果有镂空,那么从上到下就会有一个或者多个范围。
  • 4.把这些范围所在的格子加起来就是最终这个多边形占用的格子了。

UjUBnim.jpg!mobile

  • 镂空的也是效果如下

3m6N7f.jpg!mobile

线段相交

参考[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


猜你喜欢

关于极客头条


聚合每日国内外有价值,有趣的链接。

AD