blocks|key|2203075|text|这是个有趣的问题！我从来没有尝试过这样的方法，但我有个主意.如果没有意义或不起作用，请道歉:)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2203076|计算一个凸包，这可能太大了/不精确。|ordered-list-item|2203077|将船体划分为N个切片，例如将每个船体的顶点连接到中心|2203078|计算对象与每个切片的交集。|2203079|对每个交叉口递归地重复(计算交叉口的船体等)|2203080|每个层次的递归应该给出一个更好的近似..。当您达到一个满意的水平，合并所有的船体从该级别，以得到最后的多边形。|2203081|听起来能胜任这份工作吗？|2203082|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|S|8|@]|9|@]|A|$]]|$1|G|3|H|5|D|7|T|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|U|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|V|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|W|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|X|8|@]|9|@]|A|$]]]|P|$]]

That's an interesting problem! I never tried anything like this, but here's an idea off the top of my head... apologies if it makes no sense or wouldn't work :)

<ol>
<li>Calculate a convex hull, that might be way too big / imprecise</li>
<li>Divide the hull into N slices, for example joining each one of the hull's vertices to the center</li>
<li>Calculate the intersection of your object with each slice</li>
<li>Repeat recursively for each intersection (calculating the intersection's hull, etc)</li>
</ol>

Each level of recursion should give a better approximation.... when you reached a satisfying level, merge all the hulls from that level to get the final polygon.

Does that sound like it could do the job?

blocks|key|2561970|text|编辑|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|2561971|截至2013年，下面的大多数链接都不再运行了。然而，我找到了引用的论文，包括算法，仍然可以在这个(非常慢)的服务器上使用。。|2561972|这里+--您可以找到一个处理问题的项目。虽然它主要用于按点“填充”的区域，但您可以将其设置为使用“外围”类型定义。|2561973|它使用k近邻方法来计算区域.|2561974|示例：|2561975|​|2561976|📷|atomic|2561977|2561978|这里你可以要求一份论文的副本。|2561979|他们似乎是因为请求计算而计划提供在线服务，但我没有测试它，而且很可能它没有运行。|2561980|哈哈！|2561981|entityMap|0|LINK|mutability|MUTABLE|url|http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf|1|http://ubicomp.algoritmi.uminho.pt/local/concavehull.html|2|IMAGE|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/35402285c46471d068db883b6bda59d2.png|imageAlt|3|http://repositorium.sdum.uminho.pt/request-item;jsessionid=94383BCD27BDF40B4AB3B5CF6A1788FB?handle=1822/6429&bitstream-id=25848|4|http://www.concavehull.com/home.php?main_menu=1^0|0|2|0|U|V|0|0|0|2|1|0|0|0|0|0|1|2|0|0|0|2|3|0|C|8|4|0|0^^$0|@$1|2|3|4|5|6|7|1J|8|@$9|1K|A|1L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1M|8|@]|D|@$9|1N|A|1O|1|1P]]|E|$]]|$1|H|3|I|5|6|7|1Q|8|@]|D|@$9|1R|A|1S|1|1T]]|E|$]]|$1|J|3|K|5|6|7|1U|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|1V|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|1W|8|@]|D|@]|E|$]]|$1|P|3|Q|5|R|7|1X|8|@]|D|@$9|1Y|A|1Z|1|20]]|E|$]]|$1|S|3|O|5|6|7|21|8|@]|D|@]|E|$]]|$1|T|3|U|5|6|7|22|8|@]|D|@$9|23|A|24|1|25]]|E|$]]|$1|V|3|W|5|6|7|26|8|@]|D|@$9|27|A|28|1|29]]|E|$]]|$1|X|3|Y|5|6|7|2A|8|@]|D|@]|E|$]]|$1|Z|3|-4|5|6|7|2B|8|@]|D|@]|E|$]]]|10|$11|$5|12|13|14|E|$15|16]]|17|$5|12|13|14|E|$15|18]]|19|$5|1A|13|1B|E|$1C|1D|1E|-4]]|1F|$5|12|13|14|E|$15|1G]]|1H|$5|12|13|14|E|$15|1I]]]]

Edit 

As of 2013, most links below are not functional anymore. However, I've found <a href="http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf" rel="noreferrer">the cited paper, algorithm included, still available at this (very slow) server</a>.

<hr>

<a href="http://ubicomp.algoritmi.uminho.pt/local/concavehull.html" rel="noreferrer">Here</a> 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: 

<a href="https://i.stack.imgur.com/kxRKk.png" rel="noreferrer"><img src="https://i.stack.imgur.com/kxRKk.png" alt="enter image description here"></a>

<a href="http://repositorium.sdum.uminho.pt/request-item;jsessionid=94383BCD27BDF40B4AB3B5CF6A1788FB?handle=1822/6429&amp;bitstream-id=25848" rel="noreferrer">Here</a> you can request a copy of the paper. 

Seemingly they <a href="http://www.concavehull.com/home.php?main_menu=1" rel="noreferrer">planned to offer an online service</a> for requesting calculations, but I didn't test it, and probably it isn't running.

HTH!

blocks|key|2203163|text|在某种程度上，我不知道你想做什么，但你似乎有两个非常好的答案。一种是Ramer+Peucker+(DP)，另一种是计算α形状(也称为凹壳、非凸壳等)。我发现了一篇描述阿尔法形状的最新论文，并将其链接在下面。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2203164|我个人认为用多边形展开的DP是可行的。我不知道你为什么认为它不会大大减少顶点的数量。有了DP，你就可以提供一个要素，你可以让它达到你想要的任何一个三角形，不管你的输入是什么。选择这个因素可能很难，但在你的情况下，我认为这是最好的方法。您应该能够根据您想要离开的最大细节的大小来确定因素。您可以通过直接测试或通过从源数据计算它来实现这一点。|2203165|http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf|offset|length|2203166|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|2F|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@$F|R|G|S|1|T]]|A|$]]|$1|H|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|E]]]]

To some degree I'm not sure what you are trying to do but it seems you have two very good answers. One is Ramer–Douglas–Peucker (DP) and the other is computing the alpha shape (also called a Concave Hull, non-convex hull, etc.). I found a more recent paper describing alpha shapes and linked it below.

I personally think DP with polygon expansion is the way to go. I'm not sure why you think it won't substantially reduce the number of vertices. With DP you supply a factor and you can make it anything you want to the point where you end up with a triangle no matter what your input. Picking this factor can be hard but in your case I think it's the best method. You should be able to determine the factor based on the size of the largest bit of detail you want to go away. You can do this with direct testing or by calculating it from your source data.

<a href="http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf" rel="nofollow">http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf</a>

blocks|key|2203179|text|我认为维斯瓦林加算法可以适应这一目的-通过跳过删除三角形，以减少面积。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2203180|entityMap|0|LINK|mutability|MUTABLE|url|http://bost.ocks.org/mike/simplify/^0|3|7|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I think <a href="http://bost.ocks.org/mike/simplify/" rel="nofollow">Visvalingam’s algorithm</a> can be adapted for this purpose - by skipping removal of triangles that would reduce the area.

blocks|key|2203204|text|我有一个非常相似的问题:我需要一个膨胀的多边形简化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2203205|我做了一个简单的算法，通过删除concav点(这将增加多边形大小)或删除凸边(两个凸点之间)和延长相邻边。在任何情况下，做这两种可能性中的一种将删除多边形上的一个点。|2203206|我选择移除导致最小面积变化的点或边缘。你可以重复这个过程，直到简化对你来说是可以的(例如，不超过200点)。|2203207|两个主要的困难是获得快速算法(避免计算顶点/边缘的变化两次并保持可能性排序)和避免在过程中插入自交点(不太容易做和解释可能，但计算复杂度有限)。|2203208|事实上，在仔细观察之后，这是一个类似的想法，维斯瓦林加与自适应的边缘去除。|2203209|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

I had a very similar problem : I needed an inflating simplification of polygons.

I did a simple algorithm, by removing concav point (this will increase the polygon size) or removing convex edge (between 2 convex points) and prolongating adjacent edges. In any case, doing one of those 2 possibilities will remove one point on the polygon.

I choosed to removed the point or the edge that leads to smallest area variation. You can repeat this process, until the simplification is ok for you (for example no more than 200 points). 

The 2 main difficulties were to obtain fast algorithm (by avoiding to compute vertex/edge removal variation twice and maintaining possibilities sorted) and to avoid inserting self-intersection in the process (not very easy to do and to explain but possible with limited computational complexity).

In fact, after looking more closely it is a similar idea than the one of Visvalingam with adaptation for edge removal.

blocks|key|2203239|text|我已经写了一个关于Douglas的简单修改，可能对将来有这个问题的任何人都有帮助：https://github.com/prakol16/rdp-expansion-only|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2203240|它和DP是一样的，只不过如果它要删除的点在多边形之外，它会将线段向外推一点。这保证了得到的简化多边形包含了所有的原始多边形，但它的线段数几乎与原始DP算法相同，并且通常能够很好地逼近原始形状。|2203241|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/prakol16/rdp-expansion-only^0|15|1A|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

I've written a simple modification of Douglas-Peucker that might be helpful to anyone having this problem in the future: <a href="https://github.com/prakol16/rdp-expansion-only" rel="nofollow noreferrer">https://github.com/prakol16/rdp-expansion-only</a>
It's identical to DP except that it pushes a line segment outwards a bit if the points that it would remove are outside the polygon. This guarantees that the resulting simplified polygon contains all the original polygon, but it has almost the same number of line segments as the original DP algorithm and is usually reasonably good at approximating the original shape.

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:

<img src="https://i.stack.imgur.com/gU9ok.png" alt="enter image description here">

My research:

<ul>
<li>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 <a href="http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm" rel="noreferrer" title="Ramer-Douglas-Peucker algorithm">Ramer-Douglas-Peucker on Wikipedia</a></li>
<li>I considered expanding the polygon (I believe this is also known as outward polygon offsetting). I found these questions: <a href="https://stackoverflow.com/questions/3749678/expand-fill-of-convex-polygon" title="Expanding a polygon">Expanding a polygon (convex only)</a> and <a href="https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons" title="Inflating a polygon">Inflating a polygon</a>. But I don't think this will substantially reduce the detail of my polygon.</li>
</ul>

Thanks for any advice you can give me!

Simplified (or smooth) polygons that contain the original detailed polygon

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一个详细的2D多边形(代表一个地理区域)，它是由一组非常大的顶点定义的。我正在寻找一种算法，将简化和平滑多边形，(减少顶点的数目)的约束，区域的结果多边形必须包含详细多边形的所有顶点。对于上下文，下面是一个复杂多边形边缘的示例：​​我的研究：我发现Ramer Peucker算法可以减少顶点的数量，但是得到的多边形不...

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

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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