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

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

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

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

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

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


range algorithm math computational-geometry
person petrelharp    schedule 08.09.2011    source источник
comment
общая площадь, охватываемая хотя бы одним интервалом, составляет 3,5. Я что-то упускаю - как вы это понимаете?   -  person davmac    schedule 08.09.2011
comment
Площадь, покрытая интервалами — несоответствие размеров?   -  person n. 1.8e9-where's-my-share m.    schedule 08.09.2011
comment
Я имел в виду площадь в общем смысле (здесь длина). @davmac нарисовать картинку?   -  person petrelharp    schedule 08.09.2011

Ответы (2)


arrow_upward
7
arrow_downward

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

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

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

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

person Rob Neuhaus    schedule 08.09.2011
comment
Рэд, так и будет. Как раз то, что я искал! - person petrelharp; 08.09.2011

arrow_upward
1
arrow_downward

Я не знал, что @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 с расстояниями вдоль линии.

person sethobrien    schedule 08.09.2011