包含原始详细多边形的简化(或平滑)多边形

Question

我有一个详细的2D多边形(代表一个地理区域),它由一组非常大的顶点定义.我正在寻找一种算法,它将简化和平滑多边形(减少顶点的数量),其约束条件是生成的多边形的区域必须包含详细多边形的所有顶点.

对于上下文,这是一个复杂多边形边缘的示例:

我的研究:

• 我找到了Ramer-Douglas-Peucker算法,它将减少顶点的数量 - 但生成的多边形将不包含所有原始多边形的顶点.请参阅维基百科上的这篇文章Ramer-Douglas-Peucker

• 我考虑过扩展多边形(我相信这也称为向外多边形偏移).我发现了以下问题:扩展多边形(仅凸面)和膨胀多边形.但我不认为这会大大减少我的多边形的细节.

感谢您给我的任何建议!

Answer 1

编辑

截至2013年,以下大多数链接不再起作用.但是,我发现引用的论文,包括算法,仍然可以在这个(非常慢)服务器上使用.

在这里,您可以找到一个完全处理您的问题的项目.虽然它主要用于由点"填充"的区域,但您可以将其设置为与您的"周边"类型定义一起使用.

它使用k近邻方法来计算区域.

样品:

在这里,您可以索取该文件的副本.

看起来他们计划提供一个在线服务来请求计算,但我没有测试它,可能它没有运行.

HTH!

Answer 2

这是一个有趣的问题！我从来没有尝试过这样的事情，但这是我的一个想法...如果它没有意义或不起作用:)

1. 计算凸包，这可能太大/不精确
2. 将船体分为 N 片，例如将船体的每个顶点连接到中心
3. 计算对象与每个切片的交集
4. 对每个交叉点递归重复（计算交叉点的外壳等）

每个递归级别都应该给出更好的近似值......当您达到令人满意的级别时，合并该级别的所有外壳以获得最终的多边形。

这听起来像是可以完成这项工作吗？