🌐 გლობალური ბადეები: S2 და H3

ბადეების გვერდზე ვნახეთ, როგორ ხდება 2D უჯრის ერთ რიცხვად გადაქცევა. ახლა იგივე იდეა მთელ დედამიწაზე: დისკრეტული გლობალური ბადე (DGGS) ყოველ წერტილს ერთ უჯრის ID-ს აძლევს და სივრცითი კითხვები (ახლო წერტილები, რეგიონში მოხვედრა, აგრეგაცია) მთელ რიცხვებზე ოპერაციებად იქცევა. ამ ადგილას სრულიად ჩვეულებრივი ბაზა ან დახარისხებული სია გვყოფნის და სპეციალური სივრცითი ინდექსი აღარ გვჭირდება.

ორი ყველაზე ცნობილი სისტემაა:

	Geohash	S2 (Google)	H3 (Uber)
ფორმა	მართკუთხედი განედ-გრძედზე	„კვადრატი" კუბის წახნაგზე	ექვსკუთხედი (+12 ხუთკუთხედი) იკოსაედრზე
უჯრების დაშლა	32 შვილი	4 შვილი	7 შვილი
ინდექსი	Z-order	Hilbert	ჰიერარქიული, ბიტებად შეფუთული
მკაფიო მშობელ-შვილობა	კი (პრეფიქსი)	კი (ID-ს დიაპაზონი)	დაახლოებით (ზუსტად ერთმანეთში არ ეტევა)
პოლუსებთან დამახინჯება	დიდი	მცირე (≈ 2× ფართობი)	მცირე (≈ 2× ფართობი)

ეს გვერდი S2-ს ნულიდან ააგებს Python-ში და შეამოწმებს ბიბლიოთეკასთან, შემდეგ აჩვენებს, როგორ გამოიყურება სივრცითი ძებნა დახარისხებულ სიაში, და ბოლოს H3-ს შეხედავს ექსპერიმენტებით.

---

🎮 სცადეთ თქვენც: S2 უჯრის ID

აირჩიეთ ადგილი რუკაზე და გადაადგილეთ დონის სლაიდერი. ბიტებში ჩანს, როგორ „იზრდება" ID ყოველი დონით: წახნაგის 3 ბიტი, შემდეგ ორ-ორი ბიტი ყოველი დონისთვის, ბოლოს ერთი „1" და ნულები.

დაკვირვება

• დონის ზრდა ID-ს ბიტებს ბოლოში ამატებს, წინა ბიტები არ იცვლება. ამიტომ მშობლის ID მისი შვილების ID-ებში „ჩაწერილია" და ყველა შთამომავალი ერთ უწყვეტ რიცხვთა დიაპაზონშია (ბოლო ველი ეკრანზე).
• ლურჯი ხაზი უჯრების გავლის რიგია: Hilbert-ის მრუდი, რომელიც ყოველ დონეზე ბრუნავს და ირეკლავს, თუმცა ყოველ ახალ უჯრას წინას ეხებით აგრძელებს.
• უჯრის გვერდები სფეროზე დიდი წრეების რკალებია, ამიტომ განედ-გრძედის რუკაზე გამრუდებულად ჩანს (განსაკუთრებით დიდ უჯრებზე).

---

⚙️ როგორ აგებს S2 უჯრის ID-ს

წერტილი (lat, lng) რამდენიმე ბიჯით გადაიქცევა 64-ბიტიან რიცხვად:

1. სფერო → კუბი. (lat, lng) გადავიყვანოთ ერთეულოვან ვექტორად (x, y, z). კუბის ის წახნაგი, რომლის ღერძსაც ვექტორი ყველაზე ახლოა, არის face (0…5).
2. წახნაგზე კოორდინატები (u, v) ∈ [−1, 1] ცენტრალური (გნომონური) პროექციით: ვექტორს ვყოფთ მისი ყველაზე დიდი კომპონენტით.
3. კვადრატული გარდაქმნა u → s, v → t ∈ [0, 1]. უშუალოდ (u,v) ბადე კუთხეებში უჯრებს ბევრად პატარას ხდის, ვიდრე ცენტრში. კვადრატული ფორმულა ამას აკორექტირებს და უჯრების ფართობებს თითქმის გაუთანაბრებს.
4. დისკრეტიზაცია 30-ე დონეზე: i = ⌊s · 2³⁰⌋, j = ⌊t · 2³⁰⌋.
5. Hilbert-ის პოზიცია. i და j-ს ბიტებს ზევიდან ქვევით ვკითხულობთ. ყოველ დონეზე წყვილი (iₖ, jₖ) მიუთითებს, რომელი ოთხი ქვეკვადრატია, ხოლო მრუდის ორიენტაცია (გაცვლილია თუ არა i და j, შებრუნებულია თუ არა) გადაწყვეტს ამ ორბიტიან „ციფრს" და ცვლის ორიენტაციას შემდეგი დონისთვის. 60 ბიტი გამოდის.
6. შეფუთვა: ID = face(3 ბიტი) | pos(60 ბიტი) | 1. მარცხენა 2·(30 − დონე) ბიტი ნულებად რჩება და ბოლო „1" დონეს აღნიშნავს: ბოლო ერთი „1"-ის ადგილი გვეუბნება, რომელ დონეზე ვართ.

შედეგები (ყველა მარტივი ბიტური ოპერაცია):

• დონე = ბოლო „1"-ის ადგილით.
• მშობელი = ბოლო ბიტების ჩამოჭრა და ახალი „1"-ის დაყენება.
• შვილები = 4 ახალი „1"-ის ადგილი (ორი ბიტით ქვემოთ).
• შთამომავლების დიაპაზონი = [ID − lsb + 1, ID + lsb − 1]: უწყვეტი დიაპაზონი.

---

🐍 S2 ნულიდან Python-ში

import math

MAX_LEVEL = 30
SWAP, INVERT = 1, 2
POS_TO_IJ = ((0, 1, 3, 2), (0, 2, 3, 1), (3, 2, 0, 1), (3, 1, 0, 2))   # პოზიცია -> (i<<1 | j), ორიენტაციის მიხედვით
POS_TO_ORIENT = (SWAP, 0, 0, INVERT | SWAP)


def latlng_to_xyz(lat, lng):
    phi, theta = math.radians(lat), math.radians(lng)
    return (math.cos(theta) * math.cos(phi), math.sin(theta) * math.cos(phi), math.sin(phi))


def xyz_to_face_uv(p):
    face = max(range(3), key=lambda k: abs(p[k]))
    if p[face] < 0:
        face += 3
    x, y, z = p
    u, v = {0: (y / x, z / x), 1: (-x / y, z / y), 2: (-x / z, -y / z),
            3: (z / x, y / x), 4: (z / y, -x / y), 5: (-y / z, -x / z)}[face]
    return face, u, v


def face_uv_to_xyz(face, u, v):
    return {0: (1, u, v), 1: (-u, 1, v), 2: (-u, -v, 1),
            3: (-1, -v, -u), 4: (v, -1, -u), 5: (v, u, -1)}[face]


def uv_to_st(u):                     # კვადრატული პროექცია: უჯრების ფართობები თანაბარს უახლოვდება
    return 0.5 * math.sqrt(1 + 3 * u) if u >= 0 else 1 - 0.5 * math.sqrt(1 - 3 * u)


def st_to_uv(s):
    return (4 * s * s - 1) / 3 if s >= 0.5 else (1 - 4 * (1 - s) ** 2) / 3


def face_ij_to_id(face, i, j):
    """უჯრის ID 30-ე დონეზე: 3 ბიტი წახნაგი + 60 ბიტი Hilbert-ის პოზიცია + 1 ბოლო ბიტი."""
    orient = face & SWAP
    pos = 0
    for k in range(MAX_LEVEL - 1, -1, -1):
        ij = (((i >> k) & 1) << 1) | ((j >> k) & 1)
        digit = POS_TO_IJ[orient].index(ij)
        pos = (pos << 2) | digit
        orient ^= POS_TO_ORIENT[digit]
    return (face << 61) | (pos << 1) | 1


def latlng_to_cell(lat, lng, level=MAX_LEVEL):
    face, u, v = xyz_to_face_uv(latlng_to_xyz(lat, lng))
    n = 1 << MAX_LEVEL
    i = max(0, min(n - 1, int(uv_to_st(u) * n)))
    j = max(0, min(n - 1, int(uv_to_st(v) * n)))
    return parent(face_ij_to_id(face, i, j), level)


def lsb(cell):
    return cell & -cell


def level(cell):
    return MAX_LEVEL - ((lsb(cell).bit_length() - 1) >> 1)


def parent(cell, lvl):
    new = 1 << (2 * (MAX_LEVEL - lvl))
    return (cell & -new) | new


def children(cell):
    step = lsb(cell) >> 2
    return [cell - lsb(cell) + step * (2 * k + 1) for k in range(4)]


def range_min(cell):
    return cell - (lsb(cell) - 1)


def range_max(cell):
    return cell + (lsb(cell) - 1)


def cell_to_face_ij(cell):
    """(წახნაგი, i, j, ზომა): უჯრის მინიმალური კუთხე 30-ე დონის უჯრებში და გვერდის სიგრძე."""
    face = cell >> 61
    lvl = level(cell)
    orient = face & SWAP
    i = j = 0
    for k in range(lvl):
        digit = (cell >> (60 - 2 * k - 1)) & 3
        ij = POS_TO_IJ[orient][digit]
        i = (i << 1) | (ij >> 1)
        j = (j << 1) | (ij & 1)
        orient ^= POS_TO_ORIENT[digit]
    size = 1 << (MAX_LEVEL - lvl)
    return face, i * size, j * size, size


def cell_to_latlng(cell):
    """უჯრის ცენტრი."""
    face, i, j, size = cell_to_face_ij(cell)
    n = 1 << MAX_LEVEL
    return face_ij_point_to_latlng(face, (i + size / 2) / n, (j + size / 2) / n)


def face_ij_point_to_latlng(face, s, t):
    x, y, z = face_uv_to_xyz(face, st_to_uv(s), st_to_uv(t))
    return math.degrees(math.atan2(z, math.hypot(x, y))), math.degrees(math.atan2(y, x))


def cell_to_token(cell):
    return f'{cell:016x}'.rstrip('0') or '0'

გამოყენება

from s2cell import *

c = latlng_to_cell(41.72, 44.80, 17)                         # თბილისი, 17-ე დონე
print('ID:      ', c)
print('ტოკენი:  ', cell_to_token(c), ', დონე', level(c))
print('ბიტები:  ', format(c, '064b'))
print('ცენტრი:  ', tuple(round(v, 5) for v in cell_to_latlng(c)))
p = parent(c, 10)
print('მშობელი (10):', cell_to_token(p), '| შვილები:', [cell_to_token(x) for x in children(p)])
leaf = latlng_to_cell(41.72, 44.80, 30)
print('ფოთოლი უჯრის დიაპაზონშია:', range_min(c) <= leaf <= range_max(c))

ID:       4630840826652524544
ტოკენი:   40440d3254 , დონე 17
ბიტები:   0100000001000100000011010011001001010100000000000000000000000000
ცენტრი:   (41.72011, 44.80006)
მშობელი (10): 40440d | შვილები: ['40440c4', '40440cc', '40440d4', '40440dc']
ფოთოლი უჯრის დიაპაზონშია: True

შეამჩნიეთ, რომ მშობლის ტოკენი (40440d) ყველა შვილის პრეფიქსი არ არის (40440c4). ტოკენი არის ID-ს თექვსმეტობითი ჩანაწერი ბოლო ნულების გარეშე, მშობლისა და შვილის „1" კი სხვადასხვა ადგილას დგას. ამიტომ დიაპაზონებზე (range_min/range_max) მუშაობა სწორია და სტრიქონის პრეფიქსებზე არა.

შემოწმება

s2cell.py შედარებულია s2sphere-თან (S2-ის Python პორტი) 20 000 შემთხვევით წერტილზე შემთხვევით დონეზე (0…30): ID, ტოკენი, დონე, მშობელი, 4 შვილი, range_min/range_max და უჯრის ცენტრი ყველა შემთხვევაში ემთხვევა. JavaScript-ის ვერსია, რომელიც დემოშია, იგივე ID-ებს, ტოკენებს, დიაპაზონებს და შვილებს იძლევა 500 შემთხვევით შემოწმებაზე.

---

🔍 რეგიონის ძებნა დახარისხებულ სიაში

აი რატომ გვჭირდება ეს ყველაფერი. წერტილების ID-ებს ვახარისხებთ (ბაზაში ეს ჩვეულებრივი B-tree ინდექსია). კითხვა „რა მოხვდა 10 კმ-იან წრეში?" ასე იხსნება:

1. დავფაროთ წრე უჯრებით: დავიწყოთ 6 წახნაგით და ყოველი უჯრა ან გამოვტოვოთ (წრის გარეთაა), ან მთლიანად ავიღოთ (შიგნითაა), ან გავყოთ 4 შვილად. მესამე შემთხვევა მაქსიმალურ დონეზე ჩერდება.
2. ყოველი უჯრა არის ერთი უწყვეტი ID დიაპაზონი. მეზობელ დიაპაზონებს ვაერთებთ.
3. ყოველი დიაპაზონისთვის bisect-ით ვპოულობთ წერტილებს დახარისხებულ სიაში.
4. კანდიდატებზე ზუსტი მანძილით ვფილტრავთ, რადგან ფარვა ზედმეტსაც შეიცავს.

უჯრის „ქუდს" (შემომსაზღვრელ წრეს) კუთხეებიდან ცენტრამდე მაქსიმალური კუთხით ვითვლით. უჯრა ამოზნექილია (გვერდები დიდი წრის რკალებია), ამიტომ ცენტრიდან ყველაზე შორეული წერტილი მისი წვეროა.

import bisect
import math
import random
from s2cell import *


def angle(a, b):
    """ცენტრალური კუთხე ორ ერთეულოვან ვექტორს შორის (რადიანებში)."""
    d = a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
    return math.acos(max(-1.0, min(1.0, d)))


def unit(p):
    n = math.sqrt(sum(c * c for c in p))
    return tuple(c / n for c in p)


def cell_cap(cell):
    """უჯრის შემომსაზღვრელი „ქუდი": (ცენტრი ერთეულოვან ვექტორად, რადიუსი რადიანებში)."""
    face, i, j, size = cell_to_face_ij(cell)
    n = 1 << MAX_LEVEL
    pt = lambda a, b: unit(face_uv_to_xyz(face, st_to_uv(a / n), st_to_uv(b / n)))
    center = pt(i + size / 2, j + size / 2)
    corners = [pt(i, j), pt(i + size, j), pt(i, j + size), pt(i + size, j + size)]
    return center, max(angle(center, c) for c in corners)


def cover_circle(lat, lng, radius_m, max_level):
    """უჯრები, რომელთა გაერთიანება მთლიანად ფარავს წრეს (ზედმეტიც შეიძლება შეიცავდეს)."""
    c0 = latlng_to_xyz(lat, lng)
    r0 = radius_m / 6371008.8
    out, stack = [], [f << 61 | 1 << 60 for f in range(6)]      # 6 წახნაგი (0 დონე)
    while stack:
        cell = stack.pop()
        center, rad = cell_cap(cell)
        d = angle(c0, center)
        if d > r0 + rad:
            continue                                            # მთლიანად გარეთაა
        if d + rad <= r0 or level(cell) == max_level:
            out.append(cell)                                    # მთლიანად შიგნითაა, ან უკვე უმცირესია
        else:
            stack.extend(children(cell))
    return sorted(out)


def merge_ranges(cells):
    """მეზობელი უჯრების ID დიაპაზონები გავაერთიანოთ."""
    ranges = []
    for c in sorted(cells):
        lo, hi = range_min(c), range_max(c)
        if ranges and lo <= ranges[-1][1] + 2:
            ranges[-1][1] = max(ranges[-1][1], hi)
        else:
            ranges.append([lo, hi])
    return ranges

გამოყენება: 200 000 წერტილი, წრე 10 კმ

import bisect
import math
import random
from cover import *

rnd = random.Random(8)


def hav(a, b):
    la1, lo1, la2, lo2 = map(math.radians, (*a, *b))
    x = math.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * math.cos(la2) * math.sin((lo2 - lo1) / 2) ** 2
    return 2 * 6371008.8 * math.asin(math.sqrt(x))


pts = [(rnd.uniform(41.0, 43.6), rnd.uniform(40.0, 46.7)) for _ in range(200000)]
index = sorted((latlng_to_cell(la, lo), k) for k, (la, lo) in enumerate(pts))
keys = [c for c, _ in index]

q, R = (41.72, 44.80), 10000
for lvl in (8, 10, 12):
    cells = cover_circle(*q, R, lvl)
    ranges = merge_ranges(cells)
    cand = []
    for lo, hi in ranges:
        a, b = bisect.bisect_left(keys, lo), bisect.bisect_right(keys, hi)
        cand += [index[t][1] for t in range(a, b)]
    hits = [k for k in cand if hav(q, pts[k]) <= R]
    print(f'დონე {lvl:2}: უჯრა {len(cells):2}, დიაპაზონი {len(ranges):2}, კანდიდატი {len(cand):4}, პასუხი {len(hits)}')

brute = [k for k, p in enumerate(pts) if hav(q, p) <= R]
print('პირდაპირი ძებნა:', len(brute), ', ემთხვევა:', sorted(hits) == sorted(brute))

დონე  8: უჯრა  4, დიაპაზონი  2, კანდიდატი 5445, პასუხი 378
დონე 10: უჯრა 13, დიაპაზონი  2, კანდიდატი 1105, პასუხი 378
დონე 12: უჯრა 81, დიაპაზონი 12, კანდიდატი  543, პასუხი 378
პირდაპირი ძებნა: 378 , ემთხვევა: True

ყველა დონეზე პასუხი იგივეა და პირდაპირ ძებნას ემთხვევა, განსხვავდება მხოლოდ ფასი: გაუმჯობესებული ფარვა (უფრო ღრმა დონე) უფრო ნაკლებ კანდიდატს (200 000-დან 5 445 → 543) და მეტ დიაპაზონს (2 → 12) ნიშნავს, ანუ ნაკლებ წერტილს ვამოწმებთ ზუსტი მანძილით, მაგრამ მეტ ძებნას ვაკეთებთ სიაში. ბაზებში სწორედ ეს ბალანსია საჭირო, ძირითადად 8–20 დიაპაზონი კარგია.

---

🔷 H3: ექვსკუთხედები

H3 დედამიწას იკოსაედრზე (20 სამკუთხა წახნაგი) აპროეცირებს და თითოეულს ექვსკუთხედებით ფარავს. 16 რეზოლუცია (0…15) აქვს. ყოველი უჯრა მომდევნო რეზოლუციაზე 7 უჯრად იშლება (aperture 7). მცირე შეზღუდვა: იკოსაედრის 12 წვეროზე უჯრები ხუთკუთხედია (ეს სფეროს ტოპოლოგიური აუცილებლობაა).

ამ გვერდზე H3-ს თავად არ ვაგებთ (ეს ბევრად უფრო რთულია: იკოსაედრის 122 საბაზო უჯრა, ბრუნვები და ხუთკუთხედების გამონაკლისები). ვიყენებთ ოფიციალურ ბიბლიოთეკას h3 (4.5.0) და მისით ექსპერიმენტებს ვატარებთ.

import h3

cell = h3.latlng_to_cell(41.72, 44.80, 9)
print(cell, h3.get_resolution(cell), h3.cell_to_latlng(cell))
print('მეზობლები (1 რგოლი):', len(h3.grid_ring(cell, 1)), ', დისკი k=2:', len(h3.grid_disk(cell, 2)))
print('მშობელი (8):', h3.cell_to_parent(cell, 8), '| შვილები (10):', len(h3.cell_to_children(cell, 10)))
print('მანძილი ბადეზე:', h3.grid_distance(cell, h3.grid_ring(cell, 3)[0]))

892c2aa8603ffff 9 (41.71930003991853, 44.79979967667851)
მეზობლები (1 რგოლი): 6 , დისკი k=2: 19
მშობელი (8): 882c2aa861fffff | შვილები (10): 7
მანძილი ბადეზე: 3

რეზოლუციის ცხრილი (საშუალო ზომები, h3.average_hexagon_area):

რეზოლუცია	უჯრების რაოდენობა	საშუალო ფართობი	საშუალო გვერდი
0	122	4 357 449 კმ²	1 281 კმ
2	5 882	86 802 კმ²	183 კმ
4	288 122	1 770 კმ²	26.1 კმ
6	14 117 882	36.1 კმ²	3.73 კმ
8	691 776 122	0.737 კმ²	0.531 კმ
10	33 897 029 882	0.015 კმ²	0.076 კმ

---

⚖️ შედარება ცხრილებით

რამდენიმე ექსპერიმენტი ორივე სისტემაზე (კოდი დავალებებშია, ფართობების სტატისტიკა კი s2sphere-ის Cell.exact_area()-ით და h3.cell_area-თი გამოვთვალე):

თვისება	S2	H3
უჯრის ფართობის გავრცელება (მაქს/მინ)	≈ 2.06 (დონე 10, 3 000 შემთხვევითი უჯრა)	≈ 1.98 (რეზ. 5, 20 000 შემთხვევითი უჯრა)
მეზობლები	4 გვერდითი + 4 დიაგონალური	6, ყველა ერთგვაროვანი
მეზობლების მანძილი	თბილისში 17-ე დონეზე: 67–75 მ (გვერდითი), 112 მ (დიაგონალური)	თბილისში რეზ. 8: 899–945 მ ყველა 6
შვილები მშობელს მთლიანად ფარავს?	დიახ (ზუსტად 4)	არა, 7 შვილი მშობლის ფართობის 92.9%-ს ფარავს
ზრდა ერთი დონით	×4	×7

დასკვნა. S2 იდეალურია ბაზაში ინდექსისა და დიაპაზონების ძებნისთვის (მკაფიო იერარქია, უწყვეტი დიაპაზონები), H3 კი ანალიზისთვის: უჯრებს შორის მანძილი ერთგვაროვანია, ამიტომ „k რგოლი" ბუნებრივი მეზობლობაა, რაც აგრეგაციისა და ვიზუალიზაციისთვის მოსახერხებელია.

---

✍️ დავალებები

დავალება 1: S2 ძებნა და ბალანსი

გაუშვით ზემოთ მოცემული ძებნა max_level = 6, 8, 10, 12, 14-ზე. როგორ იცვლება დიაპაზონებისა და კანდიდატების რაოდენობა? რა დონეს აირჩევდით?

ამოხსნა

ციკლი იგივეა, ოღონდ for lvl in (6, 8, 10, 12, 14):

დონე  6: უჯრა  3, დიაპაზონი  1, კანდიდატი 48081, პასუხი 378
დონე  8: უჯრა  4, დიაპაზონი  2, კანდიდატი 5445, პასუხი 378
დონე 10: უჯრა 13, დიაპაზონი  2, კანდიდატი 1105, პასუხი 378
დონე 12: უჯრა 81, დიაპაზონი 12, კანდიდატი  543, პასუხი 378
დონე 14: უჯრა 379, დიაპაზონი 41, კანდიდატი  413, პასუხი 378

პასუხი ყოველთვის იგივეა (378), ფასი კი იცვლება: ყოველ ორ დონეზე კანდიდატები შესამჩნევად მცირდება (48 081 → 413), ხოლო დიაპაზონები იზრდება (1 → 41). დონე 12–14-ზე კანდიდატები პასუხს უკვე ახლოვდება (543 და 413 378-თან), ხოლო დონე 14-ზე 41 ცალკე ძებნა გვჭირდება. კონკრეტული არჩევანი ბაზაზეა დამოკიდებული: დიაპაზონული მოთხოვნა იაფია, ზუსტი გეომეტრიული შემოწმება ძვირი. ბევრ სისტემაში უჯრების რაოდენობას ზღვრავენ (მაგ. 8–20 უჯრა) და დონეს მის შესაბამისად ირჩევენ.

დავალება 2: aperture 7

საქართველოს შემომსაზღვრელი მართკუთხედი (41.0–43.6°N, 40.0–46.7°E) დაფარეთ H3 უჯრებით რეზოლუციებზე 3…8 და დათვალეთ, რამდენჯერ იზრდება რაოდენობა.

ამოხსნა

import h3

poly = h3.LatLngPoly([(41.0, 40.0), (41.0, 46.7), (43.6, 46.7), (43.6, 40.0)])
prev = None
for r in range(3, 9):
    n = len(h3.polygon_to_cells(poly, r))
    print(r, n, round(n / prev, 2) if prev else '-')
    prev = n

3 12 -
4 91 7.58
5 628 6.9
6 4394 7.0
7 30771 7.0
8 215411 7.0

ზრდა მკაფიოდ 7-ჯერ გვიახლოვდება (მცირე რეზოლუციებზე კიდეების ეფექტი ხარვეზს იძლევა). ეს ნიშნავს, რომ ყოველი რეზოლუცია ფართობს 7-ჯერ ამცირებს და რაოდენობას 7-ჯერ ზრდის. S2-ში იგივე ზრდა ×4-ია.

დავალება 3: ზუსტად ერთმანეთში ეტევა თუ არა?

აიღეთ H3 უჯრა რეზოლუციებზე 5, 7 და 9 (თბილისში), გააერთიანეთ მისი 7 შვილის პოლიგონი (shapely) და გამოთვალეთ: მშობლის რა წილია შვილებით დაფარული და შვილების ფართობის რა წილი გადის მშობლის გარეთ (ბრტყელი მიახლოება განედ-გრძედში, მცირე უჯრებისთვის საკმარისია). შეადარეთ S2-ს.

ამოხსნა

import h3
from shapely.geometry import Polygon
from shapely.ops import unary_union


def poly(c):
    return Polygon([(lng, lat) for lat, lng in h3.cell_to_boundary(c)])


for r in (5, 7, 9):
    p = h3.latlng_to_cell(41.72, 44.80, r)
    P = poly(p)
    ch = unary_union([poly(c) for c in h3.cell_to_children(p, r + 1)])
    print(r, len(h3.cell_to_children(p, r + 1)), round(P.intersection(ch).area / P.area, 3), round(ch.difference(P).area / ch.area, 3))

5 7 0.929 0.071
7 7 0.929 0.071
9 7 0.929 0.071

7 შვილი მშობლის 92.9%-ს ფარავს და შვილების ფართობის 7.1% მშობლის გარეთაა. ეს ყველა რეზოლუციაზე ერთნაირია, რადგან გეომეტრიული სურათი მასშტაბირებადია. S2-ში შვილები მშობელს ზუსტად ფარავენ (ოთხი ქვეკვადრატი), ამიტომ დიაპაზონული ძებნა სწორია. H3-ში cell_to_children განსაზღვრებით მაინც არსებობს, მაგრამ „ჩასმული" უჯრებით ზუსტი გეომეტრიული ფარვა არ გამოდის: მშობლის რეგიონზე მოთხოვნა ზუსტად ვერ გადაიქცევა შვილების მოთხოვნად.

დავალება 4: მეზობლების მანძილები

გამოთვალეთ თბილისის უჯრის მეზობლების ცენტრებამდე მანძილები: S2-ში 17-ე დონეზე (8 მეზობელი, წახნაგის შიგნით) და H3-ში რეზოლუცია 8-ზე (grid_ring(c, 1)).

ამოხსნა

import math
import h3
from s2cell import *


def hav(a, b):
    la1, lo1, la2, lo2 = map(math.radians, (*a, *b))
    x = math.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * math.cos(la2) * math.sin((lo2 - lo1) / 2) ** 2
    return 2 * 6371008.8 * math.asin(math.sqrt(x))


c = latlng_to_cell(41.72, 44.80, 17)
face, i, j, size = cell_to_face_ij(c)
n = 1 << MAX_LEVEL
center = cell_to_latlng(c)
ds = []
for di in (-1, 0, 1):
    for dj in (-1, 0, 1):
        if di or dj:
            ds.append(hav(center, face_ij_point_to_latlng(face, (i + size / 2 + di * size) / n, (j + size / 2 + dj * size) / n)))
print('S2:', sorted(round(d, 1) for d in ds))

h = h3.latlng_to_cell(41.72, 44.80, 8)
cen = h3.cell_to_latlng(h)
d = [hav(cen, h3.cell_to_latlng(x)) for x in h3.grid_ring(h, 1)]
print('H3:', len(d), round(min(d), 1), round(max(d), 1))

S2: [67.3, 67.3, 67.4, 67.4, 74.6, 74.6, 112.1, 112.1]
H3: 6 899.4 944.8

S2-ში მეზობლების მანძილი 67–112 მ-ს შორის იცვლება (გვერდითი და დიაგონალური, მათ შორის უჯრის არაკვადრატულობის გამო მცირე სხვაობა), H3-ში ყველა 6 მეზობელი ±3%-ის ფარგლებშია. ამიტომ H3-ზე „k რგოლი" ბუნებრივი სიახლოვის ზონაა, S2-ზე კი უჯრების რაოდენობით დაფარვა ფორმაში უფრო „კვადრატულია".