包含原始详细多边形的简化(或平滑)多边形 [英] Simplified (or smooth) polygons that contain the original detailed polygon

问题描述

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

关于上下文，这里是一个复杂多边形的边的示例:

我的研究:

• 我发现 Ramer–Douglas–Peucker 算法可以减少顶点的数量 - 但生成的多边形不会包含原始多边形的所有顶点.请参阅这篇文章

  这里 您可以索取论文的副本.

  似乎他们计划提供在线服务 用于请求计算，但我没有测试它，可能它没有运行.

  HTH！

  I have a detailed 2D polygon (representing a geographic area) that is defined by a very large set of vertices. I'm looking for an algorithm that will simplify and smooth the polygon, (reducing the number of vertices) with the constraint that the area of the resulting polygon must contain all the vertices of the detailed polygon.

  For context, here's an example of the edge of one complex polygon:

  My research:

  • I found the Ramer–Douglas–Peucker algorithm which will reduce the number of vertices - but the resulting polygon will not contain all of the original polygon's vertices. See this article Ramer-Douglas-Peucker on Wikipedia

  • I considered expanding the polygon (I believe this is also known as outward polygon offsetting). I found these questions: Expanding a polygon (convex only) and Inflating a polygon. But I don't think this will substantially reduce the detail of my polygon.

  Thanks for any advice you can give me!

  解决方案

  Edit

  As of 2013, most links below are not functional anymore. However, I've found the cited paper, algorithm included, still available at this (very slow) server.

  ---

  Here you can find a project dealing exactly with your issues. Although it works primarily with an area "filled" by points, you can set it to work with a "perimeter" type definition as yours.

  It uses a k-nearest neighbors approach for calculating the region.

  Samples:

  Here you can request a copy of the paper.

  Seemingly they planned to offer an online service for requesting calculations, but I didn't test it, and probably it isn't running.

  HTH!

  这篇关于包含原始详细多边形的简化(或平滑)多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！