如何將單調多邊形分解爲兩個單調鏈

Question

我正在嘗試對單調多哥進行三角化。該算法需要像2個單調鏈一樣來表示多邊形。沒有說明，如何去做。有沒有簡單的算法，可以將單調多邊形分解成2個y單調鏈？

Answer 1

如果您的多邊形是單調的相對於Y軸任何水平線最多與多邊形相交兩次），那麼只需得到兩個帶有最大和最小Y值的頂點。連接這些極值頂點的左和右多義線是Y-單調鏈。