Geopoly 모듈
Geopoly 모듈 (The Geopoly Module)
1. 개요 (Overview)
Geopoly 모듈은 GeoJSON 표기법 (RFC-7946)을 사용해 2차원 다각형을 설명하는 R-Tree 확장의 대체 인터페이스예요. Geopoly에는 한 다각형이 다른 다각형 안에 포함되는지 또는 겹치는지 감지하는 함수, 다각형이 둘러싼 면적을 계산하는 함수, 다각형의 선형 변환을 수행하는 함수, 다각형을 SVG로 렌더링하는 함수, 그리고 다른 유사한 연산들이 포함돼요.
본문
Geopoly의 소스 코드는 amalgamation에 포함돼요. 하지만 구성 옵션과 사용 중인 특정 SQLite 버전에 따라 Geopoly 확장은 기본적으로 활성화되거나 활성화되지 않을 수 있어요. 빌드에 Geopoly가 활성화되도록 하려면 -DSQLITE_ENABLE_GEOPOLY=1 컴파일 타임 옵션을 추가하세요.
Geopoly는 "단순한" 다각형 - 즉 경계가 자기 자신과 교차하지 않는 다각형 - 에 대해 동작해요. 따라서 Geopoly는 직사각형 영역만 다룰 수 있는 R-Tree 확장의 기능을 확장해요. 반면 R-Tree 확장은 1에서 5 사이의 좌표 차원을 처리할 수 있지만, Geopoly는 2차원 도형에만 제한돼요.
Geopoly 모듈의 각 다각형은 임의의 수의 보조 데이터 필드와 연관될 수 있어요.
1.1. GeoJSON
GeoJSON 표준은 JSON을 사용해 지리공간 정보를 교환하기 위한 구문이에요. GeoJSON은 거의 모든 종류의 지리공간 콘텐츠를 설명할 수 있는 풍부한 표준이에요.
Geopoly 모듈은 GeoJSON의 작은 부분집합만 이해하지만, 중요한 부분집합이에요. 특히 GeoJSON은 단순한 다각형을 설명하는 정점(vertex)들의 JSON 배열을 이해해요.
다각형은 그 정점들로 정의돼요. 각 정점은 정점의 X와 Y 좌표인 두 개의 숫자 값의 JSON 배열이에요. 다각형은 이 정점들 중 적어도 네 개의 JSON 배열이며, 따라서 배열의 배열이에요. 배열의 첫 번째와 마지막 정점은 같아야 해요. 다각형은 오른손 법칙을 따르는데: 한 정점에서 다음 정점으로 선을 그을 때 선의 오른쪽 영역은 다각형 밖이고 왼쪽 영역은 다각형 안이에요. 다시 말해 정점들의 순 회전은 반시계 방향(counter-clockwise)이에요.
예를 들어 다음 JSON은 X 축 위에 있고 면적이 0.5인 이등변 삼각형을 설명해요:
[[0,0],[1,0],[0.5,1],[0,0]]
삼각형은 세 개의 정점을 가지지만, 삼각형의 GeoJSON 설명은 첫 번째와 마지막 정점이 중복되므로 4개의 정점을 가져요.
1.2. 이진 저장 형식 (Binary storage format)
내부적으로 Geopoly는 다각형을 이진 형식 - SQL BLOB - 으로 저장해요. 이진 형식의 세부 사항은 아래에 나와 있어요. 모든 Geopoly 인터페이스는 GeoJSON 형식이나 이진 형식 어느 쪽의 다각형도 받아들일 수 있어요.
2. Geopoly 확장 사용하기 (Using The Geopoly Extension)
geopoly 테이블은 다음과 같이 만들어져요:
CREATE VIRTUAL TABLE newtab USING geopoly(a,b,c);
위 문은 "newtab"이라는 이름의 새 geopoly 테이블을 만들어요. 모든 geopoly 테이블은 내장된 정수 "rowid" 컬럼과 그 테이블의 그 행과 연관된 다각형을 포함하는 "_shape" 컬럼을 포함해요. 위 예제는 또한 애플리케이션이 각 다각형과 연관지어야 할 추가 정보를 저장할 수 있는 "a", "b", "c"라는 세 개의 보조 데이터 컬럼을 정의해요. 보조 정보를 저장할 필요가 없으면 보조 컬럼 목록은 생략할 수 있어요.
일반 INSERT 문을 사용해 테이블에 새 다각형을 저장해요:
INSERT INTO newtab(_shape) VALUES('[[0,0],[1,0],[0.5,1],[0,0]]');
UPDATE와 DELETE 문도 비슷하게 작동해요.
2.1. 쿼리 (Queries)
인덱스된 지리공간 검색을 사용해 geopoly 테이블을 질의하려면 WHERE 절에서 geopoly_overlap() 또는 geopoly_within() 함수 중 하나를 부울 함수로 사용하고 "_shape" 컬럼을 그 함수의 첫 번째 인자로 사용해요. 예를 들어:
SELECT * FROM newtab WHERE geopoly_overlap(_shape, $query_polygon);
위 예제는 _shape가 $query_polygon 매개변수의 다각형과 겹치는 모든 행을 반환해요. geopoly_within() 함수도 비슷하게 작동하지만, _shape가 $query_polygon 안에 완전히 포함된 행만 반환해요.
WHERE 절에 꾸밈없는 geopoly_overlap() 또는 geopoly_within() 함수가 포함된 쿼리(그리고 DELETE 및 UPDATE 문도)는 기본 R*Tree 데이터 구조를 사용해 테이블의 행 부분집합만 조사하면 되는 빠른 조회를 수행해요. 조사되는 행 수는 물론 $query_polygon의 크기에 따라 달라져요. 큰 $query_polygon은 보통 작은 것보다 더 많은 행을 봐야 해요.
geopoly 테이블의 rowid에 대한 쿼리도 방대한 수의 행을 가진 테이블에서도 매우 빠르게 수행돼요. 하지만 보조 데이터 컬럼은 인덱스되지 않으므로, 보조 데이터 컬럼에 대한 쿼리는 전체 테이블 스캔을 수반해요.
3. 특수 함수 (Special Functions)
geopoly 모듈은 다각형을 다루는 데 유용한 여러 새로운 SQL 함수를 정의해요. 이 함수들의 모든 다각형 인자는 GeoJSON 형식이나 내부 이진 형식일 수 있어요.
3.1. geopoly_overlap(P1,P2) 함수
P1과 P2가 모두 다각형이면, geopoly_overlap(P1,P2) 함수는 P1과 P2 사이에 겹침이 있으면 0이 아닌 정수를 반환하고, P1과 P2가 완전히 분리되어 있으면 0을 반환해요. P1 또는 P2 중 하나가 다각형이 아니면 이 루틴은 NULL을 반환해요.
geopoly_overlap(P1,P2) 함수는 geopoly 가상 테이블이 WHERE 절에서 geopoly_overlap()을 부울 함수로 사용하는 쿼리를 최적화하기 위해 R*Tree 인덱스를 사용하는 방법을 알기 때문에 특별해요. geopoly_overlap(P1,P2)와 geopoly_within(P1,P2) 함수만 이 기능을 가져요.
3.2. geopoly_within(P1,P2) 함수
P1과 P2가 모두 다각형이면, geopoly_within(P1,P2) 함수는 P1이 P2 안에 완전히 포함되면 0이 아닌 정수를 반환하고, P1의 어떤 부분이라도 P2 밖에 있으면 0을 반환해요. P1과 P2가 같은 다각형이면 이 루틴은 0이 아닌 값을 반환해요. P1 또는 P2 중 하나가 다각형이 아니면 이 루틴은 NULL을 반환해요.
geopoly_within(P1,P2) 함수는 geopoly 가상 테이블이 WHERE 절에서 geopoly_within()을 부울 함수로 사용하는 쿼리를 최적화하기 위해 R*Tree 인덱스를 사용하는 방법을 알기 때문에 특별해요. geopoly_within(P1,P2)와 geopoly_overlap(P1,P2) 함수만 이 기능을 가져요.
3.3. geopoly_area(P) 함수
P가 다각형이면 geopoly_area(P)는 그 다각형이 둘러싼 면적을 반환해요. P가 다각형이 아니면 geopoly_area(P)는 NULL을 반환해요.
3.4. geopoly_blob(P) 함수
P가 다각형이면 geopoly_blob(P)는 그 다각형의 BLOB으로서의 이진 인코딩을 반환해요. P가 다각형이 아니면 geopoly_blob(P)는 NULL을 반환해요.
3.5. geopoly_json(P) 함수
P가 다각형이면 geopoly_json(P)는 그 다각형의 TEXT 문자열로서의 GeoJSON 표현을 반환해요. P가 다각형이 아니면 geopoly_json(P)는 NULL을 반환해요.
3.6. geopoly_svg(P,...) 함수
P가 다각형이면 geopoly_svg(P,...)는 그 다각형의 Scalable Vector Graphics (SVG) 표현인 텍스트 문자열을 반환해요. 인자가 하나보다 많으면 두 번째 및 이후 인자가 각 SVG 글리프에 속성으로 추가돼요. 예를 들어:
SELECT geopoly_svg($polygon,'class="poly"','style="fill:blue;"');
P가 다각형이 아니면 geopoly_svg(P,...)는 NULL을 반환해요.
geopoly는 원점이 왼쪽 아래에 있는 전통적인 오른손 직교 좌표계를 사용하는 반면, SVG는 원점이 왼쪽 위에 있는 왼손 좌표계를 사용한다는 점에 유의하세요. geopoly_svg() 루틴은 좌표계를 변환하려고 시도하지 않으므로 표시된 이미지는 미러 이미지로 그리고 회전되어 보여요. 그것이 바람직하지 않다면, geopoly_xform() 루틴을 사용해 다각형을 geopoly_svg()에 전달하기 전에 출력을 직교 좌표에서 SVG 좌표로 변환할 수 있어요.
3.7. geopoly_bbox(P)와 geopoly_group_bbox(P) 함수
P가 다각형이면 geopoly_bbox(P)는 P를 완전히 둘러싸는 가장 작은 (축 정렬된) 직사각형인 새 다각형을 반환해요. P가 다각형이 아니면 geopoly_bbox(P)는 NULL을 반환해요.
geopoly_group_bbox(P) 함수는 geopoly_bbox(P)의 집계 버전이에요. geopoly_group_bbox(P) 함수는 집계 동안 본 모든 P 값을 둘러쌀 가장 작은 직사각형을 반환해요.
3.8. geopoly_contains_point(P,X,Y) 함수
P가 다각형이면, 좌표 X,Y가 다각형 P의 안쪽이거나 경계 위에 있을 때에만 geopoly_contains_point(P,X,Y)는 0이 아닌 정수를 반환해요. P가 다각형이 아니면 geopoly_contains_point(P,X,Y)는 NULL을 반환해요.
3.9. geopoly_xform(P,A,B,C,D,E,F) 함수
geopoly_xform(P,A,B,C,D,E,F) 함수는 다각형 P의 아핀 변환(affine transformation)인 새 다각형을 반환하며, 변환은 값 A,B,C,D,E,F에 의해 정의돼요. P가 유효한 다각형이 아니면 이 루틴은 NULL을 반환해요.
변환은 다음 공식에 따라 다각형의 각 정점을 변환해요:
x1 = A*x0 + B*y0 + E
y1 = C*x0 + D*y0 + F
예를 들어 모양을 바꾸지 않고 다각형을 일정량 DX, DY만큼 이동하려면 다음을 사용해요:
geopoly_xform($polygon, 1, 0, 0, 1, $DX, $DY)
다각형을 점 0, 0 주위로 R라디안 회전하려면:
geopoly_xform($polygon, cos($R), sin($R), -sin($R), cos($R), 0, 0)
다각형을 뒤집는 변환은 정점의 순서가 뒤집히게 할 수 있다는 점에 유의하세요. 다시 말해 변환으로 인해 정점들이 반시계 방향 대신 시계 방향 순서로 순환할 수 있어요. 이는 변환 후 결과를 geopoly_ccw() 함수에 보내면 바로잡을 수 있어요.
3.10. geopoly_regular(X,Y,R,N) 함수
geopoly_regular(X,Y,R,N) 함수는 X,Y를 중심으로 하고 외접반지름(circumradius) R을 가진, N개의 변을 가진 볼록하고 단순하며 정칙(regular)이고 등변(equilateral)이며 등각(equiangular)인 다각형을 반환해요. 또는 R이 음수이거나 N이 3보다 작으면 함수는 NULL을 반환해요. N 값은 1000에서 제한되어 N 값이 1000보다 커도 루틴이 1000개 이상의 변을 가진 다각형을 절대 렌더링하지 않도록 해요.
예를 들어 다음 그래픽:
3 4 5 6 7 8 10 12 16 20
은 이 스크립트로 생성되었어요:
SELECT '<svg width="600" height="300">';
WITH t1(x,y,n,color) AS (VALUES
(100,100,3,'red'),
(200,100,4,'orange'),
(300,100,5,'green'),
(400,100,6,'blue'),
(500,100,7,'purple'),
(100,200,8,'red'),
(200,200,10,'orange'),
(300,200,12,'green'),
(400,200,16,'blue'),
(500,200,20,'purple')
)
SELECT
geopoly_svg(geopoly_regular(x,y,40,n),
printf('style="fill:none;stroke:%s;stroke-width:2"',color))
|| printf(' <text x="%d" y="%d" alignment-baseline="central" text-anchor="middle">%d</text>',x,y+6,n)
FROM t1;
SELECT '</svg>';
3.11. geopoly_ccw(J) 함수
geopoly_ccw(J) 함수는 반시계 방향(CCW) 회전을 가진 다각형 J를 반환해요.
RFC-7946은 다각형이 CCW 회전을 사용하도록 요구해요. 하지만 스펙은 또한 많은 레거시 GeoJSON 파일이 스펙을 따르지 않고 시계 방향(CW) 회전을 가진 다각형을 포함한다고 지적해요. geopoly_ccw() 함수는 레거시 GeoJSON 스크립트를 읽는 애플리케이션에 유용해요. geopoly_ccw()에 대한 입력이 올바르게 형식화된 다각형이면 변경이 이루어지지 않아요. 하지만 입력 다각형의 순환이 거꾸로면, geopoly_ccw()는 스펙에 따르고 Geopoly 모듈에서 올바르게 작동하도록 순환 순서를 뒤집어요.
4. 구현 세부 사항 (Implementation Details)
geopoly 모듈은 R-Tree 확장의 확장이에요. Geopoly는 R-Tree 확장과 같은 기본 로직과 섀도 테이블을 사용해요. Geopoly는 단지 다른 인터페이스를 제시하고 다각형 디코딩, 겹침, 포함을 계산하는 몇 가지 추가 로직을 제공해요.
4.1. 다각형의 이진 인코딩 (Binary Encoding of Polygons)
Geopoly는 모든 다각형을 내부적으로 이진 형식을 사용해 저장해요. 이진 다각형은 각 좌표의 각 차원이 32비트 부동 소수점 숫자인 좌표 쌍의 배열이 뒤따르는 4바이트 헤더로 구성돼요.
헤더의 첫 번째 바이트는 플래그 바이트예요. 플래그 바이트의 최하위 비트는 헤더 뒤에 오는 좌표 쌍이 big-endian인지 little-endian으로 저장되는지 결정해요. 최하위 비트 값 0은 big-endian을, 1은 little-endian을 의미해요. 헤더의 첫 번째 바이트의 다른 비트들은 향후 확장을 위해 예약되어 있어요.
헤더의 다음 세 바이트는 다각형의 정점 수를 big-endian 정수로 기록해요. 따라서 다각형당 약 1600만 개의 정점이라는 상한이 있어요.
헤더 뒤에는 좌표 쌍의 배열이 있어요. 각 좌표는 32비트 부동 소수점 숫자예요. 좌표에 32비트 부동 소수점 값을 사용한다는 것은 지구 표면의 어떤 점도 약 2.5미터의 해상도로 매핑될 수 있다는 뜻이에요. 물론 지도가 단일 대륙이나 국가로 제한되면 더 높은 해상도가 가능해요. geopoly 모듈의 좌표 해상도는 조석력으로 인한 지구 표면 점들의 일일 이동과 비슷한 크기라는 점에 유의하세요.
이진 형식의 좌표 목록에는 중복이 없어요. 마지막 좌표는 GeoJSON에서처럼 첫 번째 좌표의 반복이 아니에요. 따라서 GeoJSON 표현과 비교해 다각형의 이진 표현에는 항상 좌표 쌍이 하나 더 적어요.
4.2. 섀도 테이블 (Shadow Tables)
geopoly 모듈은 R-Tree 확장 위에 구축되며 같은 기본 섀도 테이블과 알고리즘을 사용해요. 인덱싱 목적을 위해 각 다각형은 섀도 테이블에서 직사각형 경계 상자로 표현돼요. 기본 R-Tree 구현은 경계 상자를 사용해 검색 공간을 제한해요. 그런 다음 geopoly_overlap() 및/또는 geopoly_within() 루틴이 정확한 답으로 검색을 더 정제해요.