对单调多边形实施三角剖分
发布时间
阅读量：
阅读量
单调多边形的三角剖分
问题描述
单调多边形即为存在一个特定方向，在此方向上所有垂直于该方向的所有扫描线与该多边形仅相交于两点。
这里主要探讨的是那些沿着某一垂直方向呈现单调特性的多边形如何进行三角剖分。
为方便描述，这里没有水平的边。
规律1: 同侧端点不可能出现跨越
将多边形从最高顶分割至最低顶进行切分，并将其分为左右两条链。其中每条链两端的顶点都是按照y坐标顺序排列好的。
这表明位于下方的顶点不会高于上方的位置；如果这样的话就会导致与y轴方向上的单调性产生矛盾。
当D位于C上方时，在C位置绘制水平线就会再次与此链相交。
规律2:异侧相邻
如果两个端点在竖直方向上相邻且位于左右两条链的不同侧，则这两点之间的连线不会与其他边相交。
还没有任何评论哟~