非凸多边形中最大的圆

Question

如何找到能够适合凹多边形内部的最大圆？

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

- Plow

---

请注意，“实时”并不代表速度。实时意味着可以精确预测（在预定程度内）获得结果所需的时间。 - Neowizard

这些大概不是正多边形？ - user159335

@JonB 正确，这对于凹多边形应该可以工作。 - Plow

抱歉，今天我的阅读理解能力有些困难。 - user159335

对于凸多边形，请参考此处：https://dev59.com/_W865IYBdhLWcg3wKLT6 - math

Answer 1

解决这个问题的关键是先做出一个观察：适合任意多边形内部的最大圆的中心点是：

1. 在多边形内部；并且
2. 距离多边形边缘上的任何点最远。

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

这个问题在地理学中出现，并通过迭代解决以任意精度。它被称为难以到达的极点问题。请参见《难以到达的极点：计算地球上最遥远地方的算法》。

基本算法如下：

1. 将R定义为从（x _min ，y_min ）到（x_max ，y_max ）的直角区域；
2. 将R分成任意数量的点。该论文使用21作为启发式方法（即将高度和宽度除以20）；
3. 裁剪任何位于多边形外部的点；
4. 对于其余点，找到距离边缘上任何点最远的那个点；
5. 从该点定义一个具有较小间隔和范围的新R，并从步骤2开始重复，以获得任意精度的答案。该论文将R减小了根号2倍。

需要注意的是，如何测试一个点是否在多边形内或外：解决这个问题的最简单方法是向右投射一条射线。如果它跨过奇数条边，则在多边形内。如果是偶数，则在多边形外。

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

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

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

- cletus

---

似乎这是一个相当直接易懂的算法，正是我所需要的。根据文章所述，不能保证找到的解决方案是绝对最大值（但对于我的特定情况可能不是问题）。 - Plow

我认为这个算法可以修改以确保找到绝对最大值，方法是为每个矩形计算两个值：从多边形边缘的最大距离的下限（矩形的4个顶点的最大距离）和上限（通过添加0.5*sqrt(rect_size_x^2 + rect_size_y^2)）。然后，运行一个分段搜索，将所有未处理的候选矩形存储在优先队列中（按上限降序排序），并且放弃每个具有低于目前为止找到的最大下限的上限的矩形。 - Doc Brown

很遗憾，链接已经失效了... 另一个参考链接：http://arxiv.org/pdf/1212.3193.pdf - Blablaenzo

太棒了！这个解释让我只用几分钟就能在代码中实现解决方案。 - SeldomSeenSlim

是否有正确性证明或质量估计？如果点选择不当，这显然会陷入局部最小值。 - J S

这与非凸问题最流行的答案相同 https://dev59.com/MHM_5IYBdhLWcg3w2XBg#40464906 - StayOnTarget

Answer 2

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

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

- Mourner

---

这个在Java中可以用吗？ - Zaid Mirza

我需要在C#中使用它，所以进行了移植：https://gist.github.com/dfaivre/acfef42cdbf411555956e9eba65dd30d - David Faivre

相关：https://dev59.com/MHM_5IYBdhLWcg3w2XBg - StayOnTarget

这个答案真的帮了我很多！我需要在Dart中使用它，所以我进行了移植：https://pub.dev/packages/polylabel - André Sousa

Answer 3

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

广义沃罗诺伊图。

如果您将多边形的顶点和边视为一组站点，并将内部逐格分割成“最近邻单元格”，则会得到所谓的（广义）沃罗诺伊图。沃罗诺伊图由节点和连接它们的边组成。节点的间隙是其与定义多边形面的距离。

(这里的多边形甚至有洞; 原理仍然有效.)

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

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

另外，中轴线是从凸角顶点发出的沃罗诺伊边被删除的沃罗诺伊图。因此，最大内切圆的中心也位于中轴线上。

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

算法和实现。

您可以计算沃罗诺伊图。Fortune提出了一个最坏情况为O(n log n)的算法，用于点和线段，A sweepline algorithm for Voronoi diagrams，SoCG'86。Held发布了软件包Vroni，预期时间复杂度为O(n log n)，它实际上还可以计算最大内切圆。而且boost中似乎也有实现。

对于简单多边形（即没有洞的多边形），Chin等人提出了一种时间最优算法，其运行时间为O(n)，Finding the Medial Axis of a Simple Polygon in Linear Time，1999年。

暴力法。

然而，由于您表示使用暴力算法没有问题：那么试试所有三个站点（顶点和边缘）的三元组。对于每个三元组，您找到候选沃罗诺伊节点，即等距离的三个站点，并检查是否有任何其他站点会与候选最大内切圆相交。如果有相交，则将候选项取消。在所有三元组中找到您可以找到的最大值。

请查看我的硕士论文第3章，了解有关计算三个站点等距位置的更多细节。

- S. Huber

Answer 4

一个O(n log(n))算法:

1. 构建P中所有边的Voronoi图，可以使用例如Fortunes算法。
2. 对于在P内的Voronoi节点（到三条或更多边的距离相等的点）；
3. 找到与P中边距离最远的节点。该节点是最大内接圆的中心。

- Plow

---

您需要的是边的泰森多边形图，而不是顶点。例如，请参见http://valis.cs.uiuc.edu/~sariel/research/CG/applets/medial_axis/medial.html。边的泰森多边形图具有曲线段，而顶点的泰森多边形图仅具有直线。您所需的另一个名称是“中轴线”。这里有一个讨论差异的网站：http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m25/m25.html。 - brainjam

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

- Yang

Answer 6

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

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

请访问https://smartdiagram.com/simple-infographics-3d-charts-2/以尝试。

- Truong Do

---

对于凸多边形而言，直线骨架和泰森多边形图是一样的。但我更倾向于使用“泰森多边形图”一词，因为在更一般的情况下，最大内切圆问题可以通过泰森多边形图来解决，而不是通过直线骨架。如果您想了解有关直线骨架的理论背景，请参阅我12年前的博士论文：https://www.sthu.org/research/publications/files/phdthesis.pdf修订版本已出版成书，ISBN 978-3-8440-0938-5。 - S. Huber

Answer 7

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

二分查找最大半径R的圆：

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

- chhung6

---

似乎需要多边形的凸性。对于有孔或无孔的非凸多边形，我可以立即构造出例子，其中任何这样一组半平面的交集都将为空，因为可能存在两条“背靠背”的边。 - J S