＆＃8220;ビジュアル＆＃8221;を見つける最速の方法は何ですか不規則な形状の多角形の中心？
https://stackoverflow.com/questions/1203135
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
不規則な形状のポリゴンの視覚的中心であるポイントを見つける必要があります。視覚的中心とは、視覚的に多角形の広い領域の中心にあるように見える点を意味します。アプリケーションはポリゴン内にラベルを配置します。
内部バッファリングを使用するソリューションは次のとおりです。
これを使用する場合、バッファを見つけるための効果的かつ迅速な方法は何ですか？他の方法を使用する場合、その方法はどれですか？
本当に頑丈なポリゴンの好例は、巨大な太いU（Arial BlackまたはImpactまたはそのようなフォントで記述された）です。
解決
ポリゴンをバイナリイメージに変換できる場合、画像処理の分野に存在する基盤を使用できます。例：高速スケルトンアルゴリズム バイナリ画像を表すブロックについて。
しかし、これは一般的な場合、離散化エラーと余分な作業のために実際には合理的ではありません。
ただし、これらは便利な場合があります：
編集：ポリゴンに含まれる最大の円の中心であるポイントを探したいかもしれません。必ずしも観測された中心にあるとは限りませんが、ほとんどの場合、おそらく期待される結果が得られ、わずかに病理学的な場合にのみ完全にオフになります。
他のヒント
Polylabel というMapBoxから、これに対する非常に優れたソリューションを見つけました。完全なソースは、 Github でも入手できます。
本質的に、T Austinが言ったように、ポリゴンの視覚的中心を見つけようとします。
特定の詳細は、これが実用的な解決策であることを示唆しています：
残念ながら、[理想的なソリューション]の計算は両方とも複雑です そして遅い。問題に対する公開されたソリューションには、次のいずれかが必要です。 制約付きドロネー三角形分割または直線スケルトンを次のように計算 前処理ステップ＆＃8202;＆＃8212;＆＃8202;どちらも時間がかかり、エラーが発生しやすい。
ユースケースでは、正確な解決策は必要ありません＆＃8202;＆＃8212;＆＃8202;私たちは喜んで 精度を上げて速度を上げます。ラベルを貼るとき マップの場合、ミリ秒単位で計算することがより重要です 数学的に完璧になるように。
ただし、使用に関する簡単なメモ。ソースコードは、そのままJavascriptで使用できますが、「通常」で使用する場合は、ここでの関数は通常ではなく GeoJSONPolygons を取るため、ポリゴンを空の配列にラップする必要があります。ポリゴン、つまり
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
方法：
多角形の重心が多角形の内側にある場合は、それを使用します。それ以外の場合：
1）重心からポリゴンを通る線を延長して、ポリゴンを等しい面積の2つの半分に分割します
2）「ビジュアルセンター」は、線が境界線に接する最も近いポイントと、重心から遠ざかる方向に境界線を切断する次のポイントとの中間点です。
これを説明するための写真をいくつか示します。
多角形の各エッジの中心位置（x、y）を計算します。これを行うには、各エッジの端の位置の差を見つけます。各次元の各中心の平均を取ります。これがポリゴンの中心になります。
セントロイド法はすでに複数回提案されています。これは、プロセス（およびポリゴンに関するその他の多くの便利なトリック）を非常に直感的に説明する優れたリソースだと思います。
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
また、単純なUIラベルを配置するには、ポリゴンの境界ボックス（ポリゴンの頂点の最低および最高のxおよびy座標で定義される長方形）を計算し、その中心を取得するだけで十分な場合がありますで：
{
x = min_x + (max_x - min_x)/2,
y = min_y + (max_y - min_y)/2
}
これは、重心の計算よりも少し高速です。これは、リアルタイムまたは組み込みアプリケーションにとって重要な場合があります。
また、ポリゴンが静的な場合（フォームを変更しない場合）、BBの中心/重心の計算結果（ポリゴンの最初の頂点など）をポリゴンのデータ構造。
これが最速だと言っているわけではありませんが、多角形の内側にポイントを与えます。 ストレートスケルトンを計算します。探しているポイントはこのスケルトンです。たとえば、バウンディングボックスの中心までの法線距離が最も短いものを選択できます。
「インサークル」を見つける方法は？多角形（その中に収まる最大の円）、そしてラベルをその中心にセンタリングしますか？開始するためのリンクがいくつかあります：
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/ 144373.html？1219439473
これは、すべてのポリゴンで完全に機能するわけではありません。 Cのように見えるポリゴンでは、ラベルはやや予測できない場所にあります。ただし、ラベルが常にポリゴンのソリッド部分と重なるという利点があります。
リンク先の論文のポイントを理解している場合（興味深い問題がありますが、ところで）、この「内部バッファリング」はテクニックは、エッジからの酸によって溶解している砂糖の一部から問題の形状をモデリングすることに多少類似しています（たとえば、バッファ距離が増加すると、元の形状が少なくなります）残りの最後のビットは、ラベルを付けます。
アルゴリズムでこれを達成する方法は、残念ながらあまり明確ではありません。...
多角形を頂点に戻し、関数を適用して最大の凸包を見つけ、その凸包の中心を見つけると、「見かけ」と密接に一致すると思いますセンター。
頂点を指定して最大の凸包を見つける：単純な多角形の段落の下を見てください。
凸包の頂点を平均して中心を見つけます。
ラベルを（おそらくバウンディングボックスの）素朴な中心に配置し、ローカルポリゴンエッジとラベルのBBの交点に基づいて移動しますか？交差するエッジの法線に沿って移動し、複数のエッジが交差する場合、それらの法線を合計して移動しますか？
ここで推測するだけです。この種の問題では、パフォーマンスがあまり問題にならない限り、おそらく繰り返し解決しようとします。
今これを詳しく説明したりテストしたりする時間はあまりありませんが、機会があればもっとやろうとします。
重心を主な方法として使用します。重心がポリゴン内にあるかどうかをテストします。そうでない場合は、最も近いポイントを通り、ポリゴンの反対側に 線を引きます。ポリゴン内にあるそのラインのセクションの中点に、ラベルを配置します。
重心に最も近い点はかなり大きな領域に接している可能性が高いため、キラレッサの内接円と同様の結果が得られると思います。もちろん、穴のあるポリゴンがある場合、これはひどくなります。その場合、インサークルはおそらくかなり良いでしょう。一方、典型的な場合のデフォルトは（クイック？）重心法です。
この問題は、おそらく「重心」を見つけることに似ています。均一な密度を想定しています。
編集：この方法は、ポリゴンに「穴」がある場合は機能しません
土木工学で使用される重心（または重心）メソッドを使用できます。ここにウィキペディアからの便利なリンクがあります：
