오랜만에 Geometry 를 공부한김에.. 점과 선분과의 거리 구하는 방법을 정리해봤다..


일단 우리는 점과 직선과의 거리는 쉽게 구하는 방법을 알고있다..

직선 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));
    }


'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

  1. 라일락 2016.11.20 21:49 Permalink Modify/Delete Reply

    감사합니다! 많은 도움이 되었습니다

Leave a Comment


to Top