1

我试图找到一种方法来从一组整数点（由下图中的红点表示）确定直线多边形。下图显示了我想要实现的目标：

1.

在此处输入图像描述

我只需要定义直线多边形边界的最小点集。我能找到的大多数船体算法都不满足这个问题的正交性质，例如礼物包装算法，它产生以下结果（这不是我想要的）......

2.

在此处输入图像描述

如何获得定义图1中显示的边界的点集。 ？

更新：

图 1. 不再被称为凸..

4

3 回答 3

2

根据wikipedia 的定义，创建快速算法相当容易。

  1. 从最左边的点开始建造上层船体（如果有很多，最上面的点）。将此点添加到列表中。
  2. 寻找下一点：在所有坐标都严格大于当前点的点中，选择x坐标最小的点。将此点添加到您的列表中并继续。
  3. 尽可能在第 2 步中继续添加点。
  4. 从最右边的点（其中最上面的点）重复相同的操作，但向左移动。即每次选择y较大、 x较小的下一个点，并且x的差异必须最小。
  5. 合并您从第 3 步和第 4 步获得的两个列表，您就得到了上层船体。
  6. 类似地对下部船体执行相同的步骤 1-5。
  7. 合并在第 5 步和第 6 步中找到的上下船体。

为了快速找到下一个点，只需按x坐标对点进行排序。例如，在构建第一个右上链时，您按x递增排序。然后遍历所有点。对于每个点，检查其y坐标是否大于当前值。如果是，则将该点添加到列表中并将其设为最新。

排序的总体复杂度为O(N log N)。

编辑：上面的描述只显示了如何跟踪船体的主要顶点。如果您想要一个完整的直线多边形（在连续点之间有线段），那么每次找到下一个点时都必须在链中添加一个额外的点。例如，在构建右上链时，如果从当前点(x1, y1)中找到一个点(x2, y2)，则必须将(x2, y1)和(x2, y2)添加到当前链中列表（按此顺序）。

于 2015-09-10T08:51:16.383 回答
2

我认为您要计算的是点集的 Rectilinear Convex Hull（或 Orthogonal Convex Hull）。直线凸包是一种正交凸的形状，即该形状与任何水平或垂直线相交会产生一个空集、一个点或一条线段。

直线凸包的顶点是向量支配下的最大点的集合。然后可以在最佳 O(n log n) 时间内计算直线凸包。Preparata 关于计算几何的书中介绍了一个非常简单的算法（参见第 4.1.3 节）。

于 2017-10-16T23:57:59.853 回答
0

我不知道任何标准算法，但定义起来似乎并不复杂：

假设网格中的每个点至少有 2 个邻居（否则没有解决方案）

  1. p = 只有两个邻居的点。

  2. 而 p 不为空

    2a。将 p 标记为已访问

    2b。next = 具有最少邻居的未标记邻居

    2c。next.parent = p

    2d。p = 下一个

完毕

于 2015-09-10T08:51:18.647 回答