找到重叠区间的简洁算法是什么？

Question

我相信这个问题之前一定被问过了，但是我没有找到它：我只找到了相关的，但更难的问题。

我有四个点，表示两条线，如下所示：

       A         C      B   D
|------*---|-----+----|-*---+---|----------|
0          10         20        30         40

所以在这个例子中，AB = {7, 21}和CD = {16,26}。 （这些线段可以处于任何关系并且任意大小。）我想找出它们是否重叠，如果有的话重叠了多少。（在这个例子中，答案是5。）我的当前解决方案涉及一堆复杂的if/then步骤，我不禁想到是否存在一个漂亮的算术解决方案。 存在吗？

（附言：实际上，我正在进行边界框相交检测，但如果我可以在一个维度中解决它，另一个维度显然也是同样的。）

- sprugman

Answer 1

试试这个：

intersects = (max(a,b) > min(c,d)) && (min(a,b) < max(c,d))
overlap = min(max(a,b), max(c,d)) - max(min(c,d), min(a,b))

如果你可以假设 a <= b 且 c <= d：

intersects = (b > c) && (a < d)
overlap = min(b, d) - max(c, a)

你也可以按照以下方式计算intersects：

intersects = (overlap > 0)

- Mark Byers

---

我想知道它们重叠的数量，而不仅仅是它们是否重叠。谢谢。 - sprugman

@sprugman：将Mark的代码推广到计算交集的数量应该很容易。 - Matt Ball

他为我做了这件事，Matt。谢谢，Mark! :) - sprugman

“max(a,b)”不总是“b”，至少在我设置的问题中是这样吗？而“min(c,d)”总是“c”吗？等等。 - sprugman

如果你假设 a <= b 和 c <= d，那么是的。我没有在你的问题中看到任何地方说明这种假设是安全的，所以我没有做出这个假设。我已经更新了我的答案。 - Mark Byers

@Mark，说得好。在这种情况下，我们可以获得 overlap = min(b, d) - max(c, a) ，这正是我所说的整洁之处！ :^, - sprugman

Answer 2

一条线段是两个相对射线的交集（两个方向相反的半无限长直线）。您有两条线段要相交 - 结果是所有4条射线的交点。因此，您可以将代码分解为三个连续的射线交点：左侧面向左的射线与右侧面向右的射线相交。

（这是另一种陈述现在被接受的答案的方式。）

- Darius Bacon