222

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

代替テキスト

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

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

私の検索結果：

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

4

12 に答える 12

151

私自身のポリゴンのクリッピングとオフセットのライブラリであるClipperについて簡単に触れておこうと思いました。

Clipperは主にポリゴン クリッピング操作用に設計されていますが、ポリゴン オフセットも行います。このライブラリは、 Delphi、C++、および C# で記述されたオープン ソースのフリーウェアです。非常に負担の少ないBoostライセンスがあり、フリーウェアと商用アプリケーションの両方で無料で使用できます。

ポリゴン オフセットは、四角、丸、留め継ぎの 3 つのオフセット スタイルのいずれかを使用して実行できます。

ポリゴン オフセット スタイル

于 2011-10-30T19:52:32.867 に答える
43

あなたが探しているポリゴンは、計算幾何学では内向き/外向きのオフセット ポリゴンと呼ばれ、ストレート スケルトンと密接に関連しています。

これらは、複雑なポリゴンのいくつかのオフセット ポリゴンです。

そして、これは別のポリゴンのストレート スケルトンです。

他のコメントでも指摘されているように、ポリゴンを「膨張/収縮」させる計画によっては、出力の接続が異なる場合があります。

計算の観点から: まっすぐなスケルトンがあれば、オフセット ポリゴンを比較的簡単に構築できるはずです。オープン ソースの (非商用の場合は無料の) CGALライブラリには、これらの構造を実装するパッケージがあります。CGAL を使用してオフセット ポリゴンを計算するには、このコード例を参照してください。

パッケージ マニュアルは、CGAL を使用しない場合でも、これらの構造を構築する方法の良い出発点を提供する必要があり、数学的な定義とプロパティを含む論文への参照が含まれています。

CGAL マニュアル: 2D ストレート スケルトンとポリゴン オフセット

于 2009-07-10T16:25:22.477 に答える
16

これらのタイプのものには、通常JTSを使用します。デモンストレーションの目的で、 JSTS (JTS の JavaScript ポート)を使用するこのjsFiddleを作成しました。必要な座標を JSTS 座標に変換するだけです。

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

結果は次のようになります。

ここに画像の説明を入力

追加情報: 私は通常、(リーフレットまたは Google マップを使用して) マップ上に描画されたポリゴンに半径の境界を設定するために、このタイプの膨張/収縮 (目的のために少し変更) を使用します。(lat,lng) ペアを JSTS 座標に変換するだけで、他はすべて同じです。例：

ここに画像の説明を入力

于 2016-08-26T09:55:29.577 に答える
11

あなたが望むもののように私には聞こえます：

  • 頂点から開始して、隣接するエッジに沿って反時計回りに向きます。
  • dエッジを、古いエッジの「左」から離れた位置に配置された新しい平行なエッジに置き換えます。
  • すべてのエッジに対して繰り返します。
  • 新しい頂点を取得するには、新しいエッジの交点を見つけます。
  • 交差したポリゴンになったかどうかを検出し、それをどうするかを決定します。おそらく、交差点に新しい頂点を追加し、いくつかの古い頂点を取り除きます。隣接していないエッジのすべてのペアを比較して、それらの交差が両方の頂点のペアの間にあるかどうかを確認するよりも、これを検出するためのより良い方法があるかどうかはわかりません。

結果のポリゴンは、頂点から「十分に」古いポリゴンから必要な距離にあります。頂点の近くでdは、古いポリゴンから離れた点のセットは、あなたが言うように、ポリゴンではないため、前述の要件を満たすことはできません。

このアルゴリズムに名前があるのか​​、Web上のコード例があるのか​​、それとも恐ろしい最適化なのかはわかりませんが、それはあなたが望むものを説明していると思います。

于 2009-07-10T13:41:07.103 に答える
6

GIS の世界では、このタスクにネガティブ バッファリングを使用します: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

JTS ライブラリがこれを行う必要があります。バッファ操作のドキュメントを参照してください: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

大まかな概要については、開発者ガイドも参照してください: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

于 2010-11-09T08:43:14.923 に答える
5

各線は、平面を「内側」と「輪郭」に分割する必要があります。これは、通常の内積法を使用して見つけることができます。

すべての線を少し外側に移動します。

隣接する線のすべてのペア（線分ではなく線）を考慮して、交点を見つけます。これらは新しい頂点です。

交差するパーツを削除して、新しい頂点をクリーンアップします。-ここにいくつかのケースがあります

（a）ケース1：

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

あなたがそれを1つ使うならば、あなたはこれを手に入れました：

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7と4が重なっています。これが表示された場合は、このポイントとその間のすべてのポイントを削除します。

（b）ケース2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

あなたがそれを2つ使うならば、あなたはこれを手に入れました：

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

これを解決するには、線の各セグメントについて、それが後のセグメントと重なっているかどうかを確認する必要があります。

（c）ケース3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

1ずつ消費します。これは、ケース1のより一般的なケースです。

（d）ケース4

case3と同じですが、2つ消費します。

実際、ケース4を処理できる場合、他のすべてのケースは、線または頂点が重なっている特殊なケースです。

ケース4を実行するには、頂点のスタックを保持します。後者の行と重なっている行を見つけたらプッシュし、後者の行を取得したらポップします。-凸包で行うのと同じように。

于 2009-07-10T13:40:10.303 に答える
5

これが別の解決策です。これが好きかどうかを確認してください。

  1. 三角測量を行います。ドローネーである必要はありません。三角測量であれば何でも構いません。

  2. 各三角形を膨らませます - これは些細なことです。三角形を反時計回りの順序で保存する場合は、線を右側に移動して交差させます。

  3. 修正されたWeiler-Atherton クリッピング アルゴリズムを使用してそれらをマージします。

于 2009-07-10T13:54:16.403 に答える
1

@JoshO'Brian からのアドバイスに基づいてrGeos、言語のパッケージがRこのアルゴリズムを実装しているようです。を参照してくださいrGeos::gBuffer。

于 2013-08-07T20:11:28.043 に答える