如何将单调多边形分解为两个单调链

Question

我正在尝试对单调多哥进行三角化。该算法需要像2个单调链一样来表示多边形。没有说明，如何去做。有没有简单的算法，可以将单调多边形分解成2个y单调链？

Answer 1

如果您的多边形是单调的相对于Y轴任何水平线最多与多边形相交两次），那么只需得到两个带有最大和最小Y值的顶点。连接这些极值顶点的左和右多义线是Y-单调链。