두 개의 호 사이의 교차 검사

Question

두 개의 호가 시작 및 끝 각도, 중심 및 반지름을 포함하는 객체로 정의됩니다.

정의는 다음과 같이 보입니다 :

arc = { 
    start: 0, 
    end: Math.PI, 
    radius: 10, 
    centre: [0, 0] 
} 

나는 호는 어떤 점에서 교차하는 경우 알고 싶은,하지만 나는이 작업을 수행하는 방법을 확실 해요. 두 원의 반지름과 중심이 같은 두 원 사이의 교차점을 찾은 다음 두 원호에 해당 점이 있는지 확인하려고했지만 시작/끝 각도가 두 호 사이에 있지 않을 수도 있습니다. 0과 2π - 어떤 값이든 상관 없으며 원호가 호에 놓여 있는지 여부를 확인하는 방법을 모르겠습니다.

어떻게 두 개의 호가 교차하는지 확인할 수 있습니까? (가치가있는 부분에 대해서는 JavaScript를 사용하고 있지만 어떤 언어 든 대답으로 작동합니다)

Answer 1

글쎄, 이것은 약간 오래된 답변이지만. 그러나 첫째, 아크 구조는 그것이 진술 된 방식으로 질문에 대한 작업을하기에 충분한 정보가 없습니다. 원호가 2pi 라디안 이상으로 몇 번이나 돌아가는지 알려주는 것은 없습니다. 만약 그렇다면 2pi 이상의 아크에 대한 생각은 어쨌든 기하학적으로 어리 석다. 가능성은 피할 필요가있다. 여기서 비 - 기하학적 개념을 처리 할 수있는 많은 코드를 작성하고자한다면, 이는 내가 다룰 내용을 넘어서고, 구조에 더 많은 데이터를 포함시키고 적절하게 테스트 할 수있는 것입니다. 원호가 시계 방향, 시계 반대 방향으로 항상 정의되어 있는지 알려주는 것도 없습니다. 그러나 방향이 잘 정의되어 있다면 문제는 쉽게 풀 수 있습니다. 이제는 길이가 0 인 호가 사용되지 않고 호가 2pi 라디안 이상으로 돌아 가지 않는다고 가정합니다. 호가 항상 시계 방향으로 정의된다고 가정 해 봅시다.

이제 쉽습니다. 두 개의 호가있는 두 원의 교차점 인 최대 두 점을 얻으십시오. 두 점에 대한 분석을 반복하십시오 ...

교차점의 각도를 가져옵니다. 아크 시작 각도가 끝 각도보다 작 으면 교차 각도가 두 각도에 있는지 또는 두 각도 사이에 있는지 테스트합니다. 그러나 시작 각도가 호의 끝 각도보다 크면 교차 각도가 시작 각도 또는 2pi 라디안 이하인지 확인하고 필요할 경우 테스트하여 두 가지 테스트를 수행합니다. 교차 각은 0 또는 그 이상이고 호의 끝 각도 이하입니다.아크가 시계 방향 또는 반 시계 방향으로 다음 코드는 단순히 시작 교환 및 종료 할 수 있다면 말할 아크 구조의 플래그가있는 경우

on_arc = false; 
if(start > end) 
{ 
    if(intersect >= start && intersect <= 2pi) 
     on_arc = true; 
    else if(intersect >= 0 && intersect <= end) 
     on_arc = true; 
} 
else if(start == end) 
    on_arc = true; // arc is the entire circle since we are not handling zero length arcs. 
else 
{ 
    if(intersect >= start && intersect <= end) 
     on_arc = true; 
} 

:

나는 의사 코드는 다음과 같이 보일 것이라고 생각 시험 전의 각도.

유용하지 않기 때문에> 2pi 호 아이디어를 피하십시오. 호를 계산하는 것은 무엇이든 기하학적 인 2D 개념이거나 2pi 제한을 가질 수있는 것입니다.

Answer 2

간단한 케이스로 시작하십시오. 두 원의 교차점을 어떻게 테스트합니까? 두 개의 원이 0 개 (너무 멀리 떨어져 있음), 정확히 하나 (만지기 만 함), 두 개의 장소 (겹침) 또는 모든 곳 (중심과 반경이 동일)에서 교차합니다.

하나 또는 두 개의 원을 계산하는 방법을 알아 내고 두 원 사이에 어느 한 점이 포함되어 있으면 알아낼 수 있습니다.

마지막 부분은 start이 (-pi, pi] (atan2()과 동일한 반환 범위)이되도록 범위를 정규화합니다.

while (start > M_PI) { start -= 2 * M_PI, end -= 2 * M_PI ; } 

그 다음은 start 및 end 사이에있는 교차 지점이 원 내에 있다는 각도 및 테스트를 찾기 위해 atan2()를 사용합니다.

성능을 향상시키고 성능을 더욱 향상 시키려면 교차 제품을 사용하여 trig 계산없이 유사한 테스트를 수행하는 방법이 있지만 특별한 경우가 필요합니다.