使用 Boost Polygon 的减法结果不正确

Question

我有以下两个输入多边形，我想为其计算减去的多边形：

A：

               * (0, 8)
              / \
             /   \
            /     \
   (-3, 0) *-------* (3, 0)

乙：

      (-1, 2) *-----* (1, 2)
              |     |
      (-1, 1) *-----* (1, 1)

因此，我想计算A - B，这应该会产生一个带有方形切口的三角形。使用 Boost Polygon 计算此结果会导致带有切口的不正确的部分三角形。画起来很难；结果三角形的缺失部分由三角形 表示(3, 0) => (0, 8) => (1, 2)。我使用以下代码来计算减法：

               * (0, 8)
              / \
             /   \
            /     \
   (-3, 0) *-------* (3, 0)

这将打印构成剪切三角形的以下后续点：

(3, 0)
(1, 2)
(1, 1)
(-1, 1)
(-1, 2)
(1, 2)
(0, 8)
(-3, 0)
(3, 0)

因此，结果中缺少边缘(1, 2) => (3, 0)和。(3, 0) => (0, 8)结果中缺少输入三角形的右上部分。

正确的输出可能如下所示：

(3, 0)
(1, 2)
(1, 1)
(-1, 1)
(-1, 2)
(1, 2)
(3, 0)
(0, 8)
(-3, 0)
(3, 0)

这是 Boost Polygon 中的错误吗？我是否以某种方式错误地使用了该库，或者我还缺少其他内容吗？

一些附加信息：

• 我正在使用 GCC 7.2.0、Boost 1.60.0。此后 Boost Polygon 就没有更新过，因此升级 Boost 很可能不会有帮助。
• double使用代替参数化点类型和所有其他几何类型并int不能解决问题。
• 例如，使用轴对齐的矩形计算切口是没有问题的。
• 对于我的应用程序，我想使用 Boost Polygon 而不是 Boost Geometry，因为它提供多边形锁孔压裂支持。

Answer 1

回答我自己的问题...

Boost Polygon 是根据整数数据类型编写的。从文档中：

一般来说，数据类型应该定义 std::numeric_limits 并且类似于整数。浮点坐标类型并非所有算法都支持，目前通常不适合与库一起使用（http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/gtl_cooperative_concept.htm）

我怀疑这是某种我不完全理解的精度问题。事实上，将所有输入坐标缩放一个因子确实1000会产生正确的多边形：

(3000, 0)
(1000, 5333)
(1000, 2000)
(1000, 1000)
(-1000, 1000)
(-1000, 2000)
(1000, 2000)
(1000, 5333)
(0, 8000)
(-3000, 0)
(3000, 0)

因此，对于原始输入，锁孔断裂算法似乎旨在在边缘上添加一个新顶点，(3, 0) -> (0, 8)从该顶点进入“锁孔多边形”。它可以为此创建的整数网格位置上的最佳顶点位于 处(0, 8)。所以结果代表一个近似值。

事实上，为算法提供类似的输入（在三角形边上存在良好的候选顶点）确实会产生正确的输出。例如，一个这样的输入三角形是(-4, 0) - (4, 0) - (0, 8)。

我认为这是锁孔断裂算法的局限性。