algorithm - 识别二维多边形的最相关顶点

Question

我一直在研究一种识别二维多边形“最相关”顶点的已知算法。我可能使用了错误的关键字（我一直在尝试搜索网格简化算法），但我还没有发现任何有用的东西。

我应该用一些上下文来定义我所说的“最相关”的顶点。我想采用 2D 多边形，应用几何变换，并使用顶点之间的映射来渲染变换前和变换后的多边形，以可视化变换的效果。但是，对于小的高度详细的多边形（每个区域的顶点数很高），会有很多“视觉混乱”。

这个想法是应该有一种算法可以识别哪些顶点适合映射，哪些不适合。我可以通过考虑两件事来设计这样的算法：

1. 边长：如果顶点与前一个顶点之间的长度小于阈值，则忽略该顶点。需要一个累加器来避免忽略多个后续顶点。
2. 内角：如果顶点的内角高于阈值，则忽略该顶点。需要一个“累加器”以避免忽略多个后续顶点。

尽管可能能够实现这样的事情，但我不喜欢重新发明轮子，并决定问你是否遇到过这样的事情，它实际上可以解决我没有想到的其他问题（例如，复杂的多边形）。

标签： algorithmpolygon

Answer 1

听起来您正在寻找Ramer-Douglas-Peucker算法，它可以“简化路径”，但可以扩展以用于多边形。它的工作原理是只从几个端点开始，然后贪婪地添加任何必要的顶点，以将原始形状逼近到一定的公差范围内。还有许多其他算法和启发式算法，但没有一个以可靠地产生比 RDP 更好的结果而闻名，而且 RDP 易于理解和实现。