겹치는 간격을 찾는 깔끔한 알고리즘은 무엇입니까?

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 개의 모든 광선이 교차하는 것입니다. 따라서 코드를 세 개의 연속적인 광선 교차점으로 간주 할 수 있습니다. 왼쪽 방향 광선의 왼쪽은 오른쪽 광선의 오른쪽 방향과 교차합니다.

(이 지금은 허용 대답을 진술의 또 다른 방법입니다.)