c++ - 简化路径的算法

Question

给定一条路径，我想对其进行优化，以便可以删除直线上的所有顶点。

例如： 路径：

*******
*      *
*        *
***********

可以优化为：

*-----*
|      \
|        \
*---------*

但是我想控制与斜率的偏差，这样它就不必完全在斜率上。

什么样的算法可以做到这一点？

谢谢

Answer 1

我相信您可以通过简单的迭代遍历路径上的点来做到这一点。在每个点上跟踪您遇到的最后三个点。如果它们三个都是共线的，则从路径中删除中间点，因为从第一个节点到第三个节点的直线路径将通过中间节点。您可以通过使用一些术语来控制点必须接近共线的程度来控制偏差的大小。

如果您将点存储在双向链表之类的数据结构中，则可以通过简单的数据传递在 O(n) 时间内实现。

希望这可以帮助！

Answer 2

这将是一个抽象的观点，因为我不是一个 C++ 人，但是这里有......

现在让我们来看一个点：

*******
*      *
*        *<- this one, lets call it X
***********

你要做的是慢慢决定每个点是否是必要的。要确定一个点是否有效，必须使用其他点，即之前和之后的点：

*******
*      *<- A
*        *
***********<- B

如果从 A 到 X 的角度与从 X 到 B 的角度相同（或在您认为足够准确的误差范围内），则不需要 X。

这不会产生与 Convex Hull 算法相同的结果。这只会降低路径的分辨率。如果您允许的错误太大，您可能会受到副作用，例如：

     *        *
    *         |
   *          |
    *    ->   |
     *        |
    *         |
   *          *

或者如果你的错误太小，你可能根本不会改变路径。

另请注意，凸包可以极大地改变路径，例如：

  *   *            *---*
 * * * *          /     \
*   *   *   ->   *       *
*       *        |       |
*********        *-------*

Answer 3

您应该使用凸包算法（这取决于您的多边形在内存中的存储方式），然后在两个相邻点上以最小角度清理这些点。然后你会有一个多边形，只有末端的点。

这是： http ://en.wikipedia.org/wiki/Convex_hull

它们有很多可能的实现。这取决于您使用的编程语言以及您使用的数据。

编辑：我当时不知道您已经拥有数据中的点。只需遍历这些点并计算您所在位置、上一个和下一个之间的角度。如果角度为 ~= 180，则删除当前点。

Answer 4

set `D` to a maximum deviance of 10 degrees or so.  
set `P` to the first point.
set `Q` to the point after `P`. 
set `A` to the angle from `P` to `Q`.
while `Q` is not that last point in the list
    if the angle from `P` to `Q` is within of `A` plus or minus `D`
        remove `Q`
    else
        set `P` to `Q`
        set `A` to the angle from `P` to `Q`.
    set `Q` to the point after `P`

这比 templatetypedef 的答案稍微复杂一些，但它的优点是它可以更好地拟合大曲线。

Answer 5

更复杂的解决方案将涉及图像处理技术。您可以尝试允许偏差的霍夫变换。可以通过“模糊”参数空间来包含偏差。然而算法并不简单。当每条线上的点数非常不同时，我也不知道它处理大量线的能力如何。由于您的点是有序的，您可以尝试查看参数空间并删除所有产生匹配的点。如果您首先选择最佳匹配，您可能会得到一个很好的解决方案。

Answer 6

我已经在 中实现了@templatetypedef 的解决方案C++，用于由两个x,y向量描述的闭合多边形链。我遍历多边形，如果一个点与前一个点和下一个点共线，我将其删除：

template<class T> void del_collinear_vanilla(std::vector<T> &x,
        std::vector<T> &y) {
    assert(x.size() == y.size());
    size_t i = x.size();
    size_t im1, ip1 = 0;
    do {
        i--;
        im1 = i ? i - 1 : x.size() - 1;
        if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
            x.erase(x.begin() + i);
            y.erase(y.begin() + i);
        }
        ip1 = i;
    } while (i != 0);
}

其中实现取决于宏/模板are_collinear(x0,y0,x1,y1,x2,y2)。

但是，在某些情况下，输出中仍然有一些共线点。这是算法失败的示例输入：

本例中，P5 与 P0 重合，P4 与 P0 和 P1 的纵坐标相同；我改变了一点他们的坐标来显示所有的段。该算法应该只返回一个顶点为 P1、P2、P3、P4 的矩形。

上图，P6 与 P5 和 P0 共线。那么，一旦 P6 被淘汰，P5 和 P0 就重合了，它们都与 P4 和 P1 共线。

事实证明，在每个点上进行简单循环，如果它与前一个点和下一个点共线，则删除一个点，并不能提供正确的结果。

（在这个例子中，假设你从 P0 开始，你发现它与 P6 之前的点和 P1 之后的点不共线。然后你移动到 P1，P2，......直到你到达 P6。P6 共线，你删除它，循环结束。但是现在P0与P4和P1共线，它应该被删除了！）

开放路径也存在同样的缺陷。只要输入路径在某种程度上没有崩溃，该算法就可以正常工作。

解决方案是每次删除一个点时后退一步，以验证前一个点现在是否共线：

template<class T> void del_collinear(std::vector<T> &x, std::vector<T> &y) {
    assert(x.size() == y.size());
    size_t target = x.size() - 1;
    size_t i = x.size() - 1;
    do {
        size_t im1 = i ? i - 1 : x.size() - 1;
        size_t ip1 = (i == x.size() - 1) ? 0 : i + 1;
        if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) {
            x.erase(x.begin() + i);
            y.erase(y.begin() + i);
            // I do not decrease i in this case, as the the previous (alread
            // processed) point may now be a collinear point that must be
            // deleted. I mod it because i may now exceed x.size()
            i = i % x.size();
            //Increment the target as well.
            target = (i + 1 + x.size()) % x.size();
        } else
            //go for the next point.
            i = i ? i - 1 : x.size() - 1;
    } while (i != target);
}

Answer 7

我认为这个页面应该可以帮助你：Simplyfing Polygons（我也推荐这本书）。