如何找到两个给定范围之间的重叠部分？

Question

有没有一种有效的方法来查找两个范围之间的重叠部分?

实际上，这两个范围标记为(a - c)和(b - d)，并且我假设(c > a) && (d > b)。

(b <= a <= d) which means if ((a >= b) && (d > a))
(b <= c <= d) which means if ((c >= b) && (d >= c))
(a <= b <= c) which means if ((b > a) && (c > b))
(a <= d <= c) which means if ((d > a) && (c > d))

但它永远不会结束，因为这样我一次只能找到一个范围，在每个范围中，我必须检查其他情况。

例如，如果第一个条件（1）正确，我知道发生了什么，范围的起始点（a），但我仍然需要检查其他条件以找到范围的终点（c）。

更不用说所有这些都只适用于（c > a）&&（d > b），而不是它们中的任何一个相等。

- david

---

你只是想找到重叠部分吗？还是想合并重叠的范围？ - Rahul

你想要检查两个范围是否重叠吗？或者你需要找到重叠的范围吗？ - FallAndLearn

大卫，那张图片是否描述了你的问题领域？ - Mr. Polywhirl

实际上，标记为(a-c)和(b-d)的两个范围，我假设(c>a)&&(d>b)，那么为什么不直接取int range = C - B呢？如果(c>a)&&(d>b)总是成立，这应该就足够了。 - messerbill

不幸的是，它并没有描述得很好。 我必须处理一些情况，比如a-c（或b-d）包含在另一个范围内，例如1-5和2-3。 或者当图像和重叠在b-a时，情况相反。 - david

你可能想要查看名为IntervallTree的数据结构。我不懂Java，所以无法展示。 - RomainL.

Answer 1

两个范围在以下两种基本情况下重叠：

• 一个范围完全包含另一个范围（即一个范围的起始和结束都在另一个范围的起始和结束之间），或者
• 一个范围的起始或结束被包含在另一个范围内

相反地，仅当每个范围的端点均不包含在另一个范围内时它们不会重叠（图中的情况11和12）。我们可以检查任一范围的低端是否超过了另一个范围的高端，以检测这两种情况：

if (a > d || c < b) {
    // no overlap
}
else {
    // overlap
}

如果更喜欢这样做，我们可以翻转条件并使用德摩根定律来交换顺序：

if (a <= d && c >= b) {
    // overlap
}
else {
    // no overlap
}

为了找到实际的重叠范围，您需要取两个起始端点的最大值和两个结束端点的最小值：

int e = Math.max(a,b);
int f = Math.min(c,d);
// overlapping range is [e,f], and overlap exists if e <= f.

以上所有内容都是基于范围为 包含 的假设，也就是说，由a和c定义的范围包括a和c两个值。然而，对于不包含范围的调整相对容易。

- davmac

---

这就是答案。 </thread> /s - Mr. Polywhirl

我本来15分钟前就可以回答这个问题了，但是我在为楼主制作一张图形。 - Mr. Polywhirl

@Mr.Polywhirl 谢谢。确实，如果有适当的图形显示两种不重叠的情况，那么很容易看出if语句中的条件是正确的！当然，这在人们的脑海中很容易想象 :) - davmac

我实现了下面的修改后的循环检测算法。 - Mr. Polywhirl

这里使用ac和bd而不是ab和cd的表示法非常误导人。但这与问题中的表示法相同。 - gvlasov

Answer 2

使用 Apache Commons 的 Range 类及其子类，特别是 overlap 方法 。

- Boris Pavlović

Answer 3

您可以使用修改后的圆形碰撞检测算法来检测两个范围的碰撞。

import java.util.Arrays;

public class RangeUtils {
    public static void main(String[] args) {
        int[] rangeA = { 10, 110 };
        int[] rangeB = { 60, 160 };
        int[] rangeC = intersectingRange(rangeA, rangeB);

        System.out.println("Range: " + Arrays.toString(rangeC)); // Range: [60, 110]
    }

    // Based on circular collision detection.
    public static boolean collisionDetected(int[] rangeA, int[] rangeB) {
        int distA = Math.abs(rangeA[1] - rangeA[0]) / 2;
        int distB = Math.abs(rangeB[1] - rangeB[0]) / 2;
        int midA = (rangeA[0] + rangeA[1]) / 2;
        int midB = (rangeB[0] + rangeB[1]) / 2;

        return Math.sqrt((midB - midA) * (midB - midA)) < (distA + distB);
    }

    public static int[] intersectingRange(int[] rangeA, int[] rangeB) {
        if (collisionDetected(rangeA, rangeB)) {
            return new int[] {
                Math.max(rangeA[0], rangeB[0]),
                Math.min(rangeA[1], rangeB[1])
            };
        }

        return null;
    }
}

---

这是一段关于代码的视觉示例，已移植到JavaScript。

var palette = ['#393A3F', '#E82863', '#F6A329', '#34B1E7', '#81C683'];
var canvas = document.getElementById('draw');
var ctx = canvas.getContext('2d');

var rangeA = [10, 110];
var rangeB = [60, 160];
var rangeC = intersectingRange(rangeA, rangeB);

var collisionText = 'Range: [' + rangeC + ']';

var leftOffset = 18;
var topOffset = 24;

drawLines(ctx, [rangeA, rangeB], topOffset);
drawText(ctx, collisionText, leftOffset, topOffset);
drawBoundry(ctx, rangeC, topOffset);

// Based on circular collision detection.
function collisionDetected(rangeA, rangeB) {
  var distA = Math.abs(rangeA[1] - rangeA[0]) / 2;
  var distB = Math.abs(rangeB[1] - rangeB[0]) / 2;
  var midA = (rangeA[0] + rangeA[1]) / 2;
  var midB = (rangeB[0] + rangeB[1]) / 2;

  return Math.sqrt((midB - midA) * (midB - midA)) < (distA + distB);
}

function intersectingRange(rangeA, rangeB) {
  if (collisionDetected(rangeA, rangeB)) {
    return [Math.max(rangeA[0], rangeB[0]), Math.min(rangeA[1], rangeB[1])];
  }

  return null;
}

function drawText(ctx, text, x, y) {
  ctx.save();
  ctx.font = '18px Arial';
  ctx.fillText(text, x, y);
  ctx.restore();
}

function drawLines(ctx, lines, topOffset) {
  topOffset = topOffset || 0;
  var sizeWidth = ctx.canvas.clientWidth;
  var sizeHeight = ctx.canvas.clientHeight - topOffset;
  var yOffset = sizeHeight / (lines.length + 1);

  for (var i = 0; i < lines.length; i++) {
    var color = palette[i % palette.length];
    var yPos = (i + 1) * yOffset + topOffset;
    drawLine(ctx, lines[i], yPos, color)
  }
}

function drawLine(ctx, range, index, color) {
  ctx.save();
  ctx.beginPath();
  ctx.moveTo(range[0], index);
  ctx.lineTo(range[1], index);
  ctx.strokeStyle = color;
  ctx.lineWidth = 4;
  ctx.stroke();
  ctx.restore();
}

function drawBoundry(ctx, bounds, topOffset) {
  var sizeHeight = ctx.canvas.clientHeight - topOffset;
  var padding = sizeHeight * 0.25;
  var y1 = topOffset + padding;
  var y2 = sizeHeight + topOffset - padding;
  ctx.save();
  ctx.beginPath();
  ctx.strokeStyle = palette[4];
  ctx.setLineDash([5, 5]);
  ctx.lineWidth = 2;
  ctx.rect(bounds[0], y1, bounds[1] - bounds[0], sizeHeight * 0.5);
  ctx.stroke();
  ctx.restore();
}

canvas#draw {
  background: #FFFFFF;
  border: thin solid #7F7F7F;
}

<canvas id="draw" width="180" height="160"></canvas>

- Mr. Polywhirl

Answer 4

检查是否有重叠（只是true/false）实际上非常简单：

假设范围为[a，b]和[c，d]。

如果 a <= d 并且 b => c，那么您就有了一个重叠。这对于a = b和/或c = d也适用。

如果您有一个重叠，则重叠的范围为[max(a，c)，min(b，d)]。

- Thomas

Answer 5

让我们更清晰地定义范围： (start1, end1) 和 (start2, end2)。

Double totalRange = Math.max(end1, end2) - Math.min(start1, start2);
Double sumOfRanges = (end1 - start1) + (end2 - start2);
Double overlappingInterval = 0D;

if (sumOfRanges > totalRange) { // means they overlap
   overlappingInterval = Math.min(end1, end2) - Math.max(start1, start2);
}

return overlappingInterval;

根据这个回答

- Daniel

---

这太复杂了，而且会忽略两个集合有一个共同成员的边缘情况（考虑2个范围1..2和2..3，它们都有长度=1，因此totalRange == 2，sumOfRanges == 2，因此您的“if”将错过重叠值“2”。如果您将“>”更改为“>=”，则可以正常工作。但整个事情可以简化：只保留1行，计算重叠间隔，然后添加仅+1行，“if（overlappingInterval> = 0）则有重叠；否则没有重叠。” - Dmitry Shevkoplyas

Answer 6

设x=max(a,b)，y=min(c,d)。如果x < y（或x≤y），则(x-y)是两个范围的公共部分（在x=y的情况下退化），否则它们不重叠。

- CiaPan

Answer 7

根据其他回答这个问题的答案，我编写了以下两个代码示例：

第一个示例仅返回一个布尔值，指示两个范围是否重叠：

//  If just a boolean is needed
    public static boolean overlap(int[] arr1, int[] arr2) {
      if((arr1[0] <= arr2[arr2.length - 1]) && (arr2[arr1.length - 1] >= arr2[0])) {
        return true;
      } else {
        return false;
      }
    }

第二个函数将返回一个整数数组，其中包含重叠值（如果存在重叠）。否则，它将返回一个空数组。

//  To get overlapping values
public static int[] overlap(int[] arr1, int[] arr2) {
  int[] overlappingValues = {};
  if((arr1[0] <= arr2[arr2.length - 1]) && (arr2[arr1.length - 1] >= arr2[0])) {
    int z = 0;
    for(int a : arr1) {
      for(int b : arr2) {
        if(a == b) {
          overlappingValues[z] = a;
          z = z + 1;
        }
      }
    }
  } else {
    return {};
  }
}

希望这能有所帮助。

- Marco N.

---

arr2[arr2.length] - 这将是一个越界的数组索引。 - davmac

此外，你的“overlap”方法似乎将输入数组视为包含离散值的_set_。它找到的是两个集合的_union_，而不是两个范围的_overlap_。 - davmac

谢谢你提醒长度的问题，我忘记那里要减1了。:/它不可能是联合吧？这意味着如果我们有数组[1,2,3]，[2,3,4]，我们将得到返回值[1,2,3,4]。但方法应该返回[2,3]，因为只有这些值相等。我想你指的是交集。是的，但从未指定范围如何表示。所以我假设它们将以数组表示给出。但如果它们是连续的，你是对的，我的解决方案将找不到答案。 - Marco N.

是的，交集，抱歉。我认为问题已经很清楚地表明范围是由两个端点表示的。 - davmac

是的，现在我也明白了。我还利用这个反馈来调整我的第二个回答，不仅考虑离散（不太可能）的情况，还考虑了（更有可能的）连续情况。但是感谢您的反馈。学习和被提醒要先仔细阅读总是很好的。 - Marco N.

Answer 8

根据最新的问题，我通过谷歌做了一些研究，并找到了这篇文章：

Java, find intersection of two arrays

据我目前所了解的，它应该符合给定的要求。代码片段很短，据我所知也看起来很好。

为了考虑离散值和连续值的备注，我想添加另一个我能够找到的连续范围的潜在解决方案：

https://community.oracle.com/thread/2088552?start=0&tstart=0

这个解决方案并不直接返回重叠的范围，但提供了一个有趣的类实现来进行范围比较。

- Marco N.