平面内の一連の点の Delaunay Triangulation を生成するための Bowyer-Watson アルゴリズムを実装しようとしています。このアルゴリズムは、境界のある超三角形の存在を前提としていますが、点の集合の凸包を維持するなどの代替手段もいくつか言及されています。
したがって、インクリメンタル アルゴリズムで凸包を仮定して点のドロネー三角形分割を生成することを決定した場合、点が凸包の外側にある場合、その点から面を構成する凸包上のすべての頂点に頂点を描画する必要があります。ポイントが見える船体の。
どうすればこの問題にアプローチできるのだろうかと思っていました。ポイントが一度に 1 つずつ追加されるインクリメンタル アプローチですべてのポイントなどの凸包を最初に生成する必要がありますか? DCEL の形式で凸包を維持する必要がありますか?
編集: 上の画像では、平面内の一連の点の凸包の外側にある点 P がある場合、点が見える包のエッジを計算する必要があります。【船体の緑の縁】
画像が質問を明確にするのに役立つことを願っています。
前もって感謝します