問題タブ [computational-geometry]

ボロノイ図を実装して、マップ内の最も近い場所を視覚的に見つけます。現在、キャンバス内でのみ整数座標 (x,y) を使用してこれを行いたいと考えています。

問題は-私はこのアルゴリズムについて本当に混乱しています。フォーチュンのアルゴリズムに関するいくつかの理論を含む、計算幾何学の本を読みました。そして今、私は本当に混乱しています。私がコーディングしようとしているとき、それは私にとって非常に複雑に思えます。

ボロノイ図の非常に単純な実装（指定された座標を使用）についてアドバイスしてください。ハッシュ、マルチスレッド、Delaunay Traingulation、派手な色などを使用しないで、単純なJavaまたはPythonまたはスキームコードをアドバイスしてください。

マルチスレッドやハッシュマップなしで Fortune のアルゴリズムを使用してボロノイ図を実装することはできませんか?

Delaunay三角形分割がそのステップである、内側軸抽出の実装を必要とするプログラムを書いています。外部内側軸は不要であるため、対応する外部三角形を削除する予定です。幸いなことに、多くの図が掲載されたページに出くわしました。また、内部および外部の Delaunay 三角形を決定する方法のヒント (「破線の周囲に基づく」) もありましたが、詳細な説明はなく、ヒントにすぎません。アルゴリズムを知っている人はいますか？

編集:最初の点が閉じた多角形の境界からサンプリングされることを忘れていました。私の意図は、各ドローネ三角形が多角形の内側にあるかどうかを判断することです。

私はポリゴンの中心線を見つける方法を理解することを任されました。私のグーグル検索は、私が必要としているものが「MedialAxis」と呼ばれていると私に信じさせました。このような：

_{（出典：kiev.ua）}

私が読んだことによると、必要なものは、セグメントの2Dボロノイ図構築アルゴリズムを使用して生成できます。

コードプレックス（FortuneVoronoi）でボロノイアルゴリズムのC＃バージョンを見つけました。ポリゴンを適用した後、次のようになります。

代替テキストhttp://www.carbonatlas.com/geonotes/gaia_voronoi.png

緑は元のポリゴンです。オレンジはボロノイ頂点で、黒い線はボロノイエッジです。

これらの頂点で必要なものの作成を確認できますが、不要なものをすべて除外するために必要な次のステップがわかりません。

私はあなたが提供できるどんな助けにも感謝します。

ポリゴンを「膨らませる」にはどうすればよいですか？つまり、私はこれに似た何かをしたいです：

要件は、新しい（膨張した）ポリゴンのエッジ/ポイントがすべて古い（元の）ポリゴンから同じ一定の距離にあることです（例の画像ではそうではないため、膨張した頂点に円弧を使用する必要がありますが、今のところそれを忘れてください;））。

私が探しているものの数学用語は、実際には内向き/外向きのポリゴンオフセットです。これを指摘するためのバリントに+1。別の名前はポリゴンバッファリングです。

私の検索結果：

ここにいくつかのリンクがあります：

• ポリゴンオフセット戦略の調査
• ポリゴンオフセット、問題
• ポリゴンデータのバッファリング

私はこれに非常に似た質問があります：

線がC＃の平面と交差するかどうかを知る方法は？

線が任意のポリゴンと交差しているかどうかを確認するメソッド（C＃）を探しています。

Chris Marasti-Georgによるアルゴリズムは非常に役に立ちましたが、最も重要な方法、つまり線間交叉が欠けていたと思います。

Chris Marasti-Georgのコードを完成させるための線交差法を知っている人はいますか？

C＃にこれのための組み込みコードはありますか？

この方法は、禁止領域機能で拡張されたBingMapsアルゴリズムで使用するためのものです。結果のパスは、禁止領域（任意のポリゴン）を通過してはなりません。

ポイントのリストがある場合、それらが時計回りの順序であるかどうかを確認するにはどうすればよいですか？

例えば：

それは反時計回り（または一部の人にとっては反時計回り）であると言うでしょう。

いくつかの凸多角形が点のSTLベクトルとして保存されています（多かれ少なかれ）。それらを非常に迅速に、できればかなり均等なサイズのピースに、「スライバー」なしでテッセレーションしたいと思います。

これを使用して、いくつかのオブジェクトを小さな断片に分解します。ポリゴンをテッセレーションする（小さな凸多角形または三角形のメッシュに分割する）ための優れたライブラリを知っている人はいますか？

すでにオンラインで見つけたものをいくつか見てきましたが、それらをコンパイルすることすらできません。これらのアカデミックタイプは、使いやすさをあまり考慮していません。

オンラインプログラミングコンテストで幾何学の問題を解決したい。しかし、私がそれらを読むときはいつでも、私はただ難しすぎると感じます。計算幾何学を研究できる本や資料をいくつか提案してください。

平面上の一連の点が与えられた場合、これらの点のうちの任意の 2 点によって形成される最短の線分を見つけます。

どうやってやるの？自明な方法は明らかに各距離を計算することですが、比較するには別のアルゴリズムが必要です。