算法1"/>
平面封闭图的耳切算法1
耳切算法:
耳切算法用于将简单多边形切成三角形片,该算法的结果并不唯一,但结果都是三角形片源就型。
首先了解下,什么是简单多边形呢:
顺序排列的点,每个点被相邻两条边共享(即点不能出现在线的中间位置),所有线的交点都是顶点,下图①就是简单多边形,②③不简单:
所以下面的任务就是对上面图形①的操作了,这就是典型的没有内孔的简单多边形(有内孔的怎么处理下面有讲)。
简单多边形包括了凸边型,也包括凹边型。
进一步了解两个概念:①简单多边形的耳朵是指:由连续顶点Vn-1-Vn-Vn+1组成的内部不包含其他任意顶点的三角形(向量Vn~Vn+1需要相对于Vn-1~Vn是左拐,即逆时针拐,和多边形取点方向相同。),②其中Vn就是耳点。
例如上面图①中 :三角形V9-V0-V1就不是耳朵(因为内部有点V8),V0-V1-V2也不是,V2-V3-V4是的,V3-V4-V5、V5-V6-V7、V8-V9-V0也是,于是点3、4、6、9就是耳点。为什么V1-V2-V3不是呢?因为V2~V3相对于V1~V2是右拐。
耳切法主要流程,第一步就是关注一个耳朵,如这里的V2-V3-V4,去除3,于是:
接着判断,可知V1-V2-V4不是耳朵,V2-V4-V5是的,准备操作耳朵V2-V4-V5,去掉耳点V4:
接着判断,V1-V2-V5不是(这里隐藏了一个,如果125为直线怎么办?),V2-V5-V6是的,切耳点V5:
以此类推。。。其中多次计算的算法是:点是否在三角形中,和下一个点在当前线段的左侧还是右侧,而点是否在三角形中也可以通过三次点在边的左侧还是右侧来判断。具体见算法实现。
接着:如果遇到内孔的情况呢,那么在原来的路径上,靠近内孔的地方“创造一个去往内孔的路径”并顺时针走完内孔的点,然后从“创造的那个路径”返回原来的路径即可,注意:“被创造路径”的两端的点需要被两次记点。
该图路径2~3(7~8)就是被人为创造出来去往内孔的边,3&7、2&8其实是同一个点。所以上图有孔的多边形的点路径即为:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
注意一个问题,由于内孔人为增加路径,而出现的同一个点被两次记点,这会导致在计算是否有点在三角形内部时,总能找到点,比如上图,在关注判断V2-V3-V6三角形时,点V8和点V7始终就在三角形上,但其实这两个点是人为增加的,这里要注意一下剔除。
实际已完成了代码测试,下图这种情况能够准确切耳:左图一个内孔,右图两个内孔。
这是后面一张图的分割结果::
代码还有很多优化空间,先不搞,留着冗余量。。。
更多推荐
平面封闭图的耳切算法1
发布评论