时间戳

首页 > 解决方案 > 具有正交边的多边形内的最远点（凸面或凹面或有孔）

algorithm - 具有正交边的多边形内的最远点（凸面或凹面或有孔）

问题描述

我有一组表示单个形状的非相交矩形。所有矩形边要么是垂直的，要么是水平的。有些矩形是相邻的，有些是不相交的。该集合是通过从一个其他矩形中裁剪出类似方向的矩形而得出的。如何找到距离新形状边缘最远的所有点？

最远，我的意思是A给定连接多边形内的一个点P（因此我们忽略所有不包含 的不相交的多边形A；给定不相交的情况下只有一个），因此在从到任何点的最小距离B内没有点的边大于与 相同的最小距离。PBPA

这就是我认为我必须做的：

  1. 对相邻的矩形进行分组。

  2. 将多个相邻矩形转换为单个不规则多边形，该多边形可以是凸面的，也可以是凹面的，并且可能包含孔，但只有正交边。问题：如何表示孔？(3) 的孔是否应该被移除？如何在保持边缘正交的同时去除孔洞？

    • 并行执行步骤 1 和 2 可能更容易。

  3. 对于每个多边形，应用一种算法，返回距该多边形边缘最远的点以及最小距离。

  4. 过滤所有具有最大最小距离的点；这些就是结果。

假设这是正确的，什么是最好的算法（3），它如何影响答案的其余部分？问题是否通过仅具有垂直或水平边缘来简化？

最好，我的意思是最简单或最快的。

插图：

最远点示例

编辑 v1：

所以我用谷歌戳了这个问题，找到了几种方法

算法

  1. Voronoi 图 -> 中轴

    线段（而不是点）的 voronoi 图由中轴段（线或抛物线弧）和从多边形的每个顶点到中轴顶点的（反射）线组成。有关voronoi 图、中轴和最大内切圆问题之间关系的概述，请参阅此 stackoverflow 答案 (#2) 。另见下文。

    1. 使用“Voronoi 图的扫描线算法”，O[n*log(n)].

      无论孔如何，都适用于凸多边形或凹多边形。构造多边形边缘的 voronoi 图。不幸的是，会产生一组无序的线段（线或抛物线）。在确定最大内切圆之前将集合组织成图形结构。请参阅“Voronoi 图表和海滩上的一天”，以获得对 fortune 算法的一个很好的概述。

    2. 使用“在线性时间内找到简单多边形的中轴”，O(n)。

      适用于没有孔的简单多边形（凸面或凹面）。它看起来很复杂，所以我决定跳过这个。

    3. 使用“用于计算凸多边形的 Voronoi 图的线性时间算法”，O(n)。

      仅适用于凸多边形，因此不适用于我的问题。有关更多信息，请参阅此 stackoverflow 答案（#1）。

  2. 直骨架 -> 中轴

    对于凸多边形，voronoi 图和直骨架是一样的。因此，这些解决方案不适用于我的问题。

    1. 使用“STALGOO[n*log(n)] ” ，。有关更多信息，请参阅此 stackoverflow 答案（#1）。

  3. 蛮力，O(n^4)。请参阅此 stackoverflow 答案 (#3)和此 stackoverflow 答案 (#2)。

    1. 对于多边形的边和顶点的所有可能的三向组合（顺序无关紧要） ：

    2. 为每组构造最大的内切圆，即找到与所有三个等距的中心点。

    3. 如果中心位于多边形之外，则丢弃结果。

    4. 如果任何其他边或顶点在圆内（或相交），则丢弃结果。

    5. 按圆半径排序；返回最大的圆圈。

  4. Delaunay 三角剖分 -> Voronoi 图 -> 中轴

    应该可以从 delaunay 三角剖分转换为 voronoi 图……但我还没有研究过边缘的 voronoi 图。如果您的几何库仅提供 delaunay 三角剖分，此方法可能很有用。

Voronoi 图和最大内切圆

我见过的每个资源都声称最大内切圆接触多边形的三个面（顶点或边），因此最大圆的中心必须是中轴上的一个顶点。但这仅代表最大内切圆的一个子集。考虑一个矩形的中轴：

矩形的中轴

任何以中轴水平段为圆心的圆都是有效的最大内切圆。因此，如果中轴段将两个最近的相邻单元格分开，并且这些单元格的相应多边形段是平行的，则整个中轴边缘表示最大内切圆的集合，而不是单个点。

直观地说，我认为这是它的工作原理，考虑到多边形边缘到最近邻单元的可能组合：

这就是为什么上面详述的蛮力方法是不完整的。

正交多边形

尽管有正交约束，我还是找不到任何更简单的算法来构建中轴。一篇论文使用此约束为中轴提供更稳定的替代方案：“正交形状的骨架表示”。

编辑 v2：

我想知道是否有可能在保证绝对最大内切圆的同时，将这种基于“不可访问极点：地球上最偏远地区的计算算法”的stackoverflow 方法调整到我的输入（绿色）矩形（而不是正方形）。

标签： algorithmgeometrypolygoncomputational-geometry

解决方案

推荐阅读