不規則な形状の多角形の視覚的な中心となる点を見つける必要があります。視覚的中心とは、視覚的に多角形の広い領域の中心にあるように見える点を意味します。アプリケーションは、ポリゴンの内側にラベルを配置することです。
内部バッファリングを使用するソリューションは次のとおりです。
これを使用する場合、バッファを見つけるための効果的かつ迅速な方法は何ですか? 他の方法を使用する場合、その方法はどれですか?
非常にタフなポリゴンの良い例は、巨大な太い U (Arial Black や Impact などのフォントで書かれています) です。
Polylabel と呼ばれるMapBoxから、これに対する非常に優れた解決策を見つけました。完全なソースもGithubで入手できます。
基本的に、T Austin が言ったように、ポリゴンの視覚的な中心を見つけようとします。
特定の詳細は、これが実用的な解決策である可能性があることを示唆しています:
残念ながら、[理想的な解] の計算は複雑で時間がかかります。この問題に対する公開された解決策では、前処理ステップとして制約付きドローネ三角形分割または直線スケルトンの計算が必要ですが、どちらも遅くてエラーが発生しやすいものです。
私たちのユースケースでは、正確な解は必要ありません — 速度を上げるために精度をいくらか犠牲にしても構わないと思っています。マップにラベルを配置する場合、数学的に完全であるよりも、ミリ秒単位で計算されることが重要です。
ただし、使用に関する簡単なメモ。ソースコードはそのままで Javascript に最適に機能しますが、これを「通常の」ポリゴンで使用する場合は、ここの関数が通常のポリゴンではなくGeoJSONPolygonsを使用するため、空の配列でラップする必要があります。
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
ポリゴンをバイナリイメージに変換できる場合は、画像処理の分野に存在する基盤を使用できます。例：ブロック表現されたバイナリイメージの高速スケルトンアルゴリズム。
しかし、離散化誤差と余分な作業のため、これは一般的なケースでは実際には合理的ではありません。
ただし、これらが役立つ場合があります。
編集：ポリゴンに含まれる最大の円の中心である点を探したいと思うかもしれません。それは必ずしも観察された中心にあるとは限りませんが、ほとんどの場合、おそらく期待される結果が得られ、わずかに病理学的な場合にのみ、完全にオフになっています。
どうですか：
多角形の重心が多角形の内側にある場合はそれを使用し、そうでない場合:
1) 重心から多角形を通る線を延長し、多角形を 2 つの等しい面積に分割します。
2) 「視覚的中心」は、線が周囲に接する最も近い点と、重心から遠ざかる方向に周囲を切断する次の点との間の中間点です。
これを説明するための写真をいくつか示します。
重心式の使用を検討しましたか？
以下に、私が試した 5 つの異なるアプローチを示します。
cv2ベースの重心 ( get_center_of_mass)shapelyベース代表点 ( get_representative_point)cv2+スケルトン形状skimage.skeletonのベースの重心( )get_skeleton_center_of_massscipy国境までの距離に基づく ( get_furthest_point_from_edge)cv2国境までの距離に基づく ( get_furthest_point_from_edge_cv2)import numpy as np
import cv2
from shapely.geometry import Polygon
from skimage.morphology import skeletonize, medial_axis
from scipy.ndimage.morphology import distance_transform_edt
import matplotlib.pyplot as plt
H, W = 300, 300
def get_random_contour():
xs = np.random.randint(0, W, 4)
ys = np.random.randint(0, H, 4)
cnt = np.array([[x,y] for x,y in zip(xs,ys)])
mask = draw_contour_on_mask((H,W), cnt)
cnt, _ = cv2.findContours(mask, 1, 2)
cnt = cnt[0]
return cnt
def draw_contour_on_mask(size, cnt):
mask = np.zeros(size, dtype='uint8')
mask = cv2.drawContours(mask, [cnt], -1, 255, -1)
return mask
def get_center_of_mass(cnt):
M = cv2.moments(cnt)
cx = int(M['m10']/M['m00'])
cy = int(M['m01']/M['m00'])
return cx, cy
def get_representative_point(cnt):
poly = Polygon(cnt.squeeze())
cx = poly.representative_point().x
cy = poly.representative_point().y
return cx, cy
def get_skeleton_center_of_mass(cnt):
mask = draw_contour_on_mask((H,W), cnt)
skel = medial_axis(mask//255).astype(np.uint8) #<- medial_axis wants binary masks with value 0 and 1
skel_cnt,_ = cv2.findContours(skel,1,2)
skel_cnt = skel_cnt[0]
M = cv2.moments(skel_cnt)
if(M["m00"]==0): # this is a line
cx = int(np.mean(skel_cnt[...,0]))
cy = int(np.mean(skel_cnt[...,1]))
else:
cx = int(M['m10']/M['m00'])
cy = int(M['m01']/M['m00'])
return cx, cy
def get_furthest_point_from_edge(cnt):
mask = draw_contour_on_mask((H,W), cnt)
d = distance_transform_edt(mask)
cy, cx = np.unravel_index(d.argmax(), d.shape)
return cx, cy
def get_furthest_point_from_edge_cv2(cnt):
mask = draw_contour_on_mask((H,W), cnt)
dist_img = cv2.distanceTransform(mask, distanceType=cv2.DIST_L2, maskSize=5).astype(np.float32)
cy, cx = np.where(dist_img==dist_img.max())
cx, cy = cx.mean(), cy.mean() # there are sometimes cases where there are multiple values returned for the visual center
return cx, cy
このトピックに関する私の分析は次のとおりです。
get_center_of_massが最速ですが、このスレッドで述べたように、重心は非凸形状の形状の外側に配置できます。get_representative_pointも高速ですが、識別されたポイントは、常に形状の内側に留まることが保証されていますが (または、複数の切断された形状であってもマイナーな編集で!)、オブジェクトの中心とはあまり関係がありません。get_skeleton_center_of_mass知覚的に優れた中心点を返しますが、遅く、切断された形状のロジックが必要ですget_furthest_point_from_edge比較的高速で、切断された形状に簡単に一般化でき、中心点は視覚的に快適ですget_furthest_point_from_edge_cvそれ以外は同様に実行しますget_furthest_point_from_edgeが、桁違いに高速ですrows = 4
cols = 4
markers = ['x', '+', "*", "o", "^"]
colors = ['r','b','g','orange', "purple"]
functions = [
get_center_of_mass,
get_representative_point,
get_skeleton_center_of_mass,
get_furthest_point_from_edge,
get_furthest_point_from_edge_cv2
]
plt.figure(figsize=(2*cols, 2*rows, ))
for i in range(rows*cols):
cnt = get_random_contour()
mask = draw_contour_on_mask((H,W), cnt)
plt.subplot(cols,rows, i+1)
plt.imshow(mask, cmap='gray')
for c, m, f in zip(colors, markers, functions):
l = f.__name__
cx, cy = f(cnt)
plt.scatter(cx, cy, c=c, s=100, label=l, marker=m, alpha=0.7)
plt.tight_layout()
plt.legend(loc=3)
plt.show()
100 個のランダムな例で実行されたアルゴリズムの速度を比較すると、次のようになります。
N_EXAMPLES = 100
cnts = [get_random_contour() for _ in range(N_EXAMPLES)]
for fn in functions:
print(fn.__name__+":")
%time _ = [fn(cnt) for cnt in cnts]
print("~ "*40)
get_center_of_mass:
CPU times: user 1.39 ms, sys: 400 µs, total: 1.79 ms
Wall time: 1.75 ms
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
get_representative_point:
CPU times: user 16.9 ms, sys: 291 µs, total: 17.2 ms
Wall time: 16.8 ms
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
get_skeleton_center_of_mass:
CPU times: user 6.45 s, sys: 68.8 ms, total: 6.52 s
Wall time: 6.52 s
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
get_furthest_point_from_edge:
CPU times: user 499 ms, sys: 55 µs, total: 499 ms
Wall time: 499 ms
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
get_furthest_point_from_edge_cv2:
CPU times: user 51.4 ms, sys: 0 ns, total: 51.4 ms
Wall time: 51.4 ms
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
セントロイド法はすでに何度も提案されています。これは、プロセス（およびポリゴンに関する他の多くの便利なトリック）を非常に直感的に説明する優れたリソースだと思います。
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の中心/重心の計算結果（ポリゴンの最初の頂点など）を次のデータ構造に保存することで最適化できることにも注意してください。ポリゴン。
ポリゴンの各エッジの中心位置 (x,y) を計算します。これを行うには、各エッジの端の位置の違いを見つけます。各次元の各中心の平均を取ります。これがポリゴンの中心になります。
これが最速だと言っているわけではありませんが、ポリゴン内のポイントが得られます。ストレート スケルトンを計算します。お探しのポイントはこのスケルトンにあります。たとえば、境界ボックスの中心までの法線距離が最も短いものを選択できます。
多角形の「内接円」(その中に収まる最大の円) を見つけて、その中心にラベルを配置するのはどうですか? 開始するためのいくつかのリンクを次に示します。
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473
ほとんどの場合、これはすべてのポリゴンで完全に機能するとは限りません。C のように見える多角形は、やや予測不可能な場所にラベルを持っています。ただし、ラベルが常にポリゴンのソリッド部分に重なるという利点があります。
ラベルを（おそらくバウンディングボックスの）ナイーブな中心に配置し、ローカルポリゴンのエッジとラベルのBBの交点に基づいてラベルを移動できますか？交差するエッジの法線に沿って移動し、複数のエッジが交差する場合は、それらの法線を合計して移動しますか？
ここで推測するだけです。この種の問題では、パフォーマンスがそれほど問題にならない限り、おそらく繰り返し解決しようとします。
リンク先の論文の要点を理解していれば (非常に興味深い問題ですが)、この「内部バッファリング」手法は、エッジから酸によって溶解されている砂糖片から問題の形状をモデリングすることにいくらか類似しています。 . (たとえば、バッファー距離が増加するにつれて、元の形状の残りが少なくなります) 残っている最後のビットは、ラベルを配置する理想的な場所です。
残念ながら、アルゴリズムでこれを達成する方法は、私にはあまり明確ではありません....
ポリゴンを頂点に分割し、関数を適用して最大の凸包を見つけ、その凸包から中心を見つけると、「見かけの」中心と密接に一致すると思います。
与えられた頂点から最大の凸包を見つける: Simple Polygon 段落の下を見てください。
凸包の頂点を平均して中心を見つけます。
今はこれを詳しく説明したりテストしたりする時間はあまりありませんが、機会があればもっとやろうと思います。
主要な方法としてセントロイドを使用します。重心がポリゴン内にあるかどうかをテストします。そうでない場合は、最も近い点を通り、多角形の反対側に線を引きます。ポリゴン内にあるその線のセクションの中点に、ラベルを配置します。
重心に最も近いポイントは、かなり広い領域を境界付けている可能性が高いため、Kyralessa の内円と同様の結果が得られる可能性があると思います。もちろん、穴のあるポリゴンがある場合、これは凶暴になる可能性があります。その場合、インサークルはおそらくはるかに良いでしょう。一方、典型的なケースでは、デフォルトで（クイック？）重心法が使用されます。
土木工学で使用される重心 (または重心) メソッドを使用できます。ウィキペディアからの便利なリンクは次のとおりです。