x-monotoneポリゴンを三角形分割する

Question

x-monotoneポリゴンを三角形分割する方法がわかりません。私はthis articleを参照しています。私は、頂点が耳であるかどうか、そして対角があるかどうかをチェックする方法を理解していません。

Answer 1

n^2時間アルゴリズムであるear cuttingを参照してください。単純なポリゴンを三角形分割する多くの単純なアルゴリズムがあります。最も単純なn log n時間アルゴリズムの1つは、最初に単純なポリゴンを単調なピースに分割し、次にこれらのピースを三角形分割することから成ります。この場合の分割はn log nを要する。あなたのケースでは、モノトーンを既に持っているので、線形時間でx-monotoneポリゴンを簡単に三角形分割できます。

この簡単なアルゴリズムの良い説明は、たとえばComputational Geometryという本にあります。

おおよそのアイデアは、ポリゴンがxモノトーンであることを知っています。したがって、2つの単調なチェーン（上下）に分割します。今度は、両方のチェーンに沿って歩いて、視認性チェックなしに2つのチェーンの間に対角線を挿入できます。次のより低いチェーン頂点がより小さいx値のものである限り、あなたは上のチェーンに沿って進む。あなたの頂点が反射している場合、それをスタックに置きます。そうでなければ、反対側に対角線を挿入します。他のチェーンの次のステップを実行するときは、最初にスタックのすべての頂点に対角線を挿入し、このルーチンを実行します。

Answer 2

13/25ページの「三角測量：理論」を参照してください。この図は、pが耳の頂点であるかどうかを調べるテストを示しています。その隣人はqとrです。線分qrが対角であれば、pは耳にある。

他の頂点があるかどうかをテストしたり、他の稜線セグメントが交差しているかどうかをテストして、斜め線かどうかをテストします。