什麼是整齊的算法來找到重疊的時間間隔？

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) 

Answer 2

線段是兩條相對光線（相反方向的兩條半無限線）的交點。你有兩條線段相交 - 結果是所有4條光線的交點。因此，您可以將代碼分解爲三個連續的光線交點：左側光線的左側與右側光線的右側相交。

（這是陳述現在接受的答案的另一種方式。）