0

编辑：层次结构不适合我的目标。留下原始请求，但我回答了满足以下核心请求（重叠/非重叠规则）的内容。

假设有一组 1D 线，每条线由 2 个无符号整数描述：start 和 end，start < end。我想根据它们是否重叠来创建组，但我不希望组包含任何不重叠的行。在一条线在多个组中的情况下，我想我需要某种层次结构来跟踪组中的组......

这是规则：

  • 重叠的线必须在层次结构中尽可能低地组合在一起。
  • 不重叠的线不能在同一组中。

无论如何，这是一个示例图片：

线条

快速浏览一下，我可以说Line Aand Line Cform Group 0，Line Hand Line Iform Group 1， and Line Bis Group 2。其他所有内容都是重叠的组，Line D在Group 1and中Group 2，Line E在Group 0and中Group 1，并且Line FandLine G都在这三个组中。所以这里有两层分组，但我很确定可能有 N 取决于问题的复杂性。而且我也很确定我的示例没有代表一些问题。

处理这个问题的典型算法是什么？

4

2 回答 2

1

我意识到我的重叠和不重叠两条规则与层次结构不兼容。这是我确定的算法，用漂亮的图片来解释。

重铸的线条

基本思想最终归结为找到“重叠最大值”。这些行需要按开始升序排序，然后从左到右循环。您从“关闭”状态开始，这意味着没有“开放”组等待被关闭。当前正在迭代的线被认为是“活动线”。

规则 1： 如果处于关闭状态并且遇到线路启动，则切换到打开状态。发生这种情况的点用绿点表示。如果多行在同一步骤中打开一个组，我将它们全部用绿点表示，因为不知道首先遇到哪一行。

继续收集线，直到到达终点。

规则 2： 如果处于打开状态且活动线路正在结束，则将所有活动线路（包括任何结束活动线路）放入一个新组中。算法切换到关闭状态。形成组时的步骤以蓝色突出显示。触发此操作的线端用红点表示。一步多点的规则与之前相同。

例如，形成的第一组是Line A、Line C、Line F和Line G。上面两条规则足以处理这个例子。

有一个最终规则，在此示例中不会起作用。

规则 3： 如果算法在打开状态下结束迭代，则将所有活动线放入一个新组中。

以下是该算法产生的 4 个组：

线组

于 2012-10-04T21:18:40.330 回答
0

我想说一些层次聚类的变体符合要求。相似度函数可以是两条线段之间的重叠程度。

于 2012-10-04T15:47:27.527 回答