正交船体算法

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

1.

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

2.

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

Updated:

图1.不再称为凸..

继维基百科的定义，创建快速算法相当容易。

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

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

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

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