Blog Content

  • CCW 판별법 (Java)

    Category 개발레시피/└ Algorithm on 2018. 3. 4. 20:53

    세 점이 있을 때 반시계 방향으로 움직이는지, 시계방향으로 움직이는지 찾는 알고리즘이다.2차원 좌표에 세 점 A,B,C가 있다고 가정했을 때AB 기준으로 C가 왼쪽에 위치해있다고 했을 때벡터의 외적을 계산하면 d[AB, AC] > 0 이 나오고,AB기준으로 C가 오른쪽에 위치해있다고 했을 때d[AB, AC] < 0이 나온다. 즉, 벡터의 외적의 값이 0 초과이면 ccw(반시계방향),0미만이면 cw(시계방향), 0이면 일직선상에 존재한다. 1234567891011121314151617181920212223242526272829303132333435363738394041import java.io.BufferedReader;import java.io.InputStreamReader; /*2차원 좌표 평면 위에..

    Read more
  • [기하/개념] 볼록 껍질 (Convex Hull)

    Category 개발레시피/└ Algorithm on 2017. 12. 1. 20:16

    1. list[] 에 있는 점들 중 가장 작은 것을 찾아서 기준점으로 선정한다.2. 기준점 기준으로 각각의 점들을 반시계 방향으로 기준점과 각도 순서대로 정렬한다.3. 점들을 하나씩 보면서 볼록껍질에 포함시킬지 말지를 결정한다.스택을 하나 만들고, 이 스택에는 점의 번호를 넣어주는데 스택 사이즈가 한개밖에 없으면일단 지금 잡고 있는 점을 넣는다.스택에 점이 두 개 이상이면 비교를 한다.점 두개를 기준으로 다른 점을 봤을 때 CCW를 하는데, 이 때 반시계 방향에 있으면 만족하므로 스택에 넣어준다.그리고나서 또 스택의 두개를 빼서 두 점 기준으로 다음 점을 CCW 한다.만약 반시계 방향에 없다면 오목하다는 의미이므로 만족하지 않는다. 따라서 이럴 경우에는 스택에서 빼준다.이렇게 계속 반복해준다. 12345..

    Read more