algorithm - 减少封闭轮廓中点数的已知算法

Question

我有一个生成轮廓的库，作为坐标列表，如:

  [[464.5, 551. ],
   [464.5, 550. ],
   [464. , 549.5],
   [463.5, 549. ],
   [463. , 548.5],
   [462. , 548.5],
   [461. , 548.5],
   [460.5, 549. ],
   [460. , 549.5],
   [459. , 549.5],
   [458. , 549.5],
   [457. , 549.5],
   ...

坐标由直线连接，定义一个闭合的不规则不自相交的多边形。

从上面的示例中，我们可以看到可以删除一些点而不会丢失任何表面积，但我不在乎算法是否有一些损失，只要它是可配置的(比如面积与并集的交集) area > x, 或别的东西？)

是否有一些已知的算法可以减少闭合轮廓的点数？

PS:朴素的算法是测试点的所有子集，并取最小的子集，该子集高于可接受的损失。问题是我可能有数百个坐标，并且子集的数量是指数级的 (2^(coord_count))。即使计算损失也很昂贵:我需要计算 2 个多边形的交集和并集，然后计算它们的表面。

编辑:

• 删除对齐的连续点很容易，而且肯定是降低后续步骤时间复杂度的第一步。
• 我想要的是一个新的多边形，其表面覆盖率几乎相同，但坐标少得多:我什至不关心新多边形是否未使用原始多边形的任何坐标(但这看起来更复杂而不是删除原始多边形的一些点)。

Answer 1

我建议采用以下程序:

1. 对于每 3 个连续的点，检查连接两点任一侧的线是否与多边形相交。

1. 如果去掉中间点，计算“面积贡献”；如果它们是凸的，这将是负的；如果是凹的，则这将是正的。

1. 如果您想用最少的点数获得最佳结果，请始终在任何阶段删除最小化面积净变化的点。小心标志。

1. 重复此操作，直到下一个最佳净变化超过指定的容差。

---

• 在最坏的情况下，此算法的原始版本是 O(N^2)。您可以通过使用 BST/堆来跟踪与每个点对应的区域增量来对其进行一些优化，尽管更新可能很繁琐。用于交叉测试的四叉树也可能有用，尽管它会导致 O(N log N) 的设置惩罚，只有在删除大量点时才能取消。

  <

• Douglas-Peucker 并不总是产生最佳结果(在不超过面积差异阈值的情况下尽可能多地移除点)；原始算法也没有考虑自交。