algorithm - 从点数组创建绑定多边形

Question

我有一个用户用画笔在上面绘制的画布。我有大量的积分。我想创建一个绑定多边形（不是绑定矩形）

有人会指出我现有的算法或帮助我编写代码（不要介意编程语言）。

Answer 1

如果您关心性能而不关心多边形的大小，那么可能保持所有坐标的最小值和最大值并使用它来构造一个绑定矩形将是最快的方法，它只需要O(n).

如果您关心多边形的大小或形状，那么您可能需要其中一种Convex Hull 算法，它通常在其中运行O(nlogn)但会产生一个紧凑的多边形。

Answer 2

如果您需要一个具有来自输入点的顶点的多边形，那么您正在寻找我在此处描述的凸包。