절단된 단면 위의 구획을 분류하기 위해 먼저 분할된 선들의 연결성을 확인 해 그룹화한다. 그룹화 방법의 개요는 다음과 같다. Fig. 3-12와 같이 절단된 단면 위의 한 선에 점 U를 놓는다. 다음은 각 선을 이동 경로라고 생각하고 점 U를 이동시킨다. 이동 중에 점 U가 선과 선의 교차점에 왔을 경우는 그동안 이동해왔던 선을 기준선으로 놓고 만나는 선들과의 반시계방향 각도를 구하여 각도가 가장 큰 선 1개를 선택하여 이동시킨다. 만약 만나는 선이 1개일 경우 에는 반시계방향 각도와 상관없이 그 선위로 점 U를 이동시킨다. 점 U가 원위 치로 돌아오면 그 이동 경로를 한 객체로 인식하고, 선 1~9까지 순차적으로 진 행하면 결과적으로 한 면을 구성하는 각 선의 그룹들(α: 1-2-3-10, β:
6-5-4-3-2-1-11, γ: 8-7-6, δ: 7-9-5)을 얻을 수 있다. 이 방법을 전산처리에 적용하기 위해 Fig. 3-13의 흐름도에 따라 진행하였다.
Fig. 3-12 점 U의 이동
흐름도에서 = 기호는 동일한 점을 새로 생성하는 것을 뜻하고, == 기호는 동 일한지 확인하는 것을 뜻한다. 1번 과정은 임의의 기준선을 선택하여 그 선의 시작 또는 끝에 시작점 A를 설정한다. 3번 과정은 2, 7, 11과 같이 점 B가 새로 생성될 때마다 점 B가 속해있는 선을 메모리에 저장하게 되고, 알고리즘이 종 료되었을 때 메모리에 저장된 선들이 구획을 구성하기 위한 그룹이 된다. 4번 과정인 점 B와 만나는 모든 선을 추출하는 방법은 기준선을 제외한 나머지 선 의 시작 또는 끝의 거리가 0(공차 0.001)이면 만나는 선으로 간주하였다. 추출 된 선이 1개인 것은 6번 과정으로 진행되고, 6번 과정에서 참(True)이면 점 B가 선 위를 이동하다가 시작점 A로 되돌아온 것을 뜻하고, 거짓(False)이면 교차하 는 선이 1개이므로 8번 과정의 반시계방향 각도 계산 필요 없이 3번 과정으로 진행한다. 8번 과정의 반시계방향 각도 계산은 계산하고자 하는 두 선의 바로 이전 매개변수에 해당하는 점을 생성하고, 그 점과 점 B 사이의 벡터를 각각 생성하며, 생성된 두 벡터를 내적 하여 각도를 계산한다. 하지만 Fig. 3-14과 같은 경우 기준 벡터가 D일 때 구하고자 하는 각도는 반시계방향으로 진행하 는 N 각도이지만 내적을 하면 항상 작은 값으로 계산되어 시계방향의 M 각도 가 계산된다. 따라서 외적을 하여 z 항의 값이 0보다 크거나 같으면 반시계방 향의 각도이므로 값을 그대로 사용하고, 0보다 작으면 시계방향의 각도이므로 360에서 값을 빼준다. 10번 단계의 거짓은 6번 단계와 동일하게 점 B가 시작점 A로 돌아오지 않은 것을 뜻하여 7번 단계로 진행하고, 참은 점 B가 시작점 A 로 되돌아온 것을 뜻하여 선 그룹을 저장한다. 만약 1번 단계에서 시작점 A를 선의 매개변수가 가장 작은 시작에 설정했다면 선의 매개변수가 가장 큰 끝에 시작점 A를 다시 설정하여 알고리즘을 다시 시작한다. 그 이유는 Fig. 3-15의 왼쪽 그림처럼 시작점 A를 U 점에 설정하면 시작점이 단면 중심을 기준으로 반시계방향으로 이동하여 구획 분할에 오류가 없지만, 오른쪽 그림처럼 W 점 에 설정하면 시계방향으로 이동하여 구획분할에 오류가 발생한다. 따라서 선의 시작과 끝에서 시작점 A를 모두 설정하여 오류가 발생한 선의 그룹까지 저장 한 후 3.7절에서 오류가 발생한 그룹은 삭제한다. 이와 같은 절차를 각 선 모두 적용하면 모든 구획의 선 그룹을 획득할 수 있다.
Fig. 3-14 두 벡터의 내적
Fig. 3-15 시작점의 진행방향에 따른 구획 분할 오류