공간 데이타 구조 (Spatial Data Structures) 건국대학교 컴퓨터공학과 데이타베이스 연구실 97년 11월 한 기 준

래스터 구조 공간 좌표와 비공간 애트리뷰트를 포함하는 테이블 좌표값이 생략되고 애트리뷰트만을 포함하는 테이블 픽셀 값들로 구성된 사각형 배열

그리드 셀 래스터 데이타 구조 규칙적 tessellation 데이타 구조

완전 (FULL) 래스터 구조 래스터 모델의 배열구조 다중 데이타 레이어들의 중첩에 용이 많은 양의 저장 공간 차지 Run-length 엔코딩, Quadtree 등 각 그리드 레이어가 한 애트리뷰트를 표현하고, 애트리뷰트 값의 수는 정수 0  255로 제한(1바이트/픽셀) 픽셀의 순서는 주로 행-순서 구성(m bands(애트리뷰트)) (1) BSQ(Band Sequential) (2) BIL(Band Interleaved by Line) (3) BIP(Band Interleaved by Pixel) 이미지의 애트리뷰트 값이 애트리뷰트 테이블에 대한 포인터( > 1바이트)

애트리뷰트 분류화 단일 애트리뷰트 값들을 클래스들로 분류 데이타 디스플레이와 데이타 일반화(데이타 압축)를 위해 필요 클래스 경계를 정의하는 일련의 cutoff 값들을 사용 분류 과정 (1) 일정한 간격 : 선형 변환 사용 (2) 일정치 않은 간격 : 데이타의 감지(percentile) 분포와 관련된 cutoff 사용 방법 (1) 필요한 매개 변수를 갖는 변환 함수 사용 (2) 클래스 경계들을 갖는 테이블 또는 완전한 lookup 테이블 사용

RUN-LENGTH 엔코딩 이미지의 공간 사용을 줄일 수 있는 단순 데이타 구조 이미지 디스플레이와 이미지 처리에 효율적 (이웃 분석에는 부적합) 같은 값을 갖는 인접한 픽셀들을 결합하여 run으로써 숫자의 쌍으로 표현(run 길이, 애트리뷰트값)

래스터에 대한 스캔 순서 Run-length 엔코딩의 효율성에 영향 줌 (b), (d) > (a), (c)

Morton 순서와 Morton 좌표 반복적인 역 Z-모양 패턴 2n 2n 크기를 갖는 정사각형 이미지내의 픽셀들은 Morton 주소에 의해 공간적으로 인덱스됨 이진 단계에서 행과 열 좌표들을 bit-interleaving (행:1(01b), 열:3(11b)  7(0111b)

Region Quadtrees 블록들을 4개의 quadrant로 계속적인 분할에 근거한 계층적 데이타 구조 42+ 41+ 41+ 40+ 40+ 40+ 40+ 41+ 41 = 2*42+1* 41+0* 40 = 36 = 2104 블록들을 4개의 quadrant로 계속적인 분할에 근거한 계층적 데이타 구조

Octrees 입체들을 8개의 octant로 계속적인 분할에 근거한 계층적 데이타 구조

래스터내에서 선과 점 선 연결된 픽셀들의 체인에 의해 근사 점 단일 픽셀에 의해 근사

스파게티 구조 (검색용이 아니라 디스플레이용) 위치 좌표들이 각각의 기본 공간 객체 (점, 선, 다각형)와 관련됨 위상과 관련된 애트리뷰트가 없음 (검색용이 아니라 디스플레이용) 단점 데이타 중복 고비용 계산 우선권 (Fig 3-9)

위상 데이타 구조 (1/2) 공간 데이타베이스에 저장된 데이타에 부가적인 지능 제공 n차원 공간 상에서 점, 선, 다각형들 간의 논리적 연관성 (연결성, 방향성, 인접성, 포함성) 정보를 명시적으로 포함

위상 데이타 구조 (2/2)

위상 데이타 구조 사용 (1/2) 광범위한 공간 분석과 질의에 유용함 (1) which streets form the boundaries of Block1 ?

위상 데이타 구조 사용 (2/2) (2) How many street intersections are there in Block1 ?

위상 데이타 구조 연습 (1/2)

위상 데이타 구조 연습 (2/2) (1) Name the features that are boundaries of each district. (2) Which districts have bridges? Include bridges that are on the boundaries of districts. (3) Name the intersections that are entirely within districts (not on district boundaries).

지도를 위한 기본 위상 구조

운영중인 위상 구조

수치 직선 그래프(1/2) 1. DLG(Digital Line Graph) United States Geological Survey에서 개발한 지형학적 지도를 위한 수치 기호화(encoding) 점, 선, 영역 객체로 구성

수치 직선 그래프(2/2) 2. GBF/DIME(Geographic Base File/Dual Independent Map Encoding) US Census Bureau가 도시 영역들의 도로 선분들을 위한 데이타 구성 방법

공간 데이타 구조(1/5) 1. 비위상적 데이타 모델 SYMAP 소프트웨어의 다각형 모델 개체들은 정의 되지만 공간 관계는 기록되지 않음

공간 데이타 구조 (2/5) 2. 위상적 데이타 모델 라인 선분 구조 체인 모델 US Census Bureau의 DIME 포맷 라인 선분 구조 US Census Bureau의 DIME 포맷 체인 모델 ODYSSEY 시스템의 POLYVRT 구조

공간 데이타 구조 (3/5) 3. 연결성과 근접성

공간 데이타 구조 (4/5) 4. 다각형-선 위상

공간 데이타 구조 (5/5) 5. 링크 위상

DIME,DLG,TIGER 데이타 인코딩

ARC/INFO 데이타 요소

SDTS (Spatial Data Transfer Standard) 공간 형상: 실세계의 공간 개체와 그 객체적 표현 공간 객체: 실세계 공간 개체들을 수치적으로 표현하기 위해 사용 기하학적인 공간 객체 (G) point, line segment, string, arc, G-ring, interior area, G-polygon, pixel, grid cell 위상 구조의 공간 객체 (GT) node, line, chain, GT-ring, GT-polygon

VPF (Vector Product Format) 구성 테이블: 모든 공간 데이타는 기본적으로 테이블의 형태 디랙토리: 테이블을 범주화하여 하나의 디랙토리로 존재 인덱스: 레코드 접근, 테이블과 테이블의 연관성 고려 기본요소 node (entity node와 connected node), edge, face, text 위상 관계 레벨 3: 완전 위상 구조 (완전한 위상 구조를 가짐) 레벨 2: 평면 그래프 (완전한 intersect 포함) 레벨 1: 비평면 그래프 (완전한 intersect 포함하지 않음) 레벨 0: spaghetti (어떠한 위상 구조도 가지지 않음)

표면을 위한 벡터 구조 1. Triangulated Irregular Networks(TIN) 2. 다중-값 표현 표면상에서 불규칙하게 분산된 점들은 서로 이어져서 연결된 삼각형들의 네트워크를 형성 위상 구조가 명시적으로 저장될 수 있음 2. 다중-값 표현 완전한 3-차원 위상 모델은 다면체 tessellation을 사용하여 개발될 수