問題タブ [concave-hull]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
10 に答える
32747 参照

algorithm - 2D凹型船体を生成するための効率的なアルゴリズムはありますか?

GISファイル(都市地図)からの(2D)ポイントのセットがあるので、そのマップ(その境界)の「等高線」を定義するポリゴンを生成する必要があります。その入力パラメータは、設定されたポイントと「最大エッジ長」になります。次に、対応する(おそらく非凸の)ポリゴンを出力します。

これまでに見つけた最善の解決策は、ドロネー三角形を生成してから、最大エッジ長よりも長い外部エッジを削除することでした。すべての外部エッジがそれよりも短くなった後、内部エッジを削除して、必要なポリゴンを取得します。問題は、これは非常に時間がかかることであり、もっと良い方法があるかどうか疑問に思っています。

0 投票する
4 に答える
7587 参照

c# - 凹包アルゴリズムを C# に変換する

だから私は凹包のためにここにあるアルゴリズムを翻訳しようとしています: http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf

(65ページ)

私はすべてを読んだことがありますが、実装方法がわかりsortByAngleませangleん. これは私がこれまでに持っているものです:

ここには大量のコードがあることを知っています。しかし、コンテキストとそれなしで私が持っているものを示すことができるかどうかはわかりません.

その他のクラス:

0 投票する
1 に答える
113 参照

connect - ポイントの再構築

私が持っていたアイデアの 1 つについてお聞きしたいのですが、解決策がわかりません。私のアイデアは次のとおりです。

長方形で覆われた一連の GPS 座標ポイントを持って、その形状に従ってそれらのポイントを接続する方法、それらのポイントを接続するために Quick Hull を試したところ、凸状になり、期待した結果ではありませんでした。たとえば、「L」字型に沿った一連の点があるので、それらを接続すると「L」型になります。

voronoi と delaunay を試しましたが、まだ良い結果が得られませんでした!!

これに対する良い解決策を見つけるのを手伝ってくれてありがとう。

本当に感謝しています!

みんな、ありがとう

0 投票する
0 に答える
595 参照

3d - 与えられた 3D 凹面ハル、サーフェスを見つける

3D オブジェクトを定義するサーフェスのリストがあります。これらのサーフェスには次の制約があります。

  • 各サーフェスは、その境界を定義する頂点の配列で定義されます
  • サーフェスの内側に穴はありません
  • サーフェスが重なり合ったり、他のサーフェスを通り抜けたりしない
  • サーフェスの各エッジの各頂点が含まれます
  • すべての面が少なくとも 2 つの他の面に隣接している
  • これらのサーフェスによって作成されたオブジェクトは凹面である可能性があります

これらのサーフェスによって作成された 3D オブジェクトの外側のハルを取得したい - 3D オブジェクト内に空のスペースはありません
アルゴリズムを知っている人はいますか?

問題:

.) このサーフェスにのみ接触するエッジを持つすべてのサーフェスを既に除外できます。

  • 各サーフェス エッジは少なくとも 2 つのサーフェスの一部です

ただし、4 つの立方体が 1 つのエッジだけで互いに接しているイメージを作成すると、それらの間に 3D オブジェクトの一部ではない単一のサーフェスを作成できます。

.) 船体の一部のみのサーフェスの 3D オブジェクトを取得するのは簡単です。しかし、3D オブジェクト内にサーフェスがあり、ハルに接続されている場合、どうすればそれらを見つけることができますか?

どんな指針も素晴らしいでしょう。前もって感謝します

0 投票する
2 に答える
325 参照

arrays - bool-grid から多角形を見つける

私はこのようなboolの2次元配列を持っています

bool の 2 次元配列

形状に穴はありません (穴があっても無視します)。今、私は自分の形を包含するポリゴンを見つけたいと思っています:

抱きしめる

この場合に使用できるアルゴリズムはありますか? 何も見つかりませんでしたが、このタスクの正しい検索用語を知っているかどうかはわかりません。

0 投票する
2 に答える
2033 参照

javascript - マップ画像から「凹船体」を検出

私は、Waze (よく知られている無料の GPS ナビゲーター) 用のオープンソース JavaScript プラグインを開発しています。特にオンライン エディター用です。このユーザースクリプトのアイデアは、均一な色の大きな地図エリアをすばやく選択してランドマークに変換できるようにすることです。

これまでのところ、Photoshop などのグラフィック エディターで「マジック ワンド」と呼ばれるツールの実装に成功しました。ユーザーが地図上のどこか (湖や森など) をクリックすると、スクリプトが同じ色で覆われた領域全体を選択し、多角形を作成します。ランドマーク用。

画像処理後に境界としてマークされたピクセル

凸包アルゴリズムを使用して...まあ...凸包を取得していることを除いて、すべてがうまく機能します:)つまり、見つかったポイントクラウドの最も外側のポイントを接続するポリゴンです。

自動的に作成されたランドマーク

しかし、誰もが理解しているように、現実世界のオブジェクトのほとんどが凹面領域を持つポリライン形状を持っているのに対し、凸形状を持っているランドマークはごくわずかです。上の写真では、このエリアには鋭いエッジがほとんどなく、右下の隅にある農地が凸包で覆われていることがわかりますが、これは誤りです。

私は適切なアルゴリズムをグーグルで検索し、数学論文を掘り下げていましたが、まだ見つけることができませんでした。ここ Stackoverflow で凹包について最もよく寄せられる質問は、アルファ形状と Delaunay 三角形に関するものです。場合の使用方法はわかりませんが、すべてのポイントが互いに接続されて連続したポリラインを形成しているため、半径が 1 ピクセルに等しい円でさえアルファ露出されているため、適切なアルファ半径を見つけることができないようです。

凹面ハルを構築するという目標をアーカイブする方法についてのアイデアは大歓迎です! 間違った方向に進んでいる可能性があり、ビットマップのベクトル化アルゴリズムを調べる必要がありますか?

0 投票する
1 に答える
2046 参照

c++ - CGAL とビジュアライゼーションで 3D アルファ シェイプを作成する

私は、基本的な C++ の経験を持つ新しい CGAL ユーザーで、一連の点の 3D アルファ形状を見つけようとしています。私はex_alpha_shapes_3サンプル コードを使用しており、結果を視覚化するためにCGAL アルファ シェイプ サーフェス メッシュを保存する手順を使用しています。すべて正常に動作しているように見えますが、アルファの値を置き換えて変更しようとすると

3 番目の変数が alpha (= 1) の値であると仮定し、この値を毎回変更しても、結果に変化はありません。

より具体的には、私の粒子のセットでは、一部が大部分から切り離されており、凹包またはアルファ形状を使用して、それらを個別のボリューム (図 41.1と同様) で表現したいと考えています。現在、(視覚化に Tecplot を使用して) 得られたものは次のとおり ここに画像の説明を入力 です。ご覧のとおり、切り離された粒子は他の粒子に接続されています。最後にコードも添付します。この問題について何か助けていただければ幸いです。