서로 다른 네 점으로 이루어진 다각형과 한 점이 있다
이 한 점이 다각형의 내부에 있는지 외부에 있는지 판별하라
(단 각점의 좌표는 임의의 좌표이며 서로 다름. 과정을 상세히 서술할 것)
우리 모두 웃어봐요! 우리들의 이야기로.
서로 다른 네 점으로 이루어진 다각형과 한 점이 있다
이 한 점이 다각형의 내부에 있는지 외부에 있는지 판별하라
(단 각점의 좌표는 임의의 좌표이며 서로 다름. 과정을 상세히 서술할 것)
잘 될려나 모르겠는데요 ㅎㅎ
평면에서 다각형의 네 점중 두 점씩을 뽑아내어 직선 두개를 만듭니다.
1--------2
| @@@@|
| @@@@|
3--------4
대략 이렇게 생겼다면 붙어있는 점끼리 뽑아내는 거죠
목표는 @에 점이 위치하는 겁니다.
첫번째 : 1과 2를 지나는 직선과 3과 4를 지나는 직선을 찾아냅니다.
그리고 다른 한 점과 비교하세요.
두 직선의 (위/가운데/아래) 중 어디에 있는가!
두번째 : 1과3을 지나는 직선과 2와4를 지나는 직선을 찾아냅니다.
다른 한점의 위치를 위의 방법처럼 찾습니다.
두 직선의 (왼쪽/가운데/오른쪽) 중 어디에 있는가!
그래서 (가운데, 가운데) 가 된다면 내부, 그 외에는 전부 외부겠지요.
ps. 하다가 직선위의 점이라는 결론이 나온다면 그것은 경계선에
있는 겁니다.
알고리즘에 이런 문제 종종 나오죠 ^^;;;
원래 본 문제는 점 5개만 줍니다
그리고 점 4개를 가지고 우선!! 다각형인지 아닌지 판별해야됩니다
(N 이런 도형이 있을 수 있으므로)
네개의 점이 이루는 선분 중에서 두개의 직선으로부터 내각을 구하죠 (두 직선의 기울기와 sin, cos등을 이용해서...)
각각의 선분으로부터 내각을 구한두 합해서 360도인지 확인합니다
그 다음으로 다각형의 내부의 한점과 주어진 한점을 잇는 직선을 만듭니다 (두 점을 알면 직선을 그릴수 있습니다)
그래서 그린 직선과 다각형의 각 선분과 교차점이 있나 없나 판별합니다
(내부에 있다면 어느 한 직선에 걸릴테니까요)
다각형 내부의 한점을 구하는 방법은 대각선의 교차점입니다
마주보는 두점을 잇는 직선을 두개 구해서 교차점이 생기면 내부에 있는 것이죠 ^^
Comment ' 10