3

nランダムな点(黒い点)をプロットし、ドロネー三角形分割を使用しました。次に、mランダムな評価点(赤い点)を補間したいので、評価点がどの三角形の内側にあるかを計算する必要があります。

各ポイントの三角形の頂点を計算するためのアプローチは何ですか? ここに画像の説明を入力

4

4 に答える 4

3

与えられた三角形 ABC について、点 C が線分 AB の点 C と同じ側にあり、線分 BC の点 A と同じ側にあり、線分 AC の点と同じ側にある場合、点は三角形の内側にあるBです。各三角形に対してこのチェックを事前に最適化し、それが含まれる三角形が見つかるまですべてをチェックできます。詳細については、このページを参照してください。

計算を節約するために、各三角形の点の X 座標と Y 座標の最小値と最大値を計算できます。ポイントの X 座標と Y 座標が最小値と最大値の範囲内にない場合は、その三角形のチェックをすぐにスキップできます。三角形を囲む長方形の内側にない場合、点はその内側にあることはできません。

于 2013-04-12T10:31:40.953 に答える
1

この単純な例では、10 個のランダム ポイントを三角形分割し、さらに 3 個のランダム ポイントが生成され、それらが三角形の内側にある場合、頂点が与えられます。

import numpy as np
from pyhull.delaunay import DelaunayTri

def sign(a,b,c):
    return (a[0]-c[0])*(b[1]-c[1])-(b[0]-c[0])*(a[1]-c[1])

def findfacet(p,simplice):
    c,b,a = simplice.coords
    b1 = sign(p,a,b) < 0.0
    b2 = sign(p,b,c) < 0.0
    b3 = sign(p,c,a) < 0.0
    return b1 == b2 == b3

data = np.random.randn(10, 2)
dtri = DelaunayTri(data)

interpolate = np.random.randn(3, 2)

for point in interpolate:
    for triangle in dtri.simplices:
        if findfacet(point,triangle):
            print "Point",point,"inside",triangle.coords
        break

matplotlib視覚化に使用（コードは省略）：

ここに画像の説明を入力

点線の水色の線は、内挿する三角形の頂点を補間する点を接続します。黒い線は凸包で、シアンの実線はドローネ三角形分割です。

于 2013-04-14T14:56:22.467 に答える
1

共通のエッジを除いて、三角形は交差しないと仮定します。

すべての三角形 (またはそれらのサブセット) を個別にチェックする必要はありません。主な理由は計算エラーです。これにより、複数の三角形 (またはゼロ) に対して「内側」の答えが得られ、プログラムのロジックが壊れる可能性があります。

より堅牢な方法は次のとおりです。

  1. 点に最も近いエッジを見つける
  2. このエッジに接する三角形の 1 つを選択してください
  3. その三角形を 1 つチェックします (点は 3 番目の三角形の頂点と同じ側にあります)。
  4. 「内側」の場合 - この三角形を返します
  5. 「外側」の場合 - このエッジの別の三角形を返します (他の三角形がない場合は「何もない」)。

計算エラーのために間違った三角形を返す場合でも、三角形は 1 つだけ存在し、点はそのような間違いを受け入れるのに十分なほど近くにあります。

#1 については、Michael Wild が示唆するように quad-tree のようなものを使用できます。

于 2013-04-12T10:57:04.003 に答える
1

Delaunay 三角形分割は、それ自体が検索データ構造です。Delaunay 三角形分割の実装には、おそらく位置関数が含まれています。ポイントの Delaunay 三角形分割をどのように計算しましたか?

CGALには、2D および 3D の三角形分割が実装されています。結果として得られるデータ構造は、特定のポイントからのウォークを使用して任意のポイントをローカライズできます。たとえば、マニュアルのその章を参照してください。CGAL は C++ ライブラリですが、python バインディングがあります。

于 2013-04-12T13:32:11.090 に答える