computational-geometry - 在运行凸包算法之前进行修剪

Question

我必须从大量点形成一个凸包，我遇到了这篇文章。修剪的整个过程都被描述和很好地解释了，除了一个部分。

我不知道这部分是什么意思以及如何将其转换为代码：

由于空间是二维的，每个点都有两个坐标，x > 和 y。每次我们读取一个新点时，我们都会计算以下 4 个 > 点：

A = (Ax, Ay) 最大化 xy B = (Bx, Xy) 最大化 x+y C = (Cx, Cy) 最小化 xy D = (Dx, Dy) 最小化 x+y

谁能帮我计算点A、B、C、D？

标签： computational-geometryconvex-hullpruning

Answer 1

您不是在计算点数，而是从输入数据中选择它们：

• A是输入数据中的值x-y大于任何其他输入数据点的点。
• B是输入数据中的值x+y大于任何其他输入数据点的点。
• C是输入数据中的值x-y小于任何其他输入数据点的点。
• D是输入数据中的值x+y小于任何其他输入数据点的点。