1

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

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

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

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

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

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

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

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

4

2 に答える 2

2

アルファ形状は、一連の点のドローネ三角形分割を見つけ、アルファを超えるエッジを削除することによって定義されます。ドローネ三角形分割は必要ですが、円は必要ありません。ラインにも対応しています。JS で形状を計算するには、TopoJSON を使用するか、次の回答を試してください: Delaunay triangulation からアルファ形状の境界ポリゴンを計算します。私の php パッケージhttp://concavehull.codeplex.com/を試すこともできます。

于 2014-05-05T08:47:53.077 に答える
1

このペーパーでは、凹包アルゴリズムの実装方法を読むことができます。基本的な考え方は、凸包を構築し、エッジを内側に屈曲 (凹) することです。このアルゴリズムの JavaScript 実装があります: hull.js。

于 2014-12-14T16:50:51.330 に答える