如何在不包含重叠的情况下对重叠间隔求和

Question

我们收集了一些数据，在这些数据中，我们沿着测量带测量了特定物种重叠的长度。在某些情况下，多个物种可能会在同一地点重叠。当多个植物重叠在同一地点时，我需要计算出有多少胶带被植物重叠，而不计算相同长度的胶带两次，并且我需要按植被类型(例如，灌木、树木等)进行分组。所以，我要回答的问题是，“胶带上有多少是灌木？”例如。

例如，假设虚线是卷尺，星号是重叠在卷尺上的不同灌木。这就是我的数据现在本质上所代表的。如果我计算所有灌木的长度，我会得到一个很大的数字，比胶带的实际长度更长……

  ***    **    *********
   ****       **     *******
----------------------------

...but这是我需要弄清楚的，任何灌木覆盖的实际磁带长度：

  *****  **   **************
----------------------------

我希望这是有意义的，但如果需要的话，这里有一些例子可以进一步解释：

例如:假设我遇到了Doug Fir树，它与从4‘标记延伸到10’标记和从20‘标记延伸到25’标记的卷尺重叠。我还遇到了云杉树重叠的磁带从7‘到14’的标记。我需要知道树种重叠的总长度(这两种树都是树)，所以我需要对云杉和豆科冷杉的这些范围的长度进行求和。然而，如果我只是正常地将所有范围相加，我将结束计数7‘到10’的面积(sum = 3')两次，而不是一次，云杉和Doug Fir都覆盖了磁带。因此，我将需要从最终值中减去3‘，以便测量卷尺的这一部分不会被多次计数。所以，我的范围是6'，5‘和7'，总共是18’。减去重叠的3英尺后，树木与胶带重叠的地方总共有15英尺。

示例表如下。我已经有了种类、开始、结束、类型和总和数据。我需要excel来帮助我计算下表中显示的值，这些值是考虑到多物种重叠后的总和。例如，如果灌木X从10‘重叠到20'，灌木Y从13’重叠到25'，那么总重叠将从10‘到25’，因此重叠15英尺。不是22英尺的重叠，这就是如果你单独计算每个范围的话。)

SPECIES START(ft) END(ft) TYPE  SUM (ft)
Dogwood 40.3      40.9    Shrub   0.6
Cedar   52.8      79.5    Tree    26.7
Dogwood 50.2      55.6    Shrub   5.4
Rose    53.8      54.4    Shrub   0.6
Alder   88.2      95.5    Tree    7.3
Clover  75.8      76.2    Forb    0.4
Bunch   82.8      90.3    Grass   7.5
Poa     86.1      95.3    Grass   9.2
Sedge   99.4      100.9   Grass   1.5
Bttrcp  74.5      101.3   Forb    26.8
Elder   105.8     120.3   Shrub   14.5
Bttrcp  110.3     120.2   Forb    9.9
Cedar   90.4      99.9    Tree    9.5



SHRUB SUM   TREE SUM    FORB SUM    GRASS SUM
  20.5       38.4         35.4         14

任何关于解决这一问题的指导都将不胜感激！

Answer 1

下面是一些可能起作用的伪代码。此外，这只是每种类型的估计值。要获取整个区域，请对每种类型重复此操作：

get_max_area(data):
    sort(data, START)
    for i <- 1 to n:
        for j <- i to n:
            if data[j][START] < data[i][START]:         // Two segments overlap
                if data[j][END] < data[i][END]:         // j is fully contained within i
                    ignore(data[j])
                else:                                   // They just overlap
                    merge(data[i], data[i + 1])
                                                        // ELSE: independent segments

    return sum(data[SUM])

忽略意味着不再测试该段。合并意味着使段a(i，j)和b(x，y)成为新的段c(i，y)。这只是一种快速的方法，并且需要O(n^2)。一定有更好的方法。