查找相交数组的列表

Question

这是我的数据集：

isects = [[3],[2,3],[1,3],[0,1,2],[]]

以下是我的数据集中模式的一些可视化：

每个元素都是元素相交的索引列表。所以，元素@0只与元素3相交。而元素@3与元素0、1和2相交。你知道吗

我想创建这些元素之间的交叉点列表。我希望列表末尾有更多的交叉点。对于我的示例集，解决方案如下所示：

[[0,3], [1,2], [1,3], [2,3], [1,2,3]]

即0&3相交，1&2、1&3和2&3相交。最后，1&2&3都互相相交。

正如下面的评论所指出的，如果1&2&3实际上是多边形，则它们可能并不都相交，但出于我的目的，我假设所有列出的元素都可以并且将彼此相交。

仅使用isects列表获取此数据的最快方法是什么？你知道吗

Answer 1

我将创建一个与isect数据相交的表。你知道吗

  0 1 2 3 4
0 -     x
1   - x x
2   x - x
3 x x x -
4         -

每个“x”代表一个交点。交点是集合，因此[0,1]和[1,0]是相同的。从而得到唯一的交点列表：[0,3]，[1,2]，[1,3]，[2,3]。你知道吗

如果你想考虑当其他多边形与同一个多边形重叠时是一个公共交点，那么看看被x包围的“-”，在这种情况下，你只有一个（在2x2处），因此你有[1,2,3]作为一个重叠交点。然而，我同意这里的其他人的观点，isect中的数据不能保证有重叠。

Answer 2

据我所知，isects列表并没有提供关于交叉口情况的完整信息-不可能从中了解三重交叉口。所以需要几何方法来得到交叉点的位置。你知道吗

编辑如果你对真正的几何相交不感兴趣，那么你必须解决图形问题：你有邻接列表，并且想要得到。。。什么？似乎一切都有可能。你知道吗

Wiki示例：

The graph shown has one maximum clique, the triangle {1,2,5}, and four more maximal cliques, the pairs {2,3}, {3,4}, {4,5}, and {4,6}.

Bron-Kerbosch algorithm对于搜索所有派系是相对有效的（而复杂度是O（3^（n/3））。它通常用来寻找最大集团，但可以找到所有大小的。你知道吗