A5 v1.0: 지구 격자와 셀 ID를 고정합니다

AI 요약

A5는 지구상의 위치와 선, 다각형 영역을 오각형 셀 하나 또는 여러 개로 표현하는 이산 전역 격자 시스템(Discrete Global Grid System, DGGS)입니다. 셀마다 64비트 정수 ID를 부여합니다. 첫 발표 뒤 18개월 동안 라이브러리와 도구가 늘었고, v1.0에서는 격자 구조와 셀 ID 정의를 고정해 앞으로 애플리케이션과 데이터베이스, 작업 흐름이 같은 ID를 계속 참조하도록 했습니다. DuckDB와 R 구현체도 생겼으며 공식 문서에는 이 언어들과 TypeScript, Rust, Python의 코드와 API를 싣습니다.

압축 데이터 처리

셀 모음인 커버링(covering)에 합집합, 교집합, 차집합을 적용하고 포함 여부와 겹침을 판정하는 기능, 셀 수와 면적을 계산하는 기능을 추가했습니다. 이전에는 연산 전에 압축을 풀어야 했지만, 이제 압축 상태를 유지하면서 수십억 개 셀을 처리할 수 있다고 설명합니다. 예를 들어 데이터베이스 질의로 얻은 커버링을 합친 뒤 다각형이나 구면 캡과 교차시키고, 결과에 따라 지점 모음을 필터링할 수 있습니다.

계층과 면적

오각형을 더 작은 오각형으로 정확히 나누는 계층은 기하학적으로 만들 수 없습니다. 그래서 A5의 계층은 논리적이며 공간적으로는 근사치입니다. 새 cellToSubcells 함수는 셀 중심점을 기준으로 해당 셀을 덮는 하위 셀 모음을 계산합니다. 기존 cellToChildren보다 느리지만 올바른 커버링을 만듭니다. 역방향 함수인 cellToSupercell도 추가했습니다.

A5는 같은 해상도의 모든 셀이 같은 면적을 갖도록 설계했습니다. v1.0에서는 모든 해상도에서 셀의 오각형 토폴로지도 같게 했습니다. 여기서 토폴로지는 셀마다 변이 다섯 개라는 메시 구조를 뜻합니다. 구에 육각형만으로 격자를 만들 수 없어서 육각형 기반 시스템에는 오각형 12개가 들어가며, 이 셀들은 육각형과 면적이 달라질 수 있다고 A5는 설명합니다.

인덱싱과 성능

v1.0의 주요 변경은 teohedral 공간 채움 곡선(space-filling curve)입니다. 이 곡선은 지구 전체를 지나면서 자기 자신과 교차하지 않고, 셀을 공간적으로 가까운 순서로 묶습니다. 다각형을 셀로 채울 때 경계가 곡선 위의 구분점으로 작동하므로, 내부 셀을 찾기 위한 비용 큰 flood fill을 하지 않아도 된다고 설명합니다. 이 곡선을 도입하면서 셀 ID가 바뀌어 기존 사용자는 업그레이드 안내에 따라 데이터를 이전해야 합니다.

벤치마크는 영국, 프랑스, 브라질, 미국, 호주 경계를 해상도별로 채우는 호출을 Apple M1 Pro에서 측정했습니다. A5 1.0.0과 0.10.1은 Rust 네이티브 라이브러리, H3는 C 라이브러리와 Python NumPy API, S2는 C++ 라이브러리와 Python 바인딩으로 비교했습니다. 반복 실행 중 가장 빠른 시간을 사용했고, 2초가 넘는 호출은 한 번만 측정했습니다. A5는 6초, 다른 라이브러리는 1분을 넘기거나 셀이 10억 개를 넘으면 중단했습니다. 작성자는 이전 A5와 현재 H3가 백만 셀을 넘는 다각형 채우기에서 실용적으로 느려지는 반면, 새 A5와 S2는 10억 셀까지 처리한다고 보고합니다. S2도 자기 교차가 없는 Hilbert 곡선을 사용하며, H3 인덱스 순서에는 같은 성질이 없다고 설명합니다.

생태계

FIRMS Explorer는 2000년 이후 전 세계 화재 감지 6억 3,100만 건을 A5로 집계한 사례입니다. GeoParquet 도구로 데이터를 집계하고 Portolan으로 호스팅하며 a5-js와 deck.gl의 A5Layer로 시각화했습니다. A5 구현체는 DuckDB, R, QGIS 등에도 있습니다. 작성자는 A5의 설계를 자세히 설명하고 다른 DGGS와 비교하는 논문을 준비 중이라고 밝혔습니다.

Lobsters 반응

• @fanf — 오각형 격자가 어떻게 작동하는지 궁금했습니다. 소개 글은 오각형의 면적이 같다고 말하고 예쁜 그림을 연결하지만 설명은 없습니다. 블로그에서 "모든 해상도의 셀이 같은 오각형 토폴로지"라고 했는데, 여기서 토폴로지가 추상적인 변형 가능성을 뜻하는지, 실제로 기하학적 합동을 뜻하는지 궁금합니다. 공간 채움 곡선도 궁금합니다. "teohedral"이라는 용어는 있는데, 홈페이지 메뉴에서 기술 설명 문서를 찾지 못했습니다. 정십이면체 타일링을 구에 투영해도 오각형이 어떻게 합동을 유지하나요?
  • @pheelicks — 여기서 토폴로지는 그래픽에서 사각형 토폴로지나 삼각형 토폴로지를 말할 때처럼 메시 구조를 뜻합니다. A5에서 단일 토폴로지 t는 모든 셀의 변이 다섯 개라는 뜻입니다. 타일링 예제에서 dodecahedron을 선택하면 합동인 오각형을 볼 수 있습니다. project를 선택해 구로 투영하면 셀은 더 이상 정확히 합동이 아닙니다. 기하학적으로 불가능하기 때문입니다. 다만 다른 프로젝트인 S2처럼 정육면체를 투영할 때보다 모양을 더 잘 보존합니다. 곡선의 구성 원리를 다룰 논문을 준비 중이며, 핵심에는 L-system이 있습니다. lattice 예제에서 작동 방식을 짐작할 수 있습니다.
• @chrswk — 이번 릴리스 자체에 할 말은 없지만 Geomob 팟캐스트 312회, Felix Palmer의 A5 Grid System 편에서 A5를 들었습니다.
• @zem — 삼각형 메시의 어떤 문제가 다른 셀 시스템을 만들게 하나요?
  • @pheelicks — 삼각형은 꼭짓점 이웃이 9개이고 변을 공유하는 이웃은 3개라 컨볼루션이나 흐름 모델링에서 이웃을 다루기 복잡합니다. 도형 중에서는 채움 효율도 가장 낮습니다.
• @wink — H3도 처음 들었는데, 왜 육각형이 아니라 오각형을 쓰는지 궁금했습니다.
  • @fanf — 구를 육각형만으로 타일링할 수 없습니다.
  • @wink — 오늘 처음 알았습니다. 게임 엔진처럼 작은 지도만 다뤄 봐서 행성 규모 격자에서는 예상하지 못했습니다.
  • @pheelicks — 육각형 기반 시스템은 이미 여럿 있으며 비슷한 투영으로 면적을 같게 만들 수도 있습니다. 다만 육각형 시스템에는 반드시 오각형 12개가 들어가고 이 셀들은 다른 셀과 면적이 같지 않습니다. A5는 해상도가 한 단계 올라갈 때 셀 수가 4배가 되는 aperture 4 구조이며, H3는 aperture 7이라 선택 가능한 해상도 단계가 더 적습니다. 육각형도 다른 aperture를 쓸 수 있지만 계층을 자연스럽게 구성하기는 어렵습니다. 오각형은 설계 선택 중 하나이지 시스템의 나머지 기능을 성립시키는 필수 조건은 아닙니다.
  • @olegkovalov — 답이 여기 있는 것 같지만 이해하지 못하겠습니다.
  • @wink — 링크를 보고도 셀 모양과 면적 편차가 어떤 관계인지 모르겠습니다. 면적 편차가 없는 육각형 격자도 가능할 것 같은데, 그건 H3와 다른 시스템인가요?
  • @pheelicks — 맞습니다. 면적 편차는 투영 방식에서 비롯됩니다. H3는 단순하고 빠른 gnomonic 투영을 선택했지만 면적을 보존하지 않습니다.
  • @fs111 — H3는 원래 Uber에서 나왔던 것 같습니다.

원문: A5 블로그 / 번역·요약: Trawling