多边形偏移算法

在本教程中，我们将描述一种膨胀或收缩多边形的算法。

1、一般形式的同调

为了简单起见，让我们从一个形状开始，一个正方形。我们可能熟悉通过放大或缩小形状来缩放形状的想法。从技术上讲，这个想法被称为空间的拟似变换（homothetic transformation）或齐次膨胀（homogeneous dilation）：

我们从由一组 n 个顶点 v定义的任何多边形开始：

然后，我们确定一个点 S = (s_x, s_y)，我们将其称为如下相似性的中心：

选择相似比 lambda（任何实数）后，我们可以计算变换后的多边形中相应的新顶点 v'=H(v) ，如下所示：

如果我们知道顶点的坐标 v = (v_x, v_y)，则其对应的相似变换图像可以计算为：

在相似中心坐标为 (S_x, S_y) = (0,0) 的特殊情况下，相似度相对于原点发生。这显着简化了变换多边形的图像的计算。因此，前面的公式简化为：

这种特殊类型的相似变换被称为均匀缩放（uniform scaling）。在这种情况下，因子 lambda 假定为变换的缩放因子的名称。

一个相关的问题是涉及形状或多边形的偏移（Offset）的问题。在某些情况下，我们可能想要假设地变换多边形，但也对结果形状施加额外的约束。例如，我们可能希望满足添加的约束，即新形状周界中的所有点与原始形状周界中最接近的点等距：

例如，如果原始形状是圆形，并且我们围绕其中心缩放它，则相似变换遵循此规则。

但请注意，相似性通常不满足此约束。这是因为变换后的多边形中的每个角点或顶点实际上通常比变换后的形状中的任何其他点距其反转图像更远。

满足限制条件的变换被称为多边形偏移（Polygon offsetting），在地理空间分析中也称为多边形缓冲（Polygon buffering）。

为了偏移具有已知顶点的多边形，我们需要一种按顺序执行以下任务的算法。首先，我们获取每个顶点并复制它。然后，我们按顺时针顺序将每个新顶点与其前面的旧顶点连接起来。

这让我们可以定义可以彼此独立移动的段。选择任意长度 δ 后，我们将线段沿其轴移动该 δ 。

通过记住线段之间垂直度的定义，我们可以首先计算每个线段 AB 的斜率 m，如下：

垂直于该线段的直线都有一个斜率，该斜率是 m 的倒数的倒数。对于斜率为 m 的线段的每个顶点，新坐标 (Xnew, Ynew) 需要满足以下两个方程：

对于 m ≠ 0。这是两个未知数 ynew, xnew 的两个方程，我们可以求解它们来找到每个顶点的新坐标。

最后剩下的步骤包括将平移后的片段相互连接。这可以通过创建半径为 δ 的圆周弧来完成。每条弧都以每个原始顶点为中心，并限制在复制顶点的两个图像内。

该动画显示了膨胀的完整过程，从多边形的定义到最终形状：

请注意，此过程也适用于凹多边形：不过，我们需要注意检查所有偏移顶点是否位于变换后的多边形之外。如果没有，我们需要删除它们以及落在多边形内的所有线条。如果我们需要复习如何做到这一点，我们可以参考我们的地理围栏教程。

该过程也适用于缩小多边形。在这种情况下，我们需要反转平移片段的方向。这可以通过交换我们之前定义的 δ 因子的符号来完成。然后，我们再次删除所有落在新偏移多边形形状之外的点。

BimAnt翻译整理，转载请标明出处