三角形グリッドの一番近い点

Question

ある点pに最も近い三角形グリッドの三角形グリッド（基底幅w、OX軸に平行）の最も近いグリッドノード（点として）を返す関数を書いてみたい。グリッドはポイントsで始まります。開始する方法== [0.5,0]

にexapmle snapToGrid（[0.49,0]、0.5 [0.0]）のため

def snapToGrid(p,w,s): 
    ... 

任意のアイデア：関数のシグネチャは次のようになりますか？

Answer 1

EDIT： この回答は、三角形グリッドが動的に計算されることを知る前のものですが、私は今のところそれを残しておきます。これは参考になるかもしれないが、動的ポイント生成には役立ちません。

私は、ポイントを動的に生成する答えは、三角形の高さを見つけ、その三角形の高さの倍数でノードが存在することに依存すると考えています。
これは、お客様のXコンポーネントを処理する必要があります。

三角形の幅を見つけると、Y軸に沿ってノードが発生する倍数がわかりますが、三角形の2番目ごとの行には、三角形の幅の1/2に節点があります。
原点から離れた行数を見つけると、元の点が最初のステップになります。順番に

これは、あなたがYは、複数の座標、またはY乗数のためtriangle width+1/2 triangle widthとしてtriangle widthを使用するかどうかを知らせることができます。

これらの2つの値を使用すると、最も近いn*heightとの組み合わせが最も簡単に見つかるはずです。テキストの壁については申し訳ありません

、あなたが紙の上で、あなたのグリッドを描く場合は、三角形は（odd rows用）X軸に沿ったノードの行、および列（even rows用）と半分の列を形成していることがわかります。

---

最も近い点を見つけるとき、グリッドがどのタイプ/シェイプであるかは問題ではありません。論理的には、あなたが最も近いポイントはあなたのポイントが入っているシェイプに属します。あなたがしなければならないことを単純化することは、あなたに最も近いポイントを見つけることです。

これは、K-D Treeを使用すると最も簡単に見つかるようです。スプリットポイントは、グリッドのXとYの座標です。単純なバイナリ検索では、入力した座標に最も近いグリッドポイントが表示されます。

リンクされた記事には、K-Dツリー操作の疑似コードがあります。

---

また、座標そのXに対応y:nameペアの辞書を含む各値と、X座標にマッピングされた辞書を有することができます。

これは、あなたが次のようにノードを検索できるようになります。その後、xvalueとyvalueを取得することは、単純に辞書のキーを通じて最寄りの検索を行うには、あなたが探しているノードを返します

coordinate_x[<xvale>][<yvalue>] 

like：

for x in coordinate_x.keys(): 
    if x-point_x < min: 
     make x-point the closest