JavaScriptで垂直区間の集合から指定サイズ以上の独立した交差部分を検出する方法

問題の概要

ここでは、y1 と y2 の2つの座標で定義される「垂直方向の区間」の集合を扱います。y1 は各区間の始点、y2 は終点を表します。

座標系の原点は画面の左上にあるため、常に y2 > y1 という関係が成り立ちます。

具体的なデータ例は以下の通りです。

const regions = [
    [10, 100],
    [50, 120],
    [60, 180],
    [140, 220]
];

やりたいこと

このような区間の配列を第1引数として受け取り、数値を第2引数として受け取る JavaScript の関数を作成します。目的は、第2引数で指定したサイズより大きい、互いに重なり合わない（独立した）交差部分をすべて見つけることです。

例えば、閾値を 20単位 とした場合、上記の配列に対する期待される出力は次のようになります。

const output = [
    [60, 100],
    [140, 180]
];

[50, 120] と [60, 180] が重なる部分は [60, 120] ですが、さらに [10, 100] とも重なるため、共通部分は [60, 100] になります。一方、[140, 220] は他の区間とは交差せず、その長さ 80 が閾値 20 を満たすため [140, 180]（長さ40の部分）として抽出されています。

実装のアプローチ

最もシンプルな方法は、全要素同士の組み合わせを調べて重なる区間を探し、反復処理の中で共通部分だけをフィルタリングしていくアルゴリズムです。Array.prototype.reduce() を使えば、これを簡潔に実装できます。

サンプルコード

const regions = [
    [10, 100],
    [50, 120],
    [60, 180],
    [140, 220]
];

const getIntersections = (arr, num) => {
    let disjoint, res;
    return arr.reduce((acc, val, ind, array) => {
        if (val.used) {
            return acc;
        };
        res = array.map((el, index) => array[(ind + index) % array.length])
            .reduce((s, e) => {
                disjoint = [Math.max(s[0], e[0]), Math.min(s[1], e[1])];
                return disjoint[0] < disjoint[1] ? (e.used = true, disjoint) : s;
            });
        res[1] - res[0] > num && acc.push(res);
        return acc;
    }, []);
}

console.log(getIntersections(regions, 20));

コードのポイント

• used フラグを使うことで、すでに他の区間との交差計算に組み込まれた区間をスキップし、同じ交差部分が重複して結果に含まれるのを防いでいます。
• Math.max(s[0], e[0]) と Math.min(s[1], e[1]) により、2つの区間の共通部分（開始点の大きい方・終了点の小さい方）を求めています。
• disjoint[0] < disjoint[1] のときのみ実際の重なりがあると判断し、その結果を採用します。
• 最後に res[1] - res[0] > num で交差部分の長さが閾値より大きいかどうかを判定し、条件を満たすものだけを結果配列に追加しています。

実行結果

コンソールに出力される結果は以下の通りです。

[ [ 60, 100 ], [ 140, 180 ] ]

このように、指定したサイズ以上の独立した交差部分だけが正しく抽出されていることが確認できます。