5

ほとんどの反復アルゴリズムでは、ボールを転がすために最初に空の三角形が必要です。一般的に使用されるトリックは、点集合と比較して超三角形を非常に大きくすることです。

しかし、「数値レシピ：科学計算の芸術」によると：

「...距離が（境界点まで）単に有限である場合、構築された三角形分割はドローネーではない可能性があります。たとえば、その外側の境界は、異常なケースでは、直径のオーダーで小さな負の角度でわずかに凹状のままになる可能性があります「実際の」ポイント セットを「架空の」(境界) ポイントまでの距離で割った値。

では、すべての入力を同次座標などの別の座標系に変換することなく、デカルト座標を無限大の点で拡張するには、どのようなオプションがあるのでしょうか? これらの点は、通常の幾何学的述語 CCW および Incircle にどのように適合しますか?

Incircle (a,b,c) Infinity -> False. ただし、a、b、c は有限です。

しかし、a、b、c のいずれかが無限遠点である場合はどうなるでしょうか。円は半平面になり、テストは CCW チェックになりますか? 外接円上の 2 つ以上の点が無限である場合はどうなりますか? 円は完全な平面に展開し、テストが常に true になるようにしますか? CCWはどうですか？無限遠に 1 つ以上の点を持つ直線に関連する点をどのように分類しますか?

4

2 に答える 2

1

無限に点を追加することでドローネ三角形分割を実装するのは非常に簡単です。無限頂点の規則を選択しました (頂点インデックス -1 など)。

最初に、入力ポイントセットから取得した 4 つの非同一平面上の点の間に最初の有限四面体 T0 を作成し、次に T0 の各面を無限頂点 0 に接続する 4 つの無限四面体を作成します (それらを適切に相互接続することを忘れないでください)。それらの共通の無限の面)。

次に、通常どおり (Boyer-Watson アルゴリズム)、(1) 点 p を含む四面体 T を計算し (場所を特定)、(2) 次のように競合ゾーンを見つけることにより、各点 p を 1 つずつ挿入します。

(1) locate は変更されません: ランダムな有限四面体から p に移動します。ウォーキング中に無限四面体に到達すると、そこで停止します (これは、ポイントが以前に挿入されたポイントの凸包の外側にあることを意味します)。

(2) 紛争地帯の決定には、小さな変更が必要です :

  • 点 p は、その外接球内にある場合 (通常どおり) 、有限四面体 Tと衝突します。

  • 無限四面体 T = (p1, p2, p3, p4) の場合、p1、p2、p3、p4 のいずれかが無限頂点になります (たとえば、p2 の場合、T = (p1、無限、p3、p4))。p が T と競合しているかどうかを確認するには、無限頂点を p で置き換え、四面体の符号付き体積を計算します。 pで。負の場合、T は p と競合していません。p がT の 3 つの有限頂点の支持平面上に正確にある場合、T' が p と競合する場合、T は p と競合します。ここで、T' は T の有限面に沿って T に隣接する四面体です (同等に、 T' をクエリする代わりに、p が T の有限ファセットの外接円内にあるかどうかを確認できます)。

次の実装を参照してください。

于 2015-07-14T11:55:10.410 に答える
0

無限の距離にある点を含む幾何学の完全な数学を定義しようとすることで、あなたは人生を困難にしていると思います. これは、ドロネー三角形分割を正確に計算するという元の問題の目的には必要ありません。

私は少し前に Java で Delaunay ジェネレーターを書きました 。

http://open.trickl.com/trickl-graph/apidocs/index.htmlを参照してください。特に:

    // Check if fourth point is within the circumcircle defined by the first three
   private boolean isWithinCircumcircle(PlanarGraph<V, E> graph, V first,
           V second,
           V third,
           V fourth) {
      // Treat the boundary as if infinitely far away
      Coordinate p = vertexToCoordinate.get(fourth);
      if (PlanarGraphs.isVertexBoundary(graph, first)) {
         return isLeftOf(third, second, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, second)) {
         return isLeftOf(first, third, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, third)) {
         return isLeftOf(second, first, p);
      } else if (PlanarGraphs.isVertexBoundary(graph, fourth)) {
         return false;
      }

      Coordinate a = vertexToCoordinate.get(first);
      Coordinate b = vertexToCoordinate.get(second);
      Coordinate c = vertexToCoordinate.get(third);

      boolean within = (a.x * a.x + a.y * a.y) * getDblOrientedTriangleArea(b, c, p)
              - (b.x * b.x + b.y * b.y) * getDblOrientedTriangleArea(a, c, p)
              + (c.x * c.x + c.y * c.y) * getDblOrientedTriangleArea(a, b, p)
              - (p.x * p.x + p.y * p.y) * getDblOrientedTriangleArea(a, b, c) > 0;

      return within;
   }

ここでは、外接円条件をチェックするときに境界点が明示的にチェックされるため、効果的に「無限に」離れているものとして扱うことができます。これは、説明するよりもすべての幾何学的意味を理解するよりもはるかに簡単です。

于 2011-12-15T17:13:20.690 に答える