CCW를 이용한 선분 교차 판정 알고리즘 배우기

1. 선분 교차 기본형 두 선분 (A,B)와 (C,D)가 주어질때 두 선분이 교차하는가? 교차하지 않는가? 직선의 방정식 구해서.. 교점을 구해보고.. 기울기 비교해보는 등 여러 방법을 사용해볼 수 있지만.. 가장 일반적인 방법은 CCW를 이용하는 것이다. https://deepdata.tistory.com/955 기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기 https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이 deepdata.tistory.com 다음..

• format_list_bulleted 기하학
• · 2023. 9. 12.
• textsms

볼록 껍질(convex hull)구하는 monotone chain 알고리즘 배우기

1. 모노톤 체인(monotone chain) 볼록 껍질(convex hull)을 구하는 두번째 알고리즘 graham scan과는 다르게 점을 정렬하는 방법이 다르고, 아래쪽 껍질과 위쪽 껍질을 구하여 둘을 합치는 방식으로 구한다 구체적으로는... 1) 주어진 점을 x좌표 순으로 오름차순 정렬하고 x좌표가 같으면 y좌표를 기준으로 오름차순 정렬 2) 첫번째 점과 두번째 점을 스택에 넣는다. 3) 이제 순서대로 세번째 점부터 순회하면서 조건에 맞으면 스택에 차례대로 집어 넣는다. 3-1) 스택의 -2번, -1번 점과 새로 추가하려는 점이 CW를 이루면 스택에 집어 넣는다. 3-2) CW를 이루지 않는다면 CW가 될 때까지 스택의 마지막 점을 pop한다 4) 마지막에 스택에 남아있는 점들이 볼록 껍질의 윗 ..

• format_list_bulleted 기하학
• · 2023. 9. 8.
• textsms

볼록 껍질(convex hull) 구하는 graham scan 알고리즘 배우기

1. 볼록 껍질(convex hull) 주어진 모든 점을 포함하는 최소 크기의 볼록 집합 여기서 볼록 집합(convex)이라는 것은 집합 내에 임의의 두 점을 잡아 선분을 그릴때, 해당 선분이 집합 내에 포함되는 집합이다. 아래 그림에서 왼쪽은 볼록 집합이지만 오른쪽은 볼록 집합이 아니다. 직관적으로는 무한한 크기의 고무줄(검은색)을 주어진 모든 점을 둘러싸도록 크게 당긴 다음, 손을 놓았을때 점에 탁 걸리면서 만들어지는 도형(파란색) 2. 그라함 스캔(graham scan) 볼록 껍질을 구하는 대표적인 알고리즘 중 하나 1) 주어진 점을 각도 순으로 정렬 점을 각도 순으로 정렬한다는 말은... 기준점을 잡고 기준점과 점들을 연결한 선분과 x축의 양의 방향이 이루는 각도가 작은 것에서 큰 순으로 번호를 ..

• format_list_bulleted 기하학
• · 2023. 9. 7.
• textsms

기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기

https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이용된다는 뜻이다. 우선 이 게시글에서 rebro.kr https://gaussian37.github.io/math-algorithm-ccw/ CCW(counter clockwise) gaussian37's blog gaussian37.github.io https://snowfleur.tistory.com/98 [알고리즘] CCW(Counter Clock Wise) 알고리즘 개요 및 소개 CCW( Counter Clock Wise) 알..

• format_list_bulleted 기하학
• · 2023. 8. 5.
• textsms