問題タブ [computational-geometry]

http://www.compgeom.com/~piyush/scripts/triangle/の三角形 ++ ラッパー クラスを使用して、OpenGL で視覚化するための点群を三角測量しています。ポイントを入力して三角測量を計算することができました。その後、頂点イテレータを介して頂点にアクセスすることもできました。これは、パッケージに含まれている main.cpp の例に示されています。今、私は顔の反復子 (main.cpp にも例があります) を介して頂点にアクセスしたいと考えています。すべての面を反復処理して、すべての面の 3 つの頂点を取得したいと考えています。誰かがすでにそれをしましたか？私はラッパークラスを変更しようとしましたが、すでに 2 日ほど成功していません。

事前にどうもありがとう！セバスチャン

データ ポイントのセットを指定すると、kdtreeが作成されますが、この kdtree は一意のものですか?

線の点が三角形の内側（端ではない）にあるかどうかをテストするにはどうすればよいですか。（すべて2Dで）。

現在、私はこれを行うことを考えています：

• 線と三角形の各辺をAx+By + C = 0として定義し、xrangeを設定します。
• 線が三角形の線のいずれかと交差するかどうかを確認します。
• 含まれている場合は、これが行の終わりにないことを確認してください。

これを行うためのより良い方法はありますか？

2D 三角形分割を行った後、いくつかの三角形が同じ色になっているため、それらを再結合して、同じ色のグラフィックス パスに描画したいと考えています。三角形を 1 つずつ描画すると、一部のグラフィック レンダラーで三角形の間に継ぎ目が表示されることがわかりました (少なくともアンチエイリアシングや透明度が関係している場合)。

では、(重なり合っていない) 三角形のセットを取得して、穴やバラバラのポリゴンを含む可能性のあるグラフィックス パスを作成するにはどうすればよいでしょうか?

やみくもに三角形をグラフィックス パスに追加すると、塗りつぶしにはかなりうまく機能しますが (もちろんストロークには適していません)、これらの余分な内部ポイントをエクスポートするのは適切ではありません。

私は現在、運用期間にわたってデバイスがカバーするエリアを構築しようとしています。このプロセスの最初のステップは、カバーされた領域のポリゴンを構築することであるように見えます。パターンは標準的な形状ではないため、凸包は可能な限り最大のカバレッジエリアにジャンプすることでカバーエリアを誇張します。

非凸包生成の概念をカバーしているように見える論文を見つけましたが、これを高級言語で実装する方法についての議論はありません。 http://www.geosensor.net/papers/duckham08.PR.pdf

同じ結果を達成するために、非凸包または凹包、あるいはおそらく任意のPythonコードを構築するための簡単なアルゴリズムを見た人はいますか？

私は主にqhullの凸包を試しましたが、エッジサイズが限られており、成功は限られています。また、配布できないライセンスライブラリがあることに気づいたので、残念ながらそれはテーブルから外れています。より良いアイデアや料理本はありますか？

私は、エンティティが地球上の位置にあるアプリケーションを開発しています。ポイントが含まれている領域を判別できるデータセットが必要です。

リージョンには次のタイプがあります。

• 大陸
• 国
• 湖
• 海
• DMZ
• デザート
• 棚氷

...など。

各領域をポリゴンとして表現することを想定しています。任意のポイントについて、それが各ポリゴンに含まれているかどうかをテストします。代替案は大歓迎です。

また、これらの境界の一部またはすべてを含むパブリックドメインのデータセットを見つけたいと思っています。

これらのポリゴンの一部は非常に詳細になるため（おそらく必要以上に詳細になる可能性があります）、これらの計算を効率的に実行するためのヒントが必要です。2Dポリゴンを単純化する方法も役立つと思います。これらの種類のもののベストプラクティスは何ですか？

誰かがこのデータの優れたリソース、特定のプログラミングアプローチ、またはこの種のことを行う既存のソフトウェアライブラリを推奨できますか？

編集

リージョンのデータセットはかなり静的であるため、パフォーマンスが向上する場合は事前計算が適切なオプションであることを指摘しておく必要があります。

3D ポリゴン メッシュと対応する 2D ポリゴン メッシュ (実際にはUV マップから) があり、ジオメトリを 2D 平面にマッピングするために使用しています。平面上のポイントが与えられた場合、その 2D ポイントを 3D にマッピングするために、そのポイントが置かれているポリゴンを効率的に見つけるにはどうすればよいでしょうか?

私が考えることができる最善のアプローチは、ポリゴンを 2D インターバル ツリーに格納し、それを使用して候補ポリゴンを取得することです。より簡単なアプローチはありますか？

明確にするために、これはシェーダー用ではありません。私は実際に 2D の物理シミュレーションを取り、それを 3D メッシュに巻き付けてレンダリングしています。各オブジェクトを描画するには、実際の 2D 位置に対応する 3D のポイントを把握する必要があります。*

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

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

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

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

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

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

現在、接続性を最小ユークリッド距離として指定することにより、データセットから3Dポイントをグループ化しようとしているプロジェクトに取り組んでいます。現在の私のアルゴリズムは、単純なフラッドフィルの3D適応です。

このコードスニペットが新しいシードに対して再度実行され、_img.queryRadius（）がANNライブラリを使用した固定半径検索である場合：

このコードに関する私の問題は、大きなデータセットに対して実行が遅すぎることです。私が間違っていなければ、このコードはすべてのポイントを検索し、検索はO（NlogN）であるため、時間計算量は（N ^ 2 * log（N））になります。

それに加えて、KDツリーから直接覚えている場合、削除には比較的コストがかかりますが、ポイントを削除しないと、各ポイントが近くにあるすべてのポイントで何百回も検索される可能性があるという問題が発生します。

だから私の質問は、これを行うためのより良い方法はありますか？特に、データセットとともに直線的に成長する方法で？

あなたが提供できるかもしれないどんな助けにも感謝します

編集 dash-tom-bangが言ったような単純なソート済みリストを使用してみましたが、結果は以前使用していたものよりもさらに遅くなりました。それが実装だったのか、それとも単に遅すぎてすべてのポイントを反復処理してユークリッド距離をチェックできなかったのかはわかりません（2乗距離を使用した場合でも）。

人々が持っているかもしれない他のアイデアはありますか？私は今正直に困惑しています。

100万個の頂点を持つ2つのポリゴン間の最小距離を見つけたい(頂点間の最小距離ではありません)。最初の形状の各頂点と他の形状のすべての頂点との間の最短距離の最小値を見つける必要があります。Hausdorff Distanceのようなものですが、最大ではなく最小が必要です。