algorithm - 如何对二维多边形进行二次采样？

Question

我有定义英国县轮廓的多边形。这些形状非常详细（每个 10k 到 20k 点），因此使相关的计算（多边形 P 中的点 X 吗？）计算成本很高。

因此，我想对我的多边形进行“二次采样”，以获得相似的形状但点数更少。有哪些不同的技术可以做到这一点？

最简单的方法是每N点取一个（因此按一个因子进行二次抽样N），但这感觉太“粗鲁”了。我宁愿做一些平均分，或者类似的东西。任何指针？

Answer 1

我想到了两个解决方案：

1）由于英国的地图相当方正，您可以选择渲染带有县的位图。为每个指定颜色，然后用 1 或 2 像素粗的黑线渲染边框。这意味着如果样本恰好位于边界上，您只需执行昂贵的内部/外部计算。位图越大，这种情况发生的频率就越低。

2）简化县域大纲。您可以使用递归Ramer–Douglas–Peucker算法递归地简化边界。只要确保你缓存结果。您可能还必须解决这个问题，而不是针对整个县边界，而是仅针对共享边界，以确保没有间隙。这可能相当棘手。

Answer 2

在这里，您可以找到一个完全解决您的问题的项目。虽然它主要适用于由点“填充”的区域，但您可以将其设置为与您的“周长”类型定义一起使用。

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

样品：

您可以在此处索取论文的副本。

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

！

Answer 3

多边形三角剖分在这里应该有所帮助。您仍然需要检查许多多边形，但这些现在是三角形，因此它们更易于检查，并且您可以使用一些优化来确定只有一小部分多边形来检查给定的区域或点。

看起来您拥有多边形所需的所有算法，不仅适用于三角形，您还可以合并几个在三角剖分后太小的三角形，或者如果三角形计数太高。