如何叠加重叠间隔，不包括重叠
我们已经收集了数据，其中我们沿着卷尺测量了特定物种重叠的长度。 在某些情况下，多个物种可能在同一个地点重叠。 我需要弄清楚当多个植物重叠在同一地点时，有多less胶带被植物重叠而没有计算相同长度的胶带两次，我需要按照植被types（例如灌木，树等）进行分组。 所以，我正在回答这个问题：“有多less胶带被灌木覆盖？” 例如。
例如，假设虚线是卷尺，星号是与磁带重叠的所有不同的灌木。 这就是我的数据现在所代表的。 如果我计算所有灌木的长度，我会得到一个很大的数字，比磁带的实际长度更长。
*** ** ********* **** ** ******* ---------------------------- …但是这是我需要弄清的，任何灌木覆盖的胶带的实际长度：
***** ** ************** ----------------------------
我希望这是有道理的，但这里有一些例子需要进一步解释：
例子：想象一下，我遇到了道格冷杉树，它与从4'标记延伸到10'标记和20'标记延伸到25'标记的卷尺重叠。 我也遇到了从7英尺到14英尺的磁带重叠的云杉树。 我需要知道树种重叠的总长度（这两棵树都是树），所以我需要将这两个范围的长度相加，用于Spruce和Doug Fir。 但是，如果我只是正常地将所有的范围进行总和，那么我将最终将7到10个区域（总和= 3'）计数两次而不是一次，其中Spruce和Doug Firs都覆盖了磁带。 所以，我需要从最终值中减去3'，这样卷尺的这部分不会被计数一次以上。 所以，我的范围是6'，5'和7'，总计18'。 在减去重叠的3'后，总共有15英尺的地方树木重叠在一起。
下面的示例表。 我已经有了SPECIES，START，END，TYPE和SUM数据。 我需要excel来帮助我计算的是表格下面显示的值，它们是考虑多物种重叠之后的总和。 例如，如果灌木X从10'重叠到20'，而灌木Y从13'重叠到25'，则总重叠将是从10'到25'，因此十五英尺重叠。 不是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
任何指导意见，将不胜感激！
这是一些可能工作的伪代码。 此外，这只是估计每个types。 要获得整个区域，请重复每个types：
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])
忽略意味着该段不再被testing。 合并意味着使段a（i，j）和b（x，y）成为新的段c（i，y）。 这只是一个快速的方法，它需要O（n ^ 2）。 必须有一个更好的方法。