57

我需要找到一个不规则形状多边形的视觉中心点。视觉中心是指在视觉上看起来位于多边形大面积中心的点。该应用程序是在多边形内放置一个标签。

这是一个使用内部缓冲的解决方案：

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

如果要使用它，找到缓冲区的有效且快速的方法是什么？如果要使用任何其他方式，那是哪种方式？

真正坚韧的多边形的一个很好的例子是一个巨大的厚 U（用 Arial Black 或 Impact 或类似字体编写）。

4

15 回答 15

21

我从 MapBox 中找到了一个非常好的解决方案，称为Polylabel。完整的源代码也可以在他们的Github上找到。

本质上，它试图像 T Austin 所说的那样找到多边形的视觉中心。

在此处输入图像描述

某些细节表明这可能是一个实用的解决方案：

不幸的是，计算[理想解决方案]既复杂又缓慢。该问题的已发布解决方案需要约束 Delaunay 三角剖分或计算直骨架作为预处理步骤——这两个步骤都很慢且容易出错。

对于我们的用例，我们不需要一个精确的解决方案——我们愿意牺牲一些精度来获得更快的速度。当我们在地图上放置标签时，以毫秒为单位计算比数学上的完美更重要。

不过，关于使用情况的快速说明。源代码非常适合开箱即用的 Javascript，但是如果您打算将其与“普通”多边形一起使用，那么您应该将其包装在一个空数组中，因为这里的函数采用GeoJSONPolygons而不是普通多边形，即

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
于 2016-11-07T12:11:37.170 回答
13

如果可以将多边形转换为二值图像，则可以使用图像处理领域中存在的基础，例如：A Fast Skeleton Algorithm on Block Represented Binary Images。

但这在一般情况下并不合理，因为离散化错误和额外的工作。

但是，也许您会发现这些有用：

编辑：也许你想寻找多边形中包含的最大圆的中心点。它不一定总是在观察中心，但大多数时候可能会给出预期的结果，只有在轻微的病理情况下才会完全偏离。

于 2009-07-29T21:52:21.750 回答
8

怎么样：

如果多边形的质心在多边形内，则使用它，否则：

1）从质心通过多边形延伸一条线，将多边形分成等面积的两半

2）“视觉中心”是直线与周边接触的最近点与沿远离质心的方向切割周边的下一个点之间的中间点

这里有几张图片来说明它：

在此处输入图像描述

在此处输入图像描述

于 2015-12-01T21:19:56.940 回答
7

您是否考虑过使用质心公式？

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

于 2009-07-29T21:51:28.553 回答
3

这是我尝试过的五种不同的方法。

  1. cv2基于质心 ( get_center_of_mass)
  2. shapely基于代表点 ( get_representative_point)
  3. cv2+skimage.skeleton基于骨架形状的质心 ( get_skeleton_center_of_mass)
  4. scipy基于到边界的最远距离 ( get_furthest_point_from_edge)
  5. 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
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
于 2020-12-22T13:04:22.040 回答
2

计算多边形每条边的中心位置 (x,y)。您可以通过查找每条边的末端位置之间的差异来做到这一点。取每个维度中每个中心的平均值。这将是多边形的中心。

于 2009-07-29T21:31:55.200 回答
2

质心法已经被多次提出。我认为这是一个很好的资源，它非常直观地描述了这个过程（以及许多其他有用的多边形技巧）：

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 中心/质心计算的结果（相对于例如多边形的第一个顶点）保存到数据结构中进行优化多边形。

于 2012-06-06T11:04:12.960 回答
1

我并不是说这是最快的，但它会给你一个多边形内的点。计算直骨架。你要找的点就在这个骨架上。例如，您可以选择到边界框中心的法线距离最短的那个。

于 2009-07-29T22:46:49.483 回答
0

如何找到多边形的“内圆”（适合其中的最大圆），然后将标签置于其中心？这里有几个链接可以帮助您入门：

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

这很可能不会在每个多边形上都完美运行；一个看起来像 C 的多边形的标签会出现在一个有点不可预测的位置。但优点是标签总是与多边形的实体部分重叠。

于 2009-07-29T21:58:59.410 回答
-1

我认为，如果您将多边形折回其顶点，然后应用一个函数来找到最大的凸包，然后找到该凸包的中心，它将与“明显”中心紧密匹配。

在给定顶点的情况下找到最大的凸包：查看“简单多边形”段落。

平均凸包的顶点以找到中心。

于 2009-07-29T21:32:32.280 回答
-1

如果我理解您链接到的论文的要点（顺便说一句，这是一个非常有趣的问题），这种“内部缓冲”技术有点类似于用一块被酸从边缘溶解的糖建模所讨论的形状. （例如，随着缓冲距离的增加，保留的原始形状会减少）最后一位是放置标签的理想位置。

不幸的是，如何在算法中实现这一点对我来说不是很清楚......

于 2009-07-29T21:34:50.387 回答
-1

你能把标签放在天真的中心（也许是边界框），然后根据局部多边形边缘和标签BB的交点移动它吗？沿着相交边的法线移动，如果多条边相交，将它们的法线相加以进行移动？

只是在这里猜测；在这类问题中，只要性能不是太大问题，我可能会尝试迭代解决。

于 2009-07-29T21:49:16.873 回答
-1

现在没有太多时间来详细说明或测试这个，但是当我有机会时，我会尝试做更多的事情。

使用质心作为您的主要方法。测试质心是否在多边形内；如果没有，请画一条线穿过最近的点并到达多边形的另一侧。在多边形内该线部分的中点，放置标签。

因为最接近质心的点可能会限制相当大的区域，我认为这可能会产生类似于 Kyralessa 的内圈的结果。当然，如果你有一个带孔的多边形，这可能会发疯。在那种情况下，内圈可能会好得多。另一方面，对于典型情况，它默认为（快速？）质心方法。

于 2009-07-29T22:08:14.973 回答
-2

这个问题可能类似于在假设密度均匀的情况下找到“质心”。

编辑：如果多边形有“洞”，此方法将不起作用

于 2009-07-29T21:27:25.803 回答
-3

您可以使用土木工程中使用的质心（或重心）方法，这是来自维基百科的有用链接：

http://en.wikipedia.org/wiki/Center_of_mass

于 2013-04-25T08:38:34.397 回答