非凸多边形内的最大圆
Plo*_*low 41 algorithm geometry polygon computational-geometry
如何找到可以放入凹多边形内的最大圆？
只要能够实时处理具有~50个顶点的多边形,蛮力算法就可以了.
cle*_*tus 42
解决这个问题的关键是首先进行观察:适合任意多边形的最大圆的中心是:
- 在多边形内; 和
- 离多边形边缘任意一点最远.
为什么？因为圆的边缘上的每个点都与该中心等距.根据定义,最大的圆将具有最大的半径,并将在至少两个点上触摸多边形,因此如果您发现距离多边形最远的点,则您找到了圆的中心.
此问题出现在地理位置,并以迭代方式解决为任意精度.它被称为无法接近的极点问题.参见不可接近的极点:地球上最远地方的计算算法.
基本算法的工作方式如下:
- 将R定义为从(x min,y min)到(x max,y max)的直线区域;
- 将R除以任意数量的点.本文使用21作为启发式(意思是将高度和宽度除以20);
- 剪辑多边形外的任何点;
- 对于其余部分,找到距边缘上任何点最远的点;
- 从那时起定义一个具有较小间隔和边界的新R,并从步骤2重复以获得任意精度答案.本文将R减少了2的平方根.
一个注意事项,如何测试一个点是否在多边形内部:这部分问题的最简单的解决方案是将光线投射到该点的右侧.如果它穿过奇数个边,则它在多边形内.如果它是偶数,它就在外面.
此外,只要测试到任何边缘的距离,您需要考虑两种情况:
- 该点垂直于该边缘上的一个点(在两个顶点的边界内); 要么
- 事实并非如此.
(2)很容易.到边缘的距离是到两个顶点的距离的最小值.对于(1),该边缘上的最近点将是从您正在测试的点开始以90度角与边缘相交的点.请参见点到光线或线段的距离.
- 坏链接坏了......另一个参考：http://arxiv.org/pdf/1212.3193.pdf (2认同)
Plo*_*low 14
一个O(n log(n))算法:
- 构造P中边缘的Voronoi图.这可以通过例如Fortunes算法来完成.
- 对于P内部的Voronoi节点(等距三个或更多边缘的点);
- 找到P中边缘距离最大的节点.此节点是最大内切圆的中心.
- 你想要*edge*的Voronoi图,而不是顶点.例如,参见http://valis.cs.uiuc.edu/~sariel/research/CG/applets/medial_axis/medial.html.边Voronoi图有曲线段,顶点Voronoi图只有直线.你想要的另一个名字是"medial axis".这是一个讨论差异的网站:http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m25/m25.html (6认同)
Mou*_*ner 14
如果有人正在寻找一个实际的实现,我设计了一个更快的算法,解决了这个问题的给定精度,并使其成为一个JavaScript库.它类似于@cletus描述的迭代网格算法,但它保证获得全局最优,并且在实践中也快20-40倍.
看看:https://github.com/mapbox/polylabel
简介：理论上，这可以在O（n）时间内完成。实际上，您可以在O（n log n）的时间内完成此操作。
广义Voronoi图。
如果将多边形的顶点和边缘视为一组位置，并将内部细分为“最近的相邻单元”，则会得到所谓的（广义）Voronoi图。Voronoi图由节点和连接它们的边组成。节点的间隙是到其定义的多边形面的距离。
（这里的多边形甚至有孔；原理仍然有效。）
现在的主要观察结果是，最大内切圆的中心接触多边形的三个面（顶点或边），并且没有其他面可以靠近。因此，中心必须位于Voronoi节点上，即具有最大间隙的节点上。
在上面的示例中，标记最大内切圆的中心的节点接触多边形的两个边和一个顶点。
顺便说一下，中间轴是Voronoi图，其中从反射顶点发出的那些Voronoi边缘已删除。因此，最大内切圆的中心也位于中间轴上。
资料来源：我的一篇博客文章，该文章在某些时候讨论了最大内切圆的概括。在这里，您可以找到有关Voronoi图及其与最大内切圆的关系的更多信息。
算法与实现。
您实际上可以计算Voronoi图。Fortune给出了一种针对点和线段的最坏情况的O（n log n）算法，这是Voronoi图的扫掠线算法 SoCG'86。Held发布了具有预期O（n log n）时间复杂度的软件包Vroni，该软件包实际上也计算了最大内切圆。而且似乎在boost中也有一个实现。
对于简单的多边形（即没有孔），运行时间为O（n）的时间最优算法归因于Chin等人，《在线性时间中找到简单多边形的中间轴》，1999年。
蛮力。
但是，正如您所说的，使用蛮力算法就可以了：简单地尝试站点的所有三元组（顶点和边）怎么办？对于每个三元组，您都找到候选Voronoi节点，即与这三个位点等距的基因座，并检查是否有其他位点与候选最大内切圆相交。如果有交叉路口，则解雇候选人。尽最大可能在所有三胞胎中找到。
有关在三个地点计算等距基因座的更多详细信息，请参见我的硕士论文的第3章。