正交船体算法

Question

我试图找到一种方法来确定从一组整数关口的rectilinear polygon（由红点在下面的图片所示）。下面的图片是我想达到的目标：

1.

我只需要最少的一组定义直线多边形的边界点。大部分船体的算法，我可以找到不满足这个问题的性质正交，如gift-wrapping algorithm，其产生如下结果（这是不我想要的）......

2.

如何获得定义图像中所示边界的点集1.？

更新时间：

图1.不再吹罚为凸..

Answer 1

继definition from wikipedia，这是相当容易地创建一个快速算法。

1. 开始构建从最左边的点（最上面之间例如，如果有许多）上船体。将此点添加到列表中。
2. 查找下一个点：所有与点之间的两个坐标严格大于当前点时，选择具有最小X坐标。将此点添加到您的列表并继续。
3. 只要可以，继续在第2步中添加点。
4. 从最右边的点（最上面的点）重复相同的操作，但是向左。即每次选择大于y，小于x的下一个点，而x的差值必须最小。
5. 合并你从步骤3和步骤4得到的两个列表，你得到了上面的船体。
6. 对于较低的船体类似地执行相同的步骤1-5。
7. 通过X协调合并在步骤5发现和上下船体6.

为了尽快找到下一个点，只是有点贵点。例如，在构建第一个正确链时，按x增加排序。然后遍历所有点。对于每个点，检查其坐标是否大于当前值。如果是，则将该点添加到列表中并使其为最新。

总体复杂性将是O（N日志N）排序。

编辑：上面的描述只显示如何跟踪船体的主要顶点。如果你想要一个完整的直线多边形（连续点之间有线段），那么每次找到下一个点时，你都必须在链上增加一个点。例如，从当前点建设时，右 - 上链，如果你找到一个点（x2，y2）（X1，Y1），你必须添加（X2，Y1）和（X2 ，y2）添加到当前链表（按此顺序）。

Answer 2

我不知道任何标准算法此，但它似乎并没有太复杂的定义：

假设每个点在网格中至少有2个邻居（或者没有解决方案）

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

2. 虽然p不为空

   2a。 Mark p as visited

   2b。 next =拥有最少邻居数量的未标记邻居

   2c。 next.parent = p

   2d。 P =未来

做

Answer 3

我认为，要计算什么是点的集合的直线凸包（或正交凸包）。直线凸包是一个正凸形状，也就是说，形状与任何水平线或垂直线的交点会产生空集，点或线段。

直线凸包的顶点是矢量优势下的最大点集合。然后可以在最佳O（n log n）时间内计算直线凸包。在计算几何中的Preparata's book中提供了一个非常简单的算法（请参阅4.1.3节）。