점과 선분과의 거리
Problem Solving/Algorithm notes 2011.01.22 21:05
오랜만에 Geometry 를 공부한김에.. 점과 선분과의 거리 구하는 방법을 정리해봤다..
일단 우리는 점과 직선과의 거리는 쉽게 구하는 방법을 알고있다..
직선 ax + by + c = 0 과 점 (x1, y1) 과의 거리는
이렇게 구하면 되겠다..
그런데 점과 선분과의 거리를 구하고자 한다면 약간 까다롭다..
두 점 S, E 로 이루어진 선분과 점 P 와의 거리를 구한다고해보자..
P 에서 직선 SE 위로 수선의 발을 내리고 그 거리를 구하면 된다..
예)
그런데 경우에 따라서 수선의 발이 선분 위에서 만나지 않는 경우가 있다..
이 경우는 distance(P, S) 와 distance(P, E) 중 작은 값을 구하면 된다..
예)
자.. 그럼 수선의 발이 선분위에 존재하는 지 안하는지 어떻게 알 수 있을까..?
이는 벡터간의 내적을 통해서 알 수 있는데..
내적의 결과는 두 벡터간의 각도가
1) 90도보다 작으면 0보다 크고..
2) 딱 90도이면 0
3) 90도보다 크면 0보다 작은 값이 나온다..
따라서 수선의 발이 선분 위에 존재하려면
(벡터SP 내적 벡터SE) 와 (벡터EP 내적 벡터 SE) 가 서로 부호가 다르거나..
하나가 0 (수선의 발이 S 또는 E 에 떨어짐) 인 경우가 되겠다..
예)
자.. 그럼 수선의 길이는 거리는 어떻게 구할까..?
여러가지 방법이 있겠지만.. 삼각형의 넓이 공식을 이용해보자..
세 점 S, E, P 로 이루어진 삼각형의 넓이는
1) 밑변(선분SE) * 높이(수선의길이) / 2 ...이기도 하면서
2) | 벡터SE 외적 벡터SP | / 2 ... 이기도 하다..
=> 벡터 외적하면 절대값은 평행사변형의 넓이이고.. ccw(오른손법칙)에 의해서 음수가 나올수 있음에 주의!!
따라서 위의 내용을 정리해보면.. 다음과 같이 하면 되겠군..!!
일단 우리는 점과 직선과의 거리는 쉽게 구하는 방법을 알고있다..
직선 ax + by + c = 0 과 점 (x1, y1) 과의 거리는
distance = | (a*x1 + b*y1 + c) / sqrt(a^2 + b^2) |
이렇게 구하면 되겠다..
그런데 점과 선분과의 거리를 구하고자 한다면 약간 까다롭다..
두 점 S, E 로 이루어진 선분과 점 P 와의 거리를 구한다고해보자..
P 에서 직선 SE 위로 수선의 발을 내리고 그 거리를 구하면 된다..
예)
그런데 경우에 따라서 수선의 발이 선분 위에서 만나지 않는 경우가 있다..
이 경우는 distance(P, S) 와 distance(P, E) 중 작은 값을 구하면 된다..
예)
자.. 그럼 수선의 발이 선분위에 존재하는 지 안하는지 어떻게 알 수 있을까..?
이는 벡터간의 내적을 통해서 알 수 있는데..
내적의 결과는 두 벡터간의 각도가
1) 90도보다 작으면 0보다 크고..
2) 딱 90도이면 0
3) 90도보다 크면 0보다 작은 값이 나온다..
따라서 수선의 발이 선분 위에 존재하려면
(벡터SP 내적 벡터SE) 와 (벡터EP 내적 벡터 SE) 가 서로 부호가 다르거나..
하나가 0 (수선의 발이 S 또는 E 에 떨어짐) 인 경우가 되겠다..
예)
자.. 그럼 수선의 길이는 거리는 어떻게 구할까..?
여러가지 방법이 있겠지만.. 삼각형의 넓이 공식을 이용해보자..
세 점 S, E, P 로 이루어진 삼각형의 넓이는
1) 밑변(선분SE) * 높이(수선의길이) / 2 ...이기도 하면서
2) | 벡터SE 외적 벡터SP | / 2 ... 이기도 하다..
=> 벡터 외적하면 절대값은 평행사변형의 넓이이고.. ccw(오른손법칙)에 의해서 음수가 나올수 있음에 주의!!
따라서 위의 내용을 정리해보면.. 다음과 같이 하면 되겠군..!!
if (dot_product(sp, se) * dot_product(ep, se) <= 0) {
/* foot exists */
return fabs(cross_product(sp, se)) / get_dist(s, e);
}
else {
return min(get_dist(s, p), get_dist(e, p));
}
/* foot exists */
return fabs(cross_product(sp, se)) / get_dist(s, e);
}
else {
return min(get_dist(s, p), get_dist(e, p));
}
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Inversion Count (0) | 2016.01.31 |
|---|---|
| The Tower of Hanoi (0) | 2011.08.28 |
| Gaussian Prime (0) | 2011.04.03 |
| Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유.. (2) | 2011.03.02 |
| Linear Diophantine Equation (0) | 2011.01.25 |
| 점과 선분과의 거리 (2) | 2011.01.22 |
| Articulation Points (0) | 2010.11.21 |
| Konig's Theorem (0) | 2010.08.01 |
| Modular Multiplicative Inverse (0) | 2010.06.13 |
| Primality Testing (Miller-Rabin) (0) | 2010.03.23 |
| Modular Exponentiation (Big Mod) (2) | 2010.02.19 |
Comments
감사합니다! 많은 도움이 되었습니다
도움이 되었다니 다행입니다.. 열공하세요 ^^