Çakışan aralıkları bulmak için düzenli bir algoritma nedir?

Question

Eminim bunun daha önce sorulmuş olması gerekir, ama bulamıyorum: Sadece ilgili, ancak daha zor soruları buluyorum.

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

Yani örnekteki

, AB = {7, 21} ve CD = {16,26}:

böyle iki satır temsil dört puan var. (Çizgiler birbirleriyle ve herhangi bir boyutta herhangi bir ilişkide olabilirler.) Üstüste gelip gelmediklerini ve ne kadar olursa olsun öğrenmek istiyorum. (Örnekte, cevap 5 olacaktır.) Şu anki çözümüm karmaşık bir grup/adımdan oluşuyor ve ben yardımcı olamıyorum ama güzel bir aritmetik çözüm olduğunu düşünüyorum. Var mı?

(. Açıkçası, PS Gerçekten, sınırlayıcı kutunun kavşak yapıyorum ama bir boyutta alabilirsiniz eğer, diğer aynı olacaktır)

Answer 1

bu deneyin:

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)) 

Eğer a <= b ve c <= d varsayabiliriz:

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

aşağıdaki gibi de intersects hesaplayabilirsiniz:

intersects = (overlap > 0) 

Answer 2

Bir çizgi parçası, iki karşıt ışığın kesişimidir (zıt yönlerde iki yarım sonsuz çizgi). Kesişecek iki çizgi bölümünüz var - sonuçta tüm 4 ışının kesişme noktasıdır. Böylece kodunuzu birbirini takip eden üç ışın kesişme noktası olarak değerlendirebilirsiniz: sol taraftaki ışınların solu sağ taraftaki ışınların sağ tarafıyla kesişir.

(Bu şimdi kabul gören cevabı belirten başka bir yoludur.)