問題タブ [computational-geometry]

ここにいくつかのコードがあります：

マニュアルから：

「エッジは明示的に表現されず、2 つの面の隣接関係を通じて暗黙的に表現されるだけです。各エッジには 2 つの暗黙的な表現があります。インデックス i の頂点に対向する面 f のエッジは、 f の隣接 (i) のエッジ。"

CT::Finite_edges_iteratorそれは私には問題ありません...しかし、上記のコードでa を使用してエッジの終了頂点を取得するにはどうすればよいですか?

更新: 私はこの解決策を思い付くことができました:

私はまだこれを行うためのより良い方法を探しています。

4 つの 2D ポイントの凸包を計算するアルゴリズムが欲しいです。一般化された問題のアルゴリズムを見てきましたが、4 点の簡単な解決策があるのだろうかと思います。

GPCを使用して、ポリゴンを三角形に分割しています。ただし、GPCは、三角形の生成中に追加の頂点を作成していることは明らかです。これを回避する方法はありますか？

2Dメッシュグリッドで接続された1000個の三角形がいくつかあります。それは水の流れを表しています。このグリッドは、ドロネー三角形分割です。三角形をマージして最小限の単純なポリゴンに戻し、各ポリゴンに内部の穴がないように制約する必要があります。出力ポリゴンは同じ形状である必要があります。

これを達成するための既知のアルゴリズムはありますか？

重複の可能性:最大部分行列アルゴリズムを見つける

問題について助けが必要です。

各行に文字 (az) で表されるMxNボードがある場合、2 種類の文字しかない最大の領域を見つける必要があります。領域は長方形でなければなりません。例を次に示します。MN

出力は 6 になります。文字が 2 種類しかない最大の長方形の領域は上隅 AAA-ABB にあるため、A と B (2 種類) しかありません。

フォーチュンのアルゴリズムを使用して、一連の点のボロノイ図を見つけました。返されるのは線分のリストですが、どの線分が閉じた多角形を形成しているかを知り、それらを囲む元の点によってハッシュされたオブジェクトにまとめる必要があります。

これらを見つけるための最速の方法は何ですか?? アルゴリズムからいくつかの重要な情報を保存する必要がありますか? もしそうなら何？

これは、C++ 実装から移植された Java でのフォーチュンのアルゴリズムの実装です。

（コンパイルできないこと、データ構造を初期化する必要があること、およびインポートが欠落していることはわかっています）

私が欲しいのはこれです：

これを行うために私が考えることができる最も直接的な強引な方法は、ダイアグラム内のポイント (エッジのエンドポイント) の無向グラフを作成することです。次に、このグラフ内のすべてのループを探し、3 つ以上のポイントを共有するループの各セットについて、最短のループ以外をすべて破棄します。ただし、これは遅すぎるでしょう。

3D サーフェスがあります (xy 平面について考えてください)。平面は傾けることができます。（坂道を考えてみてください）。

表面を定義する 3D 座標のリスト ( Point3D1X、Point3D1Y、Point3D1Z、Point3D12X、Point3D2Y、Point3D2Z、Point3D3XなどPoint3D3Y)が与えられた場合Point3D3Z、表面の面積を計算する方法は?

ここでの私の質問は、2D 平面で面積を見つけることに類似していることに注意してください。2D 平面では、多角形を定義する点のリストがあり、この点のリストを使用して多角形の面積を見つけることができます。zここで、これらすべてのポイントが3D で隆起してサーフェスを形成するような値を持っていると仮定します。私の質問は、その 3D サーフェスの面積を見つける方法です。

これは、こちらの質問と同様の質問です。

サーフェスを定義する 3D 座標のリスト ( Point3D1、Point3D2、など) が与えられた場合、サーフェスの重心Point3D3を計算する方法は?

2D では、計算は次の式で与えられます。

3Dアナログはどうですか？

kd ツリーについて読みましたが、空間の次元が高い場合は非効率的です。値のデータベースがあり、クエリから特定のハミング距離内にある値を見つけたいと考えています。たとえば、データベースは 32 ビットの数値のリストであり、クエリ値との差が 3 ビット未満のすべての数値を見つけたいとします。

MultiVariate Partition trees についてどこかで聞いたことがありますが、適切なリファレンスが見つかりませんでした。min-Hash の方が適切な近似値を提供することは知っていますが、正確な答えが欲しいです。

2 つの任意のポリゴンをパッキングする際に問題があります。つまり、2 つの任意のポリゴンがあります。この多角形に外接する長方形の面積が最小の場合、この多角形のそのような配置を見つける必要があります (回転と移動を行うことができます)。

私は、これが NP 完全問題であることを知っています。この問題を解決するための効率的なアルゴリズムを選択したいと考えています。No-Fit-Polygon アプローチを探しています。しかし、任意の 2 つのポリゴンの NFP を見つけるための単純で明確なアルゴリズムはどこにも見つかりませんでした。