オーバーラッピング間隔を見つけるためのきちんとしたアルゴリズムとは何ですか？

Question

これは以前に聞いたことがあるはずのものだと確信していますが、私はそれを見つけることができません。

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

だから、例の

、AB = {7, 21}とCD = {16,26}：

私はこのような2つの行を表す、4点を持っています。 （線はお互いにどんな関係にあっても、どんな大きさでもかまいません）。重なりあっているかどうか、もしあればどれだけ重なり合っているかを調べたいと思います。 （この例では、答えは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

線分は、2つの対向する光線（反対方向の2つの半無限線）の交差点です。あなたは交差する2つの線分を持っています - 結果は4つのすべての光線の交差です。したがって、コードを3つの連続する光線交差点として因数分解することができます。左向き光線の左向きは、右向き光線の右向きと交差します。

（これは現在受け入れられている回答です）