algorithm - 按条件进行多边形平滑

Question

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

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

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

我需要做这样的事情:

Answer 1

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

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

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

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