CCW 정렬 알고리즘

이 페이지에서 설명드리는 알고리즘은 3차원에서 원형태의 point loop 순서를 ccw로 정렬하는 알고리즘입니다.

point 좌표를 움직이는 것은 아니고 loop index를 ccw로 정렬하는 로직입니다. index가 ccw로 정렬이 되어 있지 않는 입력데이터를 ccw로 index를 조절한다고 보시면 될 것 같습니다.

ccw 정렬 알고리즘을 위해 알아야 할 개념은 두 벡터의 사이각 계산입니다.

2024.01.17 - [3D Algorithm] - 두 벡터 사이각(내적, 외적 활용)

두 벡터 사이각(내적, 외적 활용)

두 벡터의 각 계산 개념을 통해 쉽게 point loop를 ccw로 정렬할 수 있습니다.
- point loop를 대표 평면으로 projection: 3차원에서 계산하면 사이각 오류가 발생할 수 있어 2차원으로 정사영 해야 로직이 안정적입니다.)
- point loop 중심점 계산: cp
- point loop에서 index 1에 해당하는 점 선정: p1
- point loop에서 index n에 해당하는 점 선정: pn(n은 2 ~ loop 점의 총 개수)
- 벡터 p1 cp, pn cp의 각을 계산해서 각과 index n을 pair 형태로 list에 저장
- 벡터 p1 cp, pn+1 cp의 각을 계산해서 각과 index n+1을 pair 형태로 list에 저장

- 앞 단계를 loop 점의 마지막 index까지 진행
- pair list에서 각을 오름차순으로 정렬