devmoon

선분 교차 판단 알고리즘은 2차원 평면 위에서 두 선분이 주어졌을 때, 두 선분이 서로 교차하는지 교차하지 않는지 판단하는 알고리즘이다. 이 알고리즘을 학습하기 위해서 선행되어야 하는 기하 알고리즘이 있는데, 그 개념은 CCW이다. CCW (Counter Clock Wise)는 2차원 평면 위에 놓인 3개의 점에 대해서 어떤 방향성이 있는지 알려주며 이 방향성 정보를 사용해 선분이 서로 교차하는지 판단하게 된다. CCW 먼저 3개의 점으로 나타낼 수 있는 방향성의 종류에는 무엇이 있는지 알아봐야 한다. 3개의 점을 임의의 순서대로 이어서 나온 방향성은 아래와 같이 1) 시계 방향 2) 반시계 방향 3) 일직선 3종류가 있을 수 있다. 그러면 이제 3개의 각 점에 대한 좌표정보가 주어지면 그 방향성을 어떻..