javascript - 查找相交数组的列表

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

据我所知，isects 列表不提供有关交集案例的完整信息——不可能从中了解三重交集。因此需要几何方法来确定确实发生了什么交叉点。

编辑 如果您对真正的几何交集不感兴趣，那么您必须解决图形问题:您有邻接表，并且想得到...什么？似乎所有可能K-size cliques with K=2 and more .

维基示例:

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))。通常用于查找最大团，但可以找到所有大小的团。