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

Question

我敢肯定以前一定会被问过,但我找不到它:我只是找到了相关但更难的问题.

我有四点,代表两行:

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

所以在这个例子中,AB = {7, 21}和CD = {16,26}.(这些线可以是彼此之间的任何关系,也可以是任何尺寸.)我想知道它们是否重叠,以及它是否重叠.(在这个例子中,答案是5.)我当前的解决方案涉及一堆复杂的if/then步骤,我不禁想到有一个很好的算术解决方案.在那儿？

(PS真的,我正在进行边界框交叉,但是如果我可以在一个维度上获得它,那么另一个将是相同的,显然.)

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)