三角剖分x單調多邊形

Question

我很難弄清楚如何三角剖分x單調多邊形。我參考this article。我不明白如何檢查頂點是否是耳朵，以及是否有對角線。

Answer 1

您可以參考ear cutting這是一個n^2時間算法。有很多簡單的算法來對一個簡單的多邊形進行三角剖分。最簡單的n log n時間算法之一包括首先將簡單多邊形分解爲單調片段，然後對這些片段進行三角測量。這種情況下的分裂需要n log n。就你而言，因爲你已經有單調片段，所以你可以在線性時間內很容易地對x單調多邊形進行三角測量。

對這個簡單算法的一個很好的解釋例如在書Computational Geometry中給出。

粗略的想法是：你知道你的多邊形是x-單調的。因此，你將它分成兩個單調鏈（上和下）。現在，您可以沿着兩條鏈走，並在兩條鏈之間插入對角線，而無需查看可見性。只要下一個較低鏈的頂點具有較小的x值，就沿着上層鏈走。如果您的頂點是反射，則將其放在堆棧上，否則將對角線插入另一邊。當您在另一條鏈上進行下一步時，首先將對角線插入堆棧中的每個頂點，然後繼續執行此例程。

Answer 2

請參閱第13/25頁「三角測量：理論」。該圖說明了一個測試，看看p是否是耳朵上的頂點。它的鄰居是q和r。如果線段qr是對角線，則p在耳朵上。

通過測試是否有其他頂點位於其上或其他任何邊緣線段是否跨越線段，測試線段以查看其是否爲對角線。