计算两个多边形之间的9相交矩阵

问题

给定两个没有孔的非凸多边形,我想计算相应的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维,一条线是1维,一个多边形是2维,我想知道交点的最高维度。

到目前为止我所拥有的

好的,有一些算法,比如Vatti裁剪算法,可以将一个多边形裁剪到另一个多边形上。这意味着这些算法提供了相交几何对象,它可以是对象的集合。有了这个结果后,我相信可以推导出9相交矩阵,尽管我还没有真正考虑清楚。

这种方法的一个问题是裁剪算法的二次复杂性,因为该算法要包含在GIS中,以实现高效的拓扑查询应答。

然而,我确实相信,可以仅使用边界之间的交点来填充矩阵,可在O(Nlog(N)+k)中计算,其中k是使用Balaban提出的算法和简单点位置的交点数量。

然而,我也相信,这种方法将导致一系列非常大的条件。到目前为止,我有以下一组条件:

• 外部之间的相交总是二维的
• 如果两个多边形的边界在不是角的点相交,则内部的相交是二维的
• 如果边界不相交,并且多边形的至少一个点包含在另一个点中,则第一个点包含于第二个点中(并且可以填充许多矩阵单元)
• 如果边界不相交,并且多边形的至少一个点位于另一个点之外,则多边形是不相交的(并且可以填充所有矩阵单元)

问题是,这套规则目前还不完整。例如,对于边界在一个点相交的情况,我仍然没有一个好的规则,该点也是至少一个多边形的角。

实际问题

给定两个没有孔或自相交的非凸多边形,计算两个几何对象之间的9相交矩阵的最有效方法是什么?