선분이 원에 접하는 지 확인하는 방법은 무엇입니까?

Question

나는 (cx, cy)에 원점이있는 원을가집니다. 반경은 r입니다. 그런 다음 두 개의 점 : (x1, y1)과 (x2, y2)로 정의되는 선분이 있습니다. 선 세그먼트 (연장 선이 아님) 이 원에 접하는 지 확인하는 방법은 무엇입니까? 그리고 그렇다면 두 건의 접촉은 어디에서합니까?

지금까지의 상황 : 연장 된 라인에서 (cx, cy) 지점까지의 거리를 알아보십시오. 거리! = r이면 확실히 선 세그먼트는 원에 접하지 않습니다. 심지어 거리 == r이라면, 그들이 만나는 지점 을 찾아야합니다. 그런 다음 해당 점이 (x1, y1)과 (x2, y2) 사이의 세그먼트에 있는지 확인하십시오. '예'인 경우 세그먼트가 원에 접해 있고 터치 포인트 이 이미 계산됩니다. 이것은 효과가 있지만 너무 많은 수학을 포함합니다. 그리고 모두 float 또는 double 변수가 있습니다. 똑똑하고 빠른 알고리즘으로 동일한 결과를 얻을 수 있습니까?

감사 안부 정의상 프라 모드

Answer 1

는 접선이 반경 라인에 수직이어야한다. 아래 그림에서 빨간 선은 녹색 선 (중심점에서 접촉점까지)에 수직 인 경우에만 접선입니다. 당신이 ((x1,y1) 및 (x2,y2)로부터 계산) 접선 M의 기울기를 알고있는 경우

그래서 다음 반경 라인의 기울기는 -1/M입니다. 당신이

• 원
• 원
• 녹색 선

가 접점을 계산하기 쉽습니다의 기울기의 반경의 중심을 알고 감안할. 실제로 원의 반대편에 두 개의 가능한 접점이 있습니다.

두 가지 가능한 접촉 지점 중 하나가 선분에 있는지 확인하기 만하면됩니다.

Answer 2

아마도 f(x,y) = y-m*x-c이 선분 일 경우 |f(x1,y1)|/sqrt(1+m^2)은 (x1,y1)에서 선의 거리를 나타냅니다. 따라서 :

double m = (y2-y1)/(x2-x1);//slope 
double c = y1 - m*x1;//since (x1,y1) lies on the line f(x1,y1) is zero 
double d = abs(cy - m*cx - c)/sqrt(1+m*m);//distance 
if(d==r)//radius 
//Yeah its tangent and do whatever you want 
else 
//Nope 

그리고 두 번째 부분 인 의사 코드;

g1(x,y) = y+(1/m)*x-c1;//perpendicular line through (x1,y1) 
g2(x,y) = y+(1/m)*x-c2;//perpendicular line through (x2,y2) 
c1 = y1+(1/m)*x1; 
c2 = y2+(1/m)*x2; 
if(g1(cx,cy)*g2(cx,cy)<0)//condition if point lies between two lines.Here make sure the coeffecients of y and x are of same sign in g1 and g2 
//yes 
else 
//no 

Answer 3

수직면의 특이점이 항상 다루기 힘들 기 때문에 경사로 추론을 중지하는 것이 좋습니다.

p = p1 + t v where v = p2 - p1 

지금, v에 벡터 p1 - c 프로젝트 제로로 설정 파생 WRT t를 취할하고 신속하게 무한 라인에 포인트를 설명 t의 값에 대한 식을 가지고 : 대신 파라 메트릭 양식을 시도 접선 점이다 c에 가까운 :이 값은 0과 1 사이

(c - p1) dot v 
t = -------------- 
     v dot v 

경우, 탄젠트 포인트 p1 및 p2 사이이다. 이것은 매우 저렴한 계산입니다. 이 사실하면 하위 용어 c - p1 이미 위의 계산

(c - p1 - tv) dot (c - p1 - tv) ~= r^2 ? 

참고를 확인 반경 후속 할 수 있습니다.

원만 이동한다고 언급 했으므로 v dot v을 한 번 계산하여 저장할 수 있습니다.