2d凸包の面から点が見えるかどうかを確認する

Question

飛行機内の点群のDelaunay Triangulationを生成するためのBowyer-Watsonアルゴリズムを実装しようとしています。このアルゴリズムは、境界スーパートライアングルの存在を仮定しているが、点集合の凸包を維持するようないくつかの選択肢も言及されている。

したがって、インクリメンタルアルゴリズムで凸包を仮定して点の冗長三角形分割を作成する場合、点が凸包の外側にある場合、その点から凸包のすべての頂点に頂点を描画する必要がありますそれらは、その点が見える船体の面を構成する。

私はこの問題にどのように近づくことができますか？私は最初にすべての点の凸包を生成するか、点が一度に1つずつ追加されるインクリメンタルアプローチのように、DCELの形で凸包を維持する必要がありますか？

EDIT：上の画像で、平面上の点の集合の凸包の外側に点Pがある場合、その点が見える船体の辺を計算する必要があります。 [船体の緑色の端]

質問を明確にするのに役立つことを望みます。予め

おかげ

Answer 1

はPを参照エッジは、船体が反時計回りに（署名された面積を計算する）横断したときPと時計回りの三角形を形成するものです。