스티븐 (Steven)과 펠릭스 할림 (Felix Halim)의 "Competitive Programming 3"7 장을 읽었습니다. 여기에 두 개의 원이 교차하는 점을교차점과 해당 반경이 주어질 때 두 원의 중심을 찾는 방법은 무엇입니까?
및 반경에 해당하는도 주어진다 : 나는 그 그림에 주어진이 문제를 발견했다. 두 개의 서클 센터를 찾아야합니다. 그들은 솔루션 코드를 제공했습니다. 그러나 나는 그 배후의 기술을 이해하지 못했습니다. 주어진 코드 : 나는 많은 시간을 수색,하지만 난 찾을 수 없습니다
. 누구든지 기술을 설명 할 수 있습니까?
어쨌든,
하자 최초의 시각화 변수 d2 및 h : p1와 p2 사이의 거리의 제곱에 대한 
우리가 볼 수 있듯이, d2 스탠드. d = sqrt(d2)을 입력 해 보겠습니다. 그 다음 d^2 = d2.
피타고라스를 사용하는 경우 : r^2 = h^2 + d^2/4. 따라서 h^2 = r^2 - d^2/4. 그 수직
v := (p2 - p1)/d = (p2.x - p1.x, p2.y - p1.y)/d.
우리가 점으로 c1 표현할 수 지금
w := (p2.y - p1.y, p1.x - p2.x)/d
이다
유니 터리 (규범 = 1) p1 및 p2 합류 라인의 방향 벡터는 수직 방향 :
c1 = q + w*h = (p1 + p2)/2 + w*h,
w 때문에 7백45경1천5백15조5백36억9천1백36만3천2백10
는 1 규준을 가지며 h 정확하게 c1 및 q 사이의 거리이다. 따라서,
c1 = (p1.x + p2.x, p1.y + p2.y)/2 + (p2.y - p1.y, p1.x - p2.x)*h/d
h/d = sqrt(r^2 - d^2/4)/d = sqrt(r^2/d2 - 1/4)
.
노트 r이 d/2보다 항상 ge 것을 그림에서
.따라서 r^2 ≥ d^2/4 또는 (r/d)^2 ≥ 1/4이므로 det < 0이 없기 때문에 (동그라미가 교차하는 경우) 확인하지 않아도됩니다.
는 유도 위에서 실제로 왼쪽의 두 c1 용액, 도면 중 하나에서 p1p2에 청색 라인의 오른쪽에 하나, 다른 생산 라인을 상기한다. 사실, 이러한 방정식 포인트가 왼쪽 또는 오른쪽으로의 거짓말 여부를 우리가 +h 또는 -h, 우리는 설정에 대한 잘 알려진 기준 중 하나를 적용 할 수 있습니다 사용할지 여부를 결정하기 위해
c1 = q ± w*h = q + w*(±h)
에 해당 지시 된 세그먼트. 예를 들어, 우리는 +h에 대한 기호 및 -h에 대한 반대가됩니다 결정
| 1 p1.x p1.y |
D = | 1 p2.x p2.y | = (p2.x-p1.x)(c1.y-p1.y) - (p2.y-p1.y)(c1.x-p1.x)
| 1 c1.x c1.y |
의 부호를 계산할 수 있습니다. h의 값이 D < 0 인 경우 세그먼트 오른쪽에 c1이 표시되어 p1에서 p2 사이의 값입니다.
:) 사전에 감사 오른쪽 삼각형의 피타고라스을 적용합니다. 이것은 p1p2의 중점과 중심 사이의 거리를 제공합니다.
p1p2와 평행 한 다음 직교하는 단위 벡터로부터 오프셋 벡터를 쉽게 얻을 수 있습니다. 코드에 정의 된
수학적으로 설명해 주시겠습니까? 그것은 나를 위해 도움이 될 것입니다 :) – Murad
좋은 설명. 하지만 한 가지 질문이 있습니다. c1 = q + wh 또는 c1 = q - 어느 것이 맞습니까? 또 다른 질문은 두 번째 원의 중심을 얻으려면 두 번째 원의 반경이 필요합니까? – Murad
좋은 질문입니다. 내 두 번째 메모를보십시오 (두 번째 질문을 생각하게하십시오 ...) –
예, 두 번째 원의 반지름이 필요합니다. 그 이유는'p1'과'p2' 두 점만 알면 서클을 결정할 때 세 점이 필요하기 때문입니다. 따라서 더 이상의 정보 (반경)가 없으면 교차점이 같은 무한 원 (중심)이 있습니다. –