Алгоритм для вычисления общей площади, охватываемой набором перекрывающихся сегментов?

Question

У меня есть список конечных точек, возможно, перекрывающихся интервалов, и я хотел бы получить эффективный способ вычисления общей площади, покрытой k интервалами, для k=1,2,... (без выполнения всех парных сравнений). Или это невозможно?

Например, предположим, что x - это список начальных точек, а y - это список конечных точек, и что x[i] < y[i], и

x = (1.5, 2, 3, 5)
y = (3, 4, 4, 6)

, так что общая площадь, охватываемая по меньшей мере одним интервалом, равна 3,5, а общая площадь, охватываемая по меньшей мере двумя, равна 1.

спасибо, тел.

Answer 1

Это классическая проблема строчной развертки в вычислительной геометрии.

Положите +1 в каждой начальной точке и -1 в каждой конечной точке. Затем представьте, как вы идете по числовой линии от отрицательной бесконечности к положительной бесконечности.

Каждый раз, когда вы сталкиваетесь с +1, увеличивайте свой рост на 1. Каждый раз, когда вы нажимаете -1, уменьшайте свой рост. При переходе от p1 к p2 в числовой строке добавьте p2 - p1 (развернутая длина) к величине, покрытой данной высотой.

Тогда у вас будет гистограмма длин, покрытых точно каждой высотой. Вы можете накапливать итоги, если хотите обработать случай «как минимум с двумя интервалами».

Answer 2

Я не знал, что @rrenaud опубликовал свое решение, когда писал то же самое, поэтому я опущу объяснение и просто дам вам код. Это javascript-версия развертки строки:

// x and y inputs are your start and end points for ranges,
// as in the example data
function countOverlapRanges(x, y) {
    var ranges = [];
    var n = x.length;
    if (n !== y.length) {
        throw "Input arrays must be the same length!";
    }
    var i;

    // iterate over all inputs, pushing them into the array
    for (i = 0; i < n; ++i) {
        ranges.push({
            value: x[i],
            change: 1
        });
        ranges.push({
            value: y[i],
            change: -1
        });
    }

    // sort the array into number-line order
    ranges.sort(function (a, b) {
        return a.value - b.value;
    });

    var result = {};
    var k = 1;
    var maxK = 1;
    n = ranges.length;

    // iterate over the sorted data, counting the size of ranges
    var cur, value, lastValue = ranges[0].value;
    for (i = 1; i < n; ++i) {
        cur = ranges[i];
        value = cur.value;
        if (k) {
            var difference = value - lastValue;
            result[k] = (result[k] || 0) + difference;
        }
        k += cur.change;
        maxK = Math.max(maxK, k);
        lastValue = value;
    }

    // so far we've counted the ranges covered by exactly k intervals.
    // adjust the results to get the size of ranges covered by
    // at least k intervals.
    var sum = 0;
    for (i = maxK; i > 0; --i) {
        sum = result[i] = sum + result[i];
    }

    return result;
}

Возвращает объект, который отображает значения k на расстояния вдоль линии.