algorithm - 按条件平滑多边形

Question

我有由点序列给出的多边形，我需要应用以下规则：

• 角度必须为 180、90、45 度；
• 如果线平行，则在大于 minValue 的线之间相距；
• 多边形的方向是水平和垂直的。

（如果最接近特定问题，那么我在 OpenCV 中找到对象的轮廓，那么它们应该很好画）

我需要做这样的事情：

Answer 1

我会使用 DP 点减少来解决这个问题。这个例程有几种不同的风格，最常见的并不是你想要做的最好的，但最终这种方法会产生最好的质量。

经典的 DP 操作采用形成折线的点数组，并删除不会破坏超出特定因素的形状的任何点。该因素是基于您的数据的度量单位，因此在您的情况下，它可能以像素为单位。正如您可以想象的那样，选择因子是使用 DP 最困难的部分，除非您只想从多边形中删除可以轻松量化的点并不重要。

在你的情况下，我花了很多时间，你想删除对多边形形状贡献最小的点。您应该能够采用 DP 的典型递归示例，并在第一次迭代通过点后使其中断，以便一次删除一个点。然后你会对你的形状进行评分，看看它是否符合你的要求。如果得分不完美，则删除另一分并重新得分，直到完成或只剩下三分。如果没有完美的分数，您可以采用得分最高的形状，并且可能有第二个算法来强制它满足要求。

http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Answer 2

你所问的似乎并不简单，也没有那么明确。需要更多上下文。

我会尝试两种方法：

• 在多边形上覆盖一个正方形网格，并保持足够填充的正方形。

• 骨架化形状（http://en.wikipedia.org/wiki/Topological_skeleton），清理并将骨架分成大部分水平/垂直的部分；然后用真正的水平/垂直笔划替换这些段。