अतिव्यापी अंतराल खोजने के लिए एक साफ एल्गोरिदम क्या है?

Question

मुझे यकीन है कि इससे पहले पूछा जाना चाहिए था, लेकिन मुझे यह नहीं मिल रहा है: मुझे केवल संबंधित, लेकिन कठिन प्रश्न मिल रहे हैं।

मैं चार अंक मिल गया है, दो पंक्तियों इस तरह का प्रतिनिधित्व:

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

तो उदाहरण में

, AB = {7, 21} और CD = {16,26}। (रेखाएं एक दूसरे के साथ किसी भी संबंध में हो सकती हैं, और किसी भी आकार में।) मैं यह जानना चाहता हूं कि वे ओवरलैप हैं या नहीं, और यदि ऐसा है तो। (उदाहरण में, उत्तर 5 होगा।) मेरे वर्तमान समाधान में जटिल/तो कदमों का एक गुच्छा शामिल है, और मैं मदद नहीं कर सकता लेकिन लगता है कि एक अच्छा अंकगणितीय समाधान है। है?

(। पी एस वास्तव में, मैं बाउंडिंग बॉक्स चौराहे कर रहा हूँ, लेकिन अगर मैं इसे एक आयाम में प्राप्त कर सकते हैं, अन्य एक ही होगा, जाहिर है)

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 किरणों का चौराहे है। तो आप अपने कोड को तीन लगातार रे-चौराहे के रूप में कारक बना सकते हैं: बाईं ओर वाली किरणों के बाएं तरफ दाएं किनारे वाली किरणों के दाएं किनारे से छेड़छाड़ की जाती है।

(यह अब स्वीकार किए जाते हैं जवाब बताते हुए का एक और तरीका है।)