본문 바로가기

알고리즘/기하

알고리즘/기하 2021. 2. 26. 다각형 내부 점 판정 어떤 다각형과 점이 주어질 때, 점이 다각형 내부에 있는지 여부를 판별해 봅시다. 다음과 같이 다각형과 점들이 있다고 가정합시다. 각각의 점에서 시작하면서, x축에 평행한 반직선을 그어 봅시다. (반직선의 방향은 상관없습니다) 이 반직선이 다각형의 변과 홀수번 교차한다면, 이 점은 다각형 내부에 있습니다. 짝수번 교차한다면, 이 점은 다각형 외부에 있습니다. 선분과 반직선의 교차판정은 역시 CCW를 이용하면 편리합니다. 교차 판정시 다음과 같은 예외를 조심합시다. 1. 반직선이 다각형의 꼭짓점을 지날 때 꼭짓점 기준 위쪽에 있는 변/아래쪽에 있는 점 중 한가지 경우에만 교차한다고 판정하면 됩니다. 2. 반직선이 일부 변을 완전히 포함할 때 이 변과는 교차하지 않는다고 판정하면 됩니다. 시간복잡도는 다각형..
알고리즘/기하 2021. 2. 25. 컨벡스 헐 2차원 평면위에 점들이 있습니다. 이 점들 중 일부를 골라 볼록 다각형을 만들었을 때, 나머지 점들이 모두 다각형 안에 포함된다면 이 다각형을 컨벡스 헐(Convex Hull, 볼록 껍질)이라고 합니다. 볼록 껍질을 구해 봅시다. www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 좌표 평면 위에 다음과 같이 점들이 있다고 가정해 봅시다. 이 중 y좌표가 가장 작은 점, 같다면 x좌표가 가장 작은 점을 하나 찾습니다. (기준은 바뀌어도 됩니다..
알고리즘/기하 2021. 2. 22. CCW 세 점 \(A, B, C\)가 있습니다. 이 점들을 이용해 2개의 벡터 \(\overrightarrow{AB}, \overrightarrow{BC}\)를 만듭시다. 이 두 벡터의 외적값을 이용해 세 점에 대한 방향성을 알 수 있습니다. 1. \(\overrightarrow{AB} \times \overrightarrow{BC} > 0\) A - B - C는 좌회전합니다. \(\overrightarrow{AB}\)에 비교했을 때, \(\overrightarrow{BC}\)의 방향은 반시계 방향입니다. (CCW) 2. \(\overrightarrow{AB} \times \overrightarrow{BC} < 0\) A - B - C는 우회전합니다. \(\overrightarrow{AB}\)에 비교했을 때, ..

티스토리툴바