非凸多边形内最大的圆

Question

如何找到可以容纳在凹多边形内的最大圆？

只要能够实时处理具有约 50 个顶点的多边形，暴力算法就可以。

Answer 1

解决这个问题的关键是首先进行观察：适合任意多边形的最大圆的中心是以下点：

1. 在多边形内； 。
2. 距离多边形边缘上的任意点最远

为什么？因为圆的边缘上的每个点到圆心的距离都相等。根据定义，最大的圆将具有最大的半径，并且至少在两个点上接触多边形，因此如果您找到距离多边形最远的点，您就找到了圆的中心。

这个问题出现在地理学中，并且可以以任意精度迭代解决。它被称为“难以到达的极点”问题。请参阅难以到达的极点：地球上最偏远地点的计算算法。

基本算法的工作原理如下：

1. 将 R 定义为从 (x_min,y_min) 到 (x_max,y _{的直线区域>最大）；}
2. 将 R 分成任意数量的点。论文使用 21 作为启发式（意味着高度和宽度除以 20）；
3. 裁剪多边形外部的任何点；
4. 对于余数，找到距离边缘上任意点最远的点；
5. 从那时起，定义一个具有较小间隔和界限的新 R，并重复步骤 2 以获得任意精度答案。论文将 R 减小了 2 的平方根。

需要注意的是，如何测试一个点是否在多边形内部：这部分问题的最简单解决方案是将一条射线投射到该点的右侧。如果它穿过奇数条边，则它在多边形内。如果是偶数，则在外面。

此外，就测试到任何边的距离而言，您需要考虑两种情况：

1. 该点垂直于该边上的点（在两个顶点的边界内）；或者
2. 它不是。

(2)很容易。到边缘的距离是到两个顶点的距离中的最小值。对于 (1)，该边缘上最近的点将是从您正在测试的点开始与边缘以 90 度角相交的点。请参阅点到射线或线段的距离。

Answer 2

如果有人正在寻找实际的实现，我设计了一种更快的算法，可以在给定的精度下解决这个问题，并将其作为一个 JavaScript 库。它类似于@cletus描述的迭代网格算法，但它保证获得全局最优，并且在实践中也快了20-40倍。

看看： https://github.com/mapbox/polylabel

Answer 3

摘要：理论上，这可以在 O(n) 时间内完成。实际上，您可以在 O(n log n) 时间内完成。

广义 Voronoi 图。

如果您将多边形的顶点和边视为一组位点，并将内部细分为“最近邻单元”，那么您将得到所谓的（广义）Voronoi 图。 Voronoi 图由节点和连接节点的边组成。节点的间隙是到其定义的多边形面的距离。

（这里的多边形即使有孔，原理仍然有效。）

现在的关键观察是最大内切圆的中心接触多边形的三个面（顶点或边），并且没有其他面可以更接近。因此中心必须位于 Voronoi 节点上，即间隙最大的节点。

在上面的示例中，标记最大内切圆中心的节点接触多边形的两条边和一个顶点。

顺便说一句，中轴是 Voronoi 图，其中删除了从反射顶点发出的 Voronoi 边。因此，最大内接圆的中心也位于中轴上。

来源：我的一篇博客文章，涉及概括某点的最大内切圆。在那里您可以找到有关 Voronoi 图及其与最大内切圆的关系的更多信息。

算法与

您实际上可以计算 Voronoi 图。 Fortune 给出了点和线段的最坏情况 O(n log n) 算法，Voronoi 图的扫描线算法，SoCG'86。 Held 发布了软件包 Vroni，预期为 O (n log n) 时间复杂度，实际上也计算最大内切圆。 boost 中似乎有一个实现， 也。

对于简单多边形（即没有孔），Chin 等人提出了一种在 O(n) 时间内运行的时间最优算法，在线性时间内查找简单多边形的中轴，1999。

蛮力。

但是，正如您所说，您是使用暴力算法就可以了：简单地尝试所有三元组（顶点和边）怎么样？对于每个三元组，您找到候选 Voronoi 节点，即到三个位点的等距位点，并检查是否有任何其他位点与候选最大内切圆相交。如果存在交叉点，您将解雇该候选人。从所有三胞胎中找出最大的一个。

请参阅我的硕士论文中的第 3 章，了解有关计算等距位点的更多详细信息三个站点。

Answer 4

O(n log(n)) 算法：

1. 构造 P 中边的 Voronoi 图。例如，这可以通过 Fortunes 算法 来完成。
2. 对于 P 内的 Voronoi 节点（与三个或更多边等距的点）；
3. 找到 P 中到边的距离最大的节点。该节点是最大内切圆的圆心。

Answer 5

我实现了一段基于cv2的python代码，以获取掩模/多边形/轮廓内的最大/最大内切圆。它支持非凸/空心形状。

import cv2
import numpy as np
def get_test_mask():
    # Create an image
    r = 100
    mask = np.zeros((4 * r, 4 * r), dtype=np.uint8)

    # Create a sequence of points to make a contour
    vert = [None] * 6
    vert[0] = (3 * r // 2, int(1.34 * r))
    vert[1] = (1 * r, 2 * r)
    vert[2] = (3 * r // 2, int(2.866 * r))
    vert[3] = (5 * r // 2, int(2.866 * r))
    vert[4] = (3 * r, 2 * r)
    vert[5] = (5 * r // 2, int(1.34 * r))
    # Draw it in mask
    for i in range(6):
        cv2.line(mask, vert[i], vert[(i + 1) % 6], (255), 63)
    return mask


mask = get_test_mask()

"""
Get the maximum/largest inscribed circle inside mask/polygon/contours.
Support non-convex/hollow shape
"""
dist_map = cv2.distanceTransform(mask, cv2.DIST_L2, cv2.DIST_MASK_PRECISE)
_, radius, _, center = cv2.minMaxLoc(dist_map)

result = cv2.cvtColor(mask, cv2.COLOR_GRAY2BGR)
cv2.circle(result, tuple(center), int(radius), (0, 0, 255), 2, cv2.LINE_8, 0)

# minEnclosingCircle directly by cv2
contours, _ = cv2.findContours(mask, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)[-2:]
center2, radius2 = cv2.minEnclosingCircle(np.concatenate(contours, 0))
cv2.circle(result, (int(center2[0]), int(center2[1])), int(radius2), (0, 255, 0,), 2)

cv2.imshow("mask", mask)
cv2.imshow("result", result)
cv2.waitKey(0)

红色圆圈是最大内切圆

来源：https://gist.github.com/DIYer22/f82dc329b27c2766b21bec4a563703cc

Answer 6

我使用直骨架将图像放置在多边形内，分三个步骤：

1. 使用直骨架算法找到直骨架（图​​ 1）
2. 在直骨架的基础上，找到最大的圆（图 2）
3. 在该圆内绘制图像（图 2 ） 3）

尝试一下：https://smartdiagram.com/simple-infographics-3d -charts-2/

Answer 7

O(n log X) 算法，其中 X 取决于您想要的精度。

对圆的最大半径 R 进行二分搜索：

在每次迭代中，对于给定的半径 r，将每条边 E“向内”推 R，以获得 E'。对于每条边 E'，将半平面 H 定义为多边形“内部”的所有点的集合（使用 E' 作为边界）。现在，计算所有这些半平面 E' 的交集，这可以在 O(n) 时间内完成。如果交点非空，那么如果以交点中的任意点为圆心绘制半径为 r 的圆，则该圆将位于给定多边形内。