lua三角形绘制方法

分类:CentOS运维 阅读:59058 次

最近遇到了需要在游戏中绘制多边形trap区域的问题,经过转化,这个问题可以分解成更小的如何绘制三角形的问题,因为策划只会提供3个坐标点,然后程序必须通过这三个点来获取所围成的三角形区域内的所有点的坐标,这个问题进一步归结为如何判断点是否在三角形中,经过了1天的思考,搜索了一些资料并回忆了以前的图形学内容,一般来说判断点是否在三角形,当然也包括一切多边形,有两种判断方法:一种是通过点做x轴方向或者y轴方向的射线,如果射线与多边形的交点的个数为偶数个则在多边形外,否则多边形内,当然排除一些边上点和顶点的特殊情况;另一种是通过计算多边形的有向面积,然后通过点和多边形任意边构成的所有三角形的有向面积方向是否一致来确定点是否在三角形中。

但是具体到我们的游戏中,这两种方法计算量都比较大,所以我想到了一种自动生成那些属于三角形内的点的方式,简单来讲就是从三角形的大角出发,朝向三角形内进行发散,这样处理计算量小,而且容易理解,这里贴出lua代码,代码比较冗长,因为写的时间不长,可能存在一定的bug以及需要优化的地方,比如斜率的特殊情况等等,之后会继续修改,有喜欢的朋友自取。经过测试,但没有覆盖全部的测试用例,估计会有些bug,但大致方向应该是正确的,生成一个拥有500 0000个点的三角形trap区域只需要1.8秒左右,当然我后面会继续优化。