我有定义英国县边缘的多边形。这些形状非常详细（每个形状有10k到20k个点），因此相关计算（点X在多边形P中吗？）非常耗费计算资源。因此，我想要“子采样”我的多边形，以获得类似的形状但更少的点数。有哪些不同的技术可以做到这一点？其中一个平凡的方法是每隔N个点取一个点（因此通过因子N进行子采样），但这感觉太“粗糙”了。我宁愿对点进行一些平均或类似的处理。有什么指针吗？
3个回答
5
有两种解决方案：
1）由于英国地图比较方正，您可以选择渲染带有县的位图。为每个县分配特定颜色，然后用1或2像素厚的黑线渲染边界。这意味着只有在样本恰好位于边界上时才需要执行昂贵的内部/外部计算。位图越大，这种情况发生的频率就越低。
2）简化县的轮廓。您可以使用递归Ramer–Douglas–Peucker算法递归地简化边界。只要确保缓存结果。您还可能需要仅针对共享边界而不是整个县边界来解决此问题，以确保没有间隙。这可能会很棘手。
- David Rutten
2
好主意！对于这些间隙，我的初始数据已经存在不同多边形之间的重叠，所以我想这不会是一个问题。 - Wookai
请访问psimpl.sf.net获取C++库，该库提供了多个简化算法的实现，包括道格拉斯-普克算法。 - Elmar de Koning
2
多边形三角剖分 可以帮助解决这个问题。虽然你仍需要检查许多多边形，但现在它们已经变成了三角形，因此更容易检查，并且你可以使用一些优化方法来确定只需检查给定区域或点的一小部分多边形。
似乎你已经拥有了所有需要用于多边形的算法，不仅限于三角形，所以在三角剖分之后，如果三角形数量过多或者过小，你也可以合并几个三角形。
- schnaader
2
好的，用于检查点是否在多边形内的函数不是我自己写的（我使用内置的MySQL空间函数），所以我无法真正影响它。但还是谢谢你提供这个信息！ - Wookai
即使你不能改变这些函数，如果使用更简单的多边形，它们仍然应该更快。@Wookai - schnaader
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接