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

给定两个无孔非凸多边形，我想计算相应的9交集矩阵。

A 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维，一维线和多边形二维，我想知道交点的最高维。

我至今

好了，有算法，如华帝裁剪算法，该剪辑多边形到另一个。这意味着这些算法提供了相交的几何对象，可能是一组对象。得到这个结果后，我相信有可能推导出9-Intersection Matrix，即使我没有真正想过它。

这种方法存在的问题之一是剪裁算法的二次复杂性，因为该算法将被包含在GIS中用于有效的拓扑查询回答。我确实认为可以仅使用边界之间的交点来填充矩阵，可以在O（Nlog（N）+ k）中计算，其中K是使用Balaban提出的算法的交点的数量，和简单的点位置。

但是，我也相信这种方法会导致一组非常大的条件。到目前为止，我已在以下条件：

外墙之间的交集总是2维
如果两个多边形的边界在一个点上，是不是一个角相交，的交集内部是二维的
如果边界不相交并且另一个中包含至少一个多边形点，则第一个包含在第二个中（并且可以填充大量矩阵单元）
如果边界不相交并且多边形的至少一个点位于另一个点的外部，则多边形不相交（并且所有矩阵c ells可以填写）

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

的实际问题

给定两个非凸多边形没有孔也没有自交差，什么是计算的最有效的方式9的交集矩阵，其涉及两个几何对象？

来源

2015-09-17 Bernardo Marques

你看过JTS或GEOS吗？ [这里是JTS的IntersectionMatrix]（http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/geom/IntersectionMatrix.html），或者查看[GEOS for同一个类的C++端口]（ https://github.com/libgeos/libgeos/blob/svn-trunk/src/geom/IntersectionMatrix.cpp）。 –

构建多边形线段（在输出元素数目中为linearithmic）的平面直线图（PSLG），将多边形转换为PSLG周期，确定由这些周期包围的面（基本上是深度优先搜索），然后其余的都是微不足道的。这里最困难的部分是计算PSLG，但也有一些库。

来源

2015-09-17 18:22:16

好吧，我花了一段时间，但现在我看到你的答案是如何工作的。你知道如何建立一个多边形的平面图的参考？或者你可以用一个实现来命名一个库？ –

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

回答

相关问题