计算两个多边形之间的9个交集矩阵
Calculate 9 Intersection Matrix between two polygons
问题
给定两个没有孔的非凸多边形，我想计算对应的9交矩阵
一个 9 交集矩阵的形式为：
| I | B | E
I | I ∩ I | I ∩ B | I ∩ E
B | B ∩ I | B ∩ B | B ∩ E
E | E ∩ I | E ∩ B | E ∩ E
I - Interior
B - Border
E - Exterior
在矩阵的每个单元格中，我想知道交点是否存在，如果存在我想知道它是点、线还是多边形。
值得注意的是，对于给定的单元格，多边形之间的交集可能由一组几何图形组成。但是，如果集合由一个点和一条线组成，我只对了解这条线感兴趣。在这个逻辑中，点的优先级最低，多边形的优先级最高。
因此，如果我们认为一个点是0维的，一条线是一维的，一个多边形是二维的，我想知道交集的最高维数。
到目前为止我有什么
好的，所以有一些算法，例如 Vatti 裁剪算法，可以将一个多边形裁剪到另一个多边形。这意味着这些算法提供了交集几何对象，它可能是对象的集合。有了这个结果，我相信9交矩阵是可以推导出来的，虽然我还没有真正想清楚。
此方法的一个问题是裁剪算法的二次复杂度，因为此算法将包含在 GIS 中以实现高效的拓扑查询回答。
不过我确实相信可以仅使用边界之间的交点来填充矩阵，可在 O(Nlog(N) + k) 中计算，其中 K 是使用 Balaban 提出的算法的交点数, 和简单的点位置。
不过，我也相信这种做法会导致非常多的条件。到目前为止，我有以下一组条件：
- 外部之间的交集始终是二维的
- 如果两个多边形的边界相交于一个非角点，则内部的交集是二维的
- 如果边界不相交并且多边形的至少一个点包含在另一个中，则第一个包含在第二个中（并且可以填充很多矩阵单元格）
- 如果边界不相交并且多边形的至少一个点位于另一个点之外，则多边形不相交（并且可以填充所有矩阵单元格）
问题是这套规则还不完整。例如，对于边界相交于至少一个多边形的角点的情况，我仍然没有好的规则。
实际问题
给定两个没有孔也没有自交的非凸多边形，计算关联两个几何对象的 9 交矩阵的最有效方法是什么？
构建多边形线段的平面直线图（PSLG）（输出元素数量呈线性关系），将多边形转换为 PSLG 循环，确定这些循环所包围的面（深度优先搜索，基本上)，然后剩下的就有些微不足道了。这里最困难的部分是计算 PSLG，但是有相关的库。
问题
给定两个没有孔的非凸多边形，我想计算对应的9交矩阵
一个 9 交集矩阵的形式为：
| I | B | E
I | I ∩ I | I ∩ B | I ∩ E
B | B ∩ I | B ∩ B | B ∩ E
E | E ∩ I | E ∩ B | E ∩ E
I - Interior
B - Border
E - Exterior
在矩阵的每个单元格中，我想知道交点是否存在，如果存在我想知道它是点、线还是多边形。
值得注意的是，对于给定的单元格，多边形之间的交集可能由一组几何图形组成。但是，如果集合由一个点和一条线组成，我只对了解这条线感兴趣。在这个逻辑中，点的优先级最低，多边形的优先级最高。
因此，如果我们认为一个点是0维的，一条线是一维的，一个多边形是二维的，我想知道交集的最高维数。
到目前为止我有什么
好的，所以有一些算法，例如 Vatti 裁剪算法，可以将一个多边形裁剪到另一个多边形。这意味着这些算法提供了交集几何对象，它可能是对象的集合。有了这个结果，我相信9交矩阵是可以推导出来的，虽然我还没有真正想清楚。
此方法的一个问题是裁剪算法的二次复杂度，因为此算法将包含在 GIS 中以实现高效的拓扑查询回答。
不过我确实相信可以仅使用边界之间的交点来填充矩阵，可在 O(Nlog(N) + k) 中计算，其中 K 是使用 Balaban 提出的算法的交点数, 和简单的点位置。
不过，我也相信这种做法会导致非常多的条件。到目前为止，我有以下一组条件：
- 外部之间的交集始终是二维的
- 如果两个多边形的边界相交于一个非角点，则内部的交集是二维的
- 如果边界不相交并且多边形的至少一个点包含在另一个中，则第一个包含在第二个中（并且可以填充很多矩阵单元格）
- 如果边界不相交并且多边形的至少一个点位于另一个点之外，则多边形不相交（并且可以填充所有矩阵单元格）
问题是这套规则还不完整。例如，对于边界相交于至少一个多边形的角点的情况，我仍然没有好的规则。
实际问题
给定两个没有孔也没有自交的非凸多边形，计算关联两个几何对象的 9 交矩阵的最有效方法是什么？
构建多边形线段的平面直线图（PSLG）（输出元素数量呈线性关系），将多边形转换为 PSLG 循环，确定这些循环所包围的面（深度优先搜索，基本上)，然后剩下的就有些微不足道了。这里最困难的部分是计算 PSLG，但是有相关的库。