如何对二维多边形进行二次采样？
我有定义英国各县轮廓的多边形。这些形状非常详细（每个形状有 10k 到 20k 个点），因此相关计算（X 点在多边形 P 中吗？）的计算量相当大。
因此，我想对我的多边形进行“子采样”，以获得类似的形状但点数更少。有哪些不同的技术可以做到这一点？
最简单的方法是每 N 点取一个（因此按因子 N 进行子采样），但这感觉太“粗糙”。我宁愿做一些点的平均，或者类似的事情。有什么指针吗？
I have polygons that define the contour of counties in the UK. These shapes are very detailed (10k to 20k points each), thus rendering the related computations (is point X in polygon P?) quite computationaly expensive.
Thus, I would like to "subsample" my polygons, to obtain a similar shape but with less points. What are the different techniques to do so?
The trivial one would be to take one every N points (thus subsampling by a factor N), but this feels too "crude". I would rather do some averaging of points, or something of that flavor. Any pointer?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我想到了两个解决方案：
1）由于英国的地图相当方形，您可以选择渲染带有县的位图。为每个颜色分配特定的颜色，然后使用 1 或 2 像素粗的黑线渲染边框。这意味着如果样本恰好位于边界上，您只需执行昂贵的内部/外部计算。位图越大，这种情况发生的频率就越低。
2）简化县域轮廓。您可以使用递归Ramer–Douglas–Peucker 递归简化边界的算法。只要确保缓存结果即可。您可能还必须解决这个问题，不是针对整个县边界，而是仅针对共享边界，以确保没有间隙。这可能非常棘手。
Two solutions spring to mind:
1) since the map of the UK is reasonably squarish, you could choose to render a bitmap with the counties. Assign each a specific colour, and then render the borders with a 1 or 2 pixel thick black line. This means you'll only have to perform the expensive interior/exterior calculation if a sample happens to lie on the border. The larger the bitmap, the less often this will happen.
2) simplify the county outlines. You can use a recursive Ramer–Douglas–Peucker algorithm to recursively simplify the boundaries. Just make sure you cache the results. You may also have to solve this not for entire county boundaries but for shared boundaries only, to ensure no gaps. This might be quite tricky.
在这里你可以找到一个完全处理你的问题。尽管它主要适用于由点“填充”的区域，但您可以将其设置为适用于您的“周界”类型定义。
它使用 k 最近邻方法来计算区域。
示例：
在这里您可以索取论文副本。
看来他们计划提供在线服务请求计算，但我没有测试它，可能它没有运行。
哈！
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!
多边形三角测量在这里应该有所帮助。您仍然需要检查许多多边形，但现在这些是三角形，因此它们更容易检查，并且您可以使用一些优化来确定仅一小部分多边形子集来检查给定区域或点。
看来您拥有多边形所需的所有算法，不仅适用于三角形，您还可以合并三角测量后太小的几个三角形或三角形计数太高的三角形。
Polygon triangulation should help here. You'll still have to check many polygons, but these are triangles now, so they are easier to check and you can use some optimizations to determine only a small subset of polygons to check for a given region or point.
As it seems you have all the algorithms you need for polygons, not only for triangles, you can also merge several triangles that are too small after triangulation or if triangle count gets too high.