我有一组代表单一形状的非交叉矩形 . 所有矩形边都是垂直或水平的 . 有些矩形是相邻的，有些是不相交的 . 通过从单个其他矩形中剪切出类似定向的矩形来导出该集合 . 如何找到离新形状边缘最远的所有点？
最远，我指的是给定连接多边形 P 内的一个点 A （所以我们忽略所有不包含 A 的不相交多边形;给定非交叉点只会有一个）这样在 P 内没有点 B 其中最小距离从 B 到 P 边缘上的任何点都大于与 A 相同的最小距离 .
这就是我认为我必须做的事情：
-
组相邻的矩形 .
-
将多个相邻的矩形转换为单个不规则多边形，该多边形可以是凸面或凹面，也可以包含孔，但只有正交边 . 问题：如何表示漏洞？是否应移除孔（3）？如何在保持边缘正交的同时去除孔洞？
-
可能更容易并行执行步骤1和2 .
-
对于每个多边形，应用一种算法，该算法返回距该多边形边缘最远的点以及最小距离 .
-
问题：如何测试点是否在多边形内？
-
过滤所有具有最小距离的点;结果就是这些 .
假设这是正确的，最好的算法是什么（3），它如何影响答案的其余部分？只有垂直或水平边缘才能简化问题？
最好的，我的意思是最简单或最快 .
插图：
编辑v1：
所以我用google搜索了这个问题，找到了几种方法
算法
- Voronoi Diagram - > Medial Axis
线段（而不是点）的voronoi图由中间轴段（线或抛物线弧）和从多边形的每个顶点到中轴的顶点的（反射）线组成 . 有关voronoi图，中轴和最大内切圆问题之间关系的概述，请参见this stackoverflow answer (#2) . 另见下文 .
- 使用"A Sweepline Algorithm for Voronoi Diagrams"，
O[n*log(n)].
无论孔洞如何，都可以使用凸面或凹面多边形 . 构造多边形边缘的voronoi图 . 不幸的是会产生一组无序的线段（线或抛物线） . 在确定最大内切圆之前，将集合组织成图形结构 . 有关fortune算法的详细概述，请参阅"Voronoi Diagrams and a Day at the Beach" .
适用于没有孔的简单多边形（凸面或凹面） . 它看起来很复杂，所以我决定跳过这个 .
仅适用于凸多边形，因此不适用于我的问题 . 有关更多信息，请参见this stackoverflow answer (#1) .
- Straight Skeleton - > Medial axis
对于凸多边形，voronoi图和直骨架是相同的 . 因此，这些解决方案不适用于我的问题 .
-
使用"STALGO"，
O[n*log(n)]. 有关更多信息，请参见this stackoverflow answer (#1) . -
蛮力，
O(n^4). 见this stackoverflow answer (#3)和this stackoverflow answer (#2) . -
对于所有可能的三向组合（顺序没有't matter) of polygon' s边和顶点：
-
构造每组的最大内切圆，即找到与所有三个中心点等距的中心点 .
-
如果中心位于多边形外，则放弃结果 .
-
如果任何其他边或顶点在圆内（或相交），则丢弃结果 .
-
按圆半径排序;返回最大的圈子 .
-
Delaunay三角测量 - > Voronoi图 - >内侧轴
应该可以从delaunay三角测量转换为voronoi图...但我还没有研究过边缘的voronoi图 . 如果几何库仅提供delaunay三角剖分，则此方法可能很有用 .
Voronoi图和最大内切圆
我看到的每个资源都声称最大内切圆触及多边形的三个面（顶点或边），因此最大圆的中心必须是中轴上的顶点 . 但这仅代表最大内切圆的子集 . 考虑矩形的中轴：
沿着中轴的水平段具有中心的任何圆都是有效的最大内切圆 . 因此，如果中间轴段分隔两个最近的相邻单元，并且这些单元的相应多边形段是平行的，则整个中间轴边缘代表单个点而不是单个点，表示最大内切圆的集合 .
直观地说，考虑到多边形边缘与最近邻居单元的可能组合，我认为这是如何工作的：
-
line，line，parallel：中轴是一条线，代表一组可能的最大内切圆 .
-
line，line，not parallel：中轴是一条线 . 像往常一样，该线的 endpoints 必须至少有两条反射线连接回多边形 . 可能的最大内切圆以具有最长反射线的 endpoints 为中心 .
-
line，point：中轴是抛物线 . 如上所述，使用反射线来确定可能的最大内切圆的中心 . （*）
-
点，点：与上述相同 . （*）
最后两个不确定
这就是上面详述的蛮力方法不完整的原因 .
正交多边形
尽管存在正交约束，但我无法找到任何更简单的算法来构建中轴 . 一篇论文使用这种约束来为中轴提供更稳定的替代方案："Skeletal representations of orthogonal shapes" .
编辑v2：
我想知道是否有可能使this stackoverflow approach - 基于"Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth" - 适应我的输入（绿色）矩形（而不是正方形），同时保证绝对最大内切圆 .