Przetwarzanie OpenStreetMap na systemie wbudowanym #3 - Kodowanie formatu .ltd

[kronikary]

Po przedstawieniu w poprzedniej części artykułu struktury proponowanego formatu map, rozpoczynamy tworzenie kodera formatu. Naszym zadaniem jest przeprasowanie map w formacie .osm, a następnie zakodowanie interesujących nas informacji do formatu .ltd. Zadanie jest o tyle utrudnione, że musimy uwzględnić i utworzyć mapy kafelkowe. Jest to wbrew pozorom nie tak łatwe zadanie. Dlaczego?

Ten artykuł bierze udział w naszym konkursie! 🔥
Na zwycięzców czekają karty podarunkowe Allegro, m.in.: 2000 zł, 1000 zł i 500 zł.

Potrafisz napisać podobny poradnik? Opublikuj go na forum i zgłoś się do konkursu!
Czekamy na ciekawe teksty związane z elektroniką i programowaniem. Sprawdź szczegóły »

Kodowanie .osm do .ltd

Weźmy ponownie mapę polski i zaznaczmy jej obszar kwadratem. Następnie podzielmy ten kwadrat na dwie części. W taki sposób otrzymaliśmy koordynaty kafelków mapy składającej się teraz z dwóch części. Skupmy się na jednej z nich. Znamy współrzędne geograficzne, które zakreślają ten obszar. To co teraz musimy zrobić to wyeksportować wszystkie obiekty, które znajdują się w tym obszarze. Aby to zrobić musimy sprawdzać pozycję każdego z obiektów i eksportować go, jeżeli spełnia nasze kryterium. Wiemy, że mapy polski (o rozmiarze 25GB) nie jesteśmy w stanie otworzyć prostym parserem XML, zatem wykorzystajmy jakieś API do „cięcia” map. Dla przykładu wykorzystałem Osmosis. Wykorzystujemy funkcję "--bounding-box", określamy obszar i czekamy, aż zostanie wyeksportowany. Czekamy niecałe 20 minut, a to dopiero jeden kafelek. Co jeżeli mamy 8 poziomów zbliżenia?

W najlepszym przypadku będziemy czekać 1747600 minut, aż wszystkie kafelki zostaną wyeksportowane. Jest to około 1 213 dni. Co możemy zrobić z tym fantem pozostawię na inną okazję. Na ten moment skupimy się na kodowaniu map .osm, których rozmiar będzie akceptowalny przez nasze ograniczenia sprzętowe. Zacznijmy od tego, jakim wymaganiom musi sprostać nasz algorytm:

1. Musi ciąć mapę na kafelki, a następnie odczytywać tylko te obiekty, które znajdują się w interesującym nas obszarze
2. Musi obliczać rozmiar kafelka dla każdego z poziomów zbliżeń
3. Do każdego utworzonego kafelka eksportować tylko te obiekty, które mają być widoczne na danym poziomie zbliżenia
4. Obiekty muszą być eksportowane zgodnie z pewną kolejnością
5. Musi śledzić adresy do poziomów zbliżeń jak i kafelków w formacie .ltd, po to aby poprawnie utworzyć relacje
6. Nie musi być demonem prędkości, ale fajnie byłoby gdyby nie trzeba było czekać 3 lat na ukończenie procesu kodowania

Po tym krótkim wstępie możemy zacząć omawianie programu kodera. Wykorzystamy język Python ze względu na dostępne narzędzia, które idealnie spełniają nasze wymagania. Plik z koderem do dwóch wersji formatu .ltd znajduje się w załączniku.
Zaczynamy!

Wstępne informacje

Całe drzewo plików wygląda następująco:

Zanim rozpoczniemy parsowanie pliku .osm i kodowanie .ltd, chciałbym się skupić na pliku reader_size.py. Znajdują się w nim 4 klasy:

#Rozmiar podany w bajtach do budowania pliku .hdr
class size_info_file_1:
    file_type_size = 4
    map_name_size = 13
    doc_size = 4                #date of creation
    map_coordinates_size = 4    #*4
    noz_size = 1                #number of zooms
    
#Rozmiar podany w bajtach do budowania pliku .ltd
class size_info_file_2:
    #Nagłówek zoom
    map_name_size = 13
    zoom_name_size = 1
    squares_number_size = 2
    block_size_x = 4
    block_szie_y = 4
    addr_size = 1

    #Kafelki
    coordinates_size = 4
    all_obj_types_size = 1
    object_type_size  = 1
    objects_qnty_size = 4
    subobject_type_size = 1
    point_qnty_size = 2         
    node_size = 'f'             #zapisz współrzędne geograficzne jako float

class file_1_info:
    squares_number = []

class file_2_info:
    addr_size = 0               #rozmiar adresu w bajtach
    square_addr = []            #adres do kafelka
    block_width = []            #szerokość kafelka
    all_objects_type = 0        #liczba typów obiektów w kafelku
    objects_qnty = [0]*32       #liczba wszystkich obiektów w kafelku

Atrybuty klasy "size_info_file_1" oraz "size_info_file_2" są wykorzystywane podczas kodowania do określenia ile bajtów przeznaczyć na dane pole w kodowanym formacie. Jeżeli mamy potrzebę zwiększenia jakiegoś pola danych to możemy to tutaj zrobić. Atrybuty klasy "file_1_info" oraz "file_2_info" przechowują dane, które nie mogą zostać wpisane od razu do formatu .ltd. Może się tak zdarzyć, gdy musimy ominąć jakieś bajty, ponieważ wartość jaką musimy tam wpisać zostanie dopiero obliczona na koniec działania algorytmu. Wtedy wpisujemy n bajtów wypełnionych 0x00 i wracamy do tego miejsca, gdy będziemy wiedzieli jaką wartością wypełnić to pole. Przykładowo:

self.write_n_bytes(self.new_file, size_info_file_2.objects_qnty_size, 0) 

 

Konfiguracja kodera

Przejdźmy teraz do folderu Map_levels. Zawiera on pliki zoom_n.py oraz zoom_info.py. Pliki zoom_n.py są plikami konfiguracyjnymi i ze względu na rozmiary pozwolę sobie ich całych tutaj nie wklejać. To w tych plikach możemy ustalić filtry dla danego poziomu zbliżenia. W klasie zoom_visibility_n na samym początku znajduje się lista pod nazwą „objects".

objects = [
    0,  # aerialway
    0,  # aeroway
    0,  # amenity
    0,  # barrier
    0,  # boundary
    0,  # building
    0,  # craft
    0,  # emergency
    0,  # firefighters
    0,  # lifeguards
    0,  # assembly_point
    0,  # other_structure
    0,  # geological
    0,  # highway
    0,  # historic
    0,  # landuse
    0,  # leisure
    0,  # man_made
    0,  # military
    0,  # natural
    0,  # office
    0,  # place
    0,  # power
    0,  # public_transport
    0,  # railway
    0,  # route
    0,  # shop
    0,  # sport
    0,  # telecom
    0,  # tourism
    0,  # waterway
]

Lista ta umożliwia skonfigurowanie, które typy obiektów mają być eksportowane do pliku .ltd dla danego poziomu zbliżenia. Z reguły zoom_visibility_0 jest używany dla największego oddalenia, więc jeżeli chcemy np. wyświetlać jedynie drogi to pod odpowiednie 0 podstawiamy „highway”.

objects = [
     .
     .
     .
    0,  ----- „highway”
     .
     .
     .
]

Skoro tak, to musimy jeszcze ustawić jakie rodzaje obiektów mają być eksportowane dla tego typu obiektu. W tym celu idziemy do odpowiadającej listy:

highway = []

i analogicznie podstawiamy rodzaje obiektów (w postaci ciągu znaków) pod odpowiadające zera. Istotne jest, aby nie pomylić się podczas wpisywaniu stringa, dlatego najlepiej skopiować i wkleić zakomentowany ciąg znaków.
W folderze Map_levels znajduje się kilka plików zoom_n.py, a ich liczba zależy od tego ile chcemy mieć stopni przybliżeń. Każdy plik może zostać skonfigurowany dowolnie i nie będzie to wpływać na inne poziomy zbliżenia. Jeżeli chcemy dodać kolejny poziom zbliżenia, wystarczy skopiować jakikolwiek zoom_n, nadać mu nazwę z identyfikatorem n+1 (gdzie n jest aktualną liczbą stopni przybliżeń), skonfigurować go wedle własnych potrzeb i do pliku zoom_info.py wkleić.

from Map_levels.zoom_n import *

Oczywiście za “n” należy podstawić nowo dodany stopień.

W ten oto sposób przeszliśmy do ostatniego pliku z folderu /Map_levels, czyli zoom_info.py. Oprócz kilku linijek odpowiadających za dołączenie do tego pliku wszystkich zoom_n, plik ten wygląda następująco:

map_level = [4,9,16,25,36,64,100,144,256,289,400,625,900,1024]
zoom_levels = [0,1,2,3]

def factory(classname):
    cls = globals()[classname]

    return cls()

Tylko tyle, ale to tutaj wykonuje się konfigurowanie na ile kafelków mają zostać podzielone stopnie zbliżenia. Wpierw widzimy listę map_level = []. Można zaobserwować, że wszystkie jej elementy są wynikiem podniesienia liczby naturalnej do drugiej potęgi. Jeżeli to kryterium nie zostanie spełnione, kod się nie wykona. Jest to oczywisty wymóg, aby mapa została podzielona na „n” równych części. Ta lista nie powinna i nie może ulec zmianie podczas przetwarzania mapy.  Do tej listy najbardziej optymalną metodą jest wpisywanie wartości zgodnie ze wzorem:

lecz przy wymiarach małej mapy piąty stopień dzieliłby ją na zbyt wiele części, przez co czas wyświetlania mógłby się wydłużyć. Trzeba tutaj znaleźć kompromis, a w przyszłości opracować prosty algorytm, który sam będzie ustalał te wartości na podstawie rozmiaru mapy.

Dalej widzimy listę "zoom_levels = []". To w niej konfigurujemy na ile części ma zostać podzielony dany stopień przybliżenia. Nie jest to jednak bezpośrednie, ponieważ aktualnie widoczne wartości czyli 0,1,2,3 wskazują na elementy listy "map_level = []". Zrobiłem tak, ze względu na ułatwienie podczas testowania programu – nie musiałem za każdym razem liczyć na ile kwadratów podzielić stopień.

Ostatnia pojawia się funkcja:

def factory(classname):

Działa ona na zasadzie wskaźnika do klasy zoom_visibility_n w pliku zoom_n. Poprzez jej wywołanie możemy uzyskać dostęp do obiektów znajdujące się w klasie „classname”. Funkcja ta jest wykorzystywana w pliku export.py do którego teraz przejdziemy.

 

Plik export.py

To w pliku export.py dzieje się cała magia parsowania .osm i kodowania formatu .ltd. Na wstępie oprócz dodania bibliotek, w obiekcie „map_name” możemy ustalić jaka mapa ma zostać zamieniona na format .ltd.

map_name = 'kreta'
tree = ET.parse('%s.osm' % map_name)

Następnie wykorzystując API do parsera XML mapa zostaje zostaje wczytana przez parser XML i od tego momentu mamy swobodny dostęp do elementów pliku .osm. Cała funkcjonalność parsera została umieszczona w klasie parser_export. Aby rozpocząć proces kodowania formatu należy wywołać funkcję export_map().

def export_map():
    #Konstruktor
    export = parser_export()

    #Eksportowanie pliku .hdr
    export.export_main()

    #Eksportowanie plików .ltd
    export.export_zoom_headers(zoom_levels)

 

Odczyt podstawowych informacji z pliku .osm

Podczas tworzenia obiektu klasy "parser_export()" zostają alokowane wszystkie zmienne i listy, które przydadzą się podczas kodowania. W jej konstruktorze wywoływane są trzy funkcje:

self.read_header()
self.read_bounds()
self.read_nodes()

Pierwsza z nich odczytuje nagłówek pliku .osm. Następnie funkcja read_bounds() odczytuje obszar (określony przez współrzędne geograficzne), jaki obejmuje mapa i zapisuje te dane jako float. W ramach ostatniej funkcji zostają wczytane wszystkie ‘nodes’ jakie są wykorzystywane w tej mapie. Informacje jakie zostają zapisane to:

• Szerokość geograficzna punktu
• Wysokość geograficzna punktu
• Numer ID punktu

Proces ten jest potrzebny, aby poszukując punktów z jakich składa się ‘way’ nie trzeba było ponownie parsować pliku .osm, co zajmuje więcej czasu niż bezpośredni odczyt z pamięci RAM. Po wykonaniu tych trzech funkcji możemy już przejść do eksportowania pierwszego pliku.

Funkcje I/O

Zanim to zrobimy, wpierw skupmy się na opisie podstawowych funkcji I/O do plików systemowych. Będą one wykorzystywane za każdym razem, gdy chcemy coś zapisać lub odczytać z pliku.

# Funkcja służąca do wpisywania ciągu bajtów do wybranego pliku w wybranym formacie
# [in] file - obiekt odpowiadający naszemu plikowi
# [in] nodes - lista danych
# [in] type - format danych
def write_array_data(self, file, nodes, type):
    write_array = array(type, nodes)
    write_array.tofile(file)

# Funkcja służąca do wpisywania ciągu bajtów do wybranego pliku
# [in] file - obiekt odpowiadający naszemu plikowi
# [in] size - ilość bajtów do wpisania
# [in] data - lista danych
def write_n_bytes(self, file, size, data):
    file.write(data.to_bytes(size, 'little'))

# Funkcja służąca do odczytu ciągu danych w wybranym formacie
# [in] file - obiekt odpowiadający naszemu plikowi
# [in] size - ilość bajtów do odczytania
# [in] type - typ danych jaki ma zostać zwrócony
# [out] return – zwraca odczytany ciąg bajtów
def read_array_data(self, file, size, type):
    read_array = array(type)
    read_array.fromfile(file, size)
    return read_array

# Funkcja służąca do utworzenia folderu
# [in] path - obiekt opisujacy ścieżkę folderu
def create_dir(self, path):
    try:
        os.mkdir(path)
    except OSError:
        print("Creation of the directory %s failed" % path)
    else:
        print("Successfully created the directory %s " % path)

Do wpisywania oraz wczytywania ciągów znaków z pliku wykorzystaliśmy moduł array.

from array import array

Może się pojawić pytanie czym się różni funkcja:

def write_array_data(self, file, nodes, type):

od:

def write_n_bytes(self, file, size, data):

Pierwsza funkcja posiada możliwość kodowania przekazanego typu danych do innego typu np. float. Druga funkcja umożliwia zapisanie np. wartości 2 bajtowej jako 8 bajtów. W przypadku funkcji do wczytywania danych, możemy odczytać dany ciąg bajtów i od razu zwrócić go, jako określony typ danych.

 

Eksportowanie pliku .hdr

Skoro mamy już to za wszystko za sobą, możemy przejść do tworzenia głównego pliku z rozszerzeniem .hdr.

#Eksportowanie pliku o rozszerzeniu .hdr
def export_main(self):
    main_header_file = open("Mapa/%s.hdr" % map_name, mode="w+b")  #utwórz nowy plik

    today = datetime.datetime.now()
    self.write_array_data(main_header_file, [ord(c) for c in ".ltd"], 'B')                  #wpisz rozszerzenie
    self.write_array_data(main_header_file, [ord(c) for c in map_name_truncated], 'B')      #wpisz map name

    self.write_n_bytes(main_header_file, int(size_info_file_1.doc_size / 4), today.day)     #wpisz dzien
    self.write_n_bytes(main_header_file, int(size_info_file_1.doc_size / 4), today.month)   #wpisz miesiac
    self.write_n_bytes(main_header_file, int(size_info_file_1.doc_size / 2), today.year)    #wpisz rok

    self.write_array_data(main_header_file, [self.min_lon, self.max_lon, self.min_lat, self.max_lat], 'f')  #wpisz obszar mapy
    self.write_n_bytes(main_header_file, size_info_file_1.noz_size, self.zoom_numbers)  #wpisz ilosc stopni zbliżeń
    main_header_file.close()

Wpierw tworzymy lub otwieramy (wtedy dodatkowo nadpisujemy) plik w folderze /Mapa. Nazwa tego pliku będzie taka sama jak ustaliliśmy na początku, lecz rozszerzenie pliku to .hdr. Wskaźnik R/W w tym wypadku jest automatycznie ustalony na pozycji 0, więc zaczynamy wpisywanie danych do pliku zgodnie z formatem, który został opisany w poprzednim rozdziale. Po zakończeniu wpisywania danych do pliku jest on zamykany.

 

Eksportowanie pliku .ltd

Możemy rozpocząć eksportowanie naszych własnych map tiles. Eksportowane pliki będą umieszczane w /Mapa/Zooms/zoom_level_n, gdzie n oznacza stopień zbliżenia. Ostatecznie utworzony plik będzie się nazywał:

<nazwa mapy>_n.ltd

Mówię ostatecznie, ponieważ w trakcie kodowania zostanie utworzonych kilka dodatkowych plików pomocniczych. Cały proces tworzenia pliku .ltd zaczyna się od wywołania poniższej funkcji:

def export_zoom_headers(self, zoom_level):
    # iteracja przez wszystkie stopnie zbliżeń
    for level in range(len(zoom_level)):
        self.zoom_level = zoom_level[level]
        self.squares_numer = map_level_squares[zoom_level[level]]
        self.split_segment(self.squares_numer)

        path = "Mapa/Zooms/zoom_level_%s" % self.zoom_level
        self.create_dir(path)
        zoom_header_file = open("Mapa/Zooms/zoom_level_%s/%s_%s.ltd" % (self.zoom_level,map_name, self.zoom_level), mode="w+b")  #utworz plik naglowkowy do .ltd
        self.write_array_data(zoom_header_file, [ord(c) for c in map_name_truncated], 'B')              #wpisz nazwe mapy
        self.write_n_bytes(zoom_header_file, size_info_file_2.zoom_name_size, self.zoom_level)          #wpisz stopień zbliżenia
        self.write_n_bytes(zoom_header_file, size_info_file_2.squares_number_size, self.squares_numer)  #wpisz ilośc kafelków
        self.write_array_data(zoom_header_file, file_2_info.block_width[level], 'f')                    #wpisz szerokosc oraz wysokosc kafelka
        zoom_header_file.close()                                            
        #Wykorzystanie naszego pliku konfiguracyjnego do okreslenia jakie typy i rodzaje obiektow maja zostac eksporotwane
        self.zoom_n_info = factory(("zoom_visibility_%d"%(zoom_level[level])))
        #Eksportowanie kafelków
        self.export_squares(level)

        #łączenie kafelków
        square_file = open("Mapa/Zooms/zoom_level_%s/all_squares_%s" % (self.zoom_level, self.zoom_level), mode="w+b")
        for squares in range(0,self.squares_numer):
            #Zapisywanie wskaźnika na bajt gdzie zaczyna się kafelek
            file_2_info.square_addr.append(square_file.tell())      
            #Otwieranie jednego z wcześniej utworzonych kafelków
            square_file_n = open("Mapa/Zooms/zoom_level_%s/square_%s" % (self.zoom_level, squares), mode="r+b")
            #Dołączanie n-tego kafelka do pliku, który ma zawierać wszystkie połączone kafelki
            square_file.write(square_file_n.read())
        square_file.close()
        
        #Obliczanie ile bajtów jest potrzebne do zapisania adresu do kafelka
        b_len = max(file_2_info.square_addr).bit_length()
        if (b_len <= 8):
            file_2_info.addr_size= 1
        elif (b_len <= 16):
            file_2_info.addr_size= 2
        elif (b_len <= 32):
            file_2_info.addr_size= 4
        elif (b_len <= 64):
            file_2_info.addr_size= 8
            
        #Określenie offsetu tzn. określenie ile bajtów zajmuje nagłówek .ltd
        offset_zoom_header = size_info_file_2.map_name_size+size_info_file_2.zoom_name_size +size_info_file_2.squares_number_size + 2*size_info_file_2.block_size_x + size_info_file_2.addr_size+self.squares_numer*file_2_info.addr_size

        #Przygotowanie do łączenia kafelków           
        zoom_header_file = open("Mapa/Zooms/zoom_level_%s/%s_%s.ltd" % (self.zoom_level, map_name, self.zoom_level), mode="a+b") 
        self.write_n_bytes(zoom_header_file, size_info_file_2.addr_size, file_2_info.addr_size)  
        for squares in range(0,self.squares_numer):
            self.write_n_bytes(zoom_header_file, file_2_info.addr_size, file_2_info.square_addr[squares]+offset_zoom_header)
        
        # Połącz nagłówek .ltd wraz z utworzonym plikiem kafelków
        square_file = open("Mapa/Zooms/zoom_level_%s/all_squares_%s" % (self.zoom_level, self.zoom_level), mode="r+b")  
        zoom_header_file.write(square_file.read())
        file_2_info.addr_size = 0
        file_2_info.square_addr.clear()
        zoom_header_file.close()
        square_file.close()

Wchodząc do funkcji od razu trafiamy na pętlę, która zapewnia że zostanie wyeksportowanych tyle plików .ltd ile zostało określonych wartości w liście zoom_levels = [] w pliku zoom_info.py. Następnie odczytujemy na ile części ma zostać podzielona mapa dla aktualnie eksportowanego pliku .ltd.  Gdy to zrobimy zostaje wywołana funkcja:

def split_segment(self, pieces):
    self.sqrt_pieces = math.sqrt(pieces)

    #Sprawdz czy podany argument jest perfect square number
    if int(self.sqrt_pieces + 0.5) ** 2 == pieces:
        self.lon_difference = (self.max_lon – self.min_lon) / self.sqrt_pieces
        self.lat_difference = (self.max_lat – self.min_lat) / self.sqrt_pieces
        file_2_info.block_width.append([self.lon_difference, self.lat_difference])
    else:
        print(“Error: Given number of squares to divide the map is not a perfect square number”)
        exit()

w której wpierw zostanie sprawdzone czy podana wartość argumentu funkcji jest na pewno wynikiem podniesienia liczby naturalnej do drugiej potęgi. Jeżeli nie to program się dalej nie wykona. Jeżeli tak, to mapa zostanie wirtualnie podzielona na x równych części i zostanie obliczona szerokość oraz wysokość jednego kafelka. Wielkości te będą podane, jako różnica współrzędnych geograficznych tego kafelka. Następnie wielkości te zostaną dołączone do listy "file_2_info.block_width".

Wracamy do poprzedniej funkcji

def export_zoom_headers(self, zoom_level):

Zostaje utworzony nowy folder pod ścieżką Mapa/Zooms/zoom_level_n do którego będą teraz zapisywane wszystkie niezbędne pliki do utworzenia pierwszego pliku .ltd. Na samym wstępie zostaje on utworzony tylko po to, aby zapisać w nim nagłówek. W dalszych etapach dane będą już tylko dołączane do tego pliku. Następnie pobierane są informacje z pliku konfiguracyjnego o zastosowanych filtrach w danym stopniu zbliżenia. Gdy to zrobimy zostaje wywołana funkcja:

def export_squares(self, level):
    #Iteracja przez wszystkie kafelki
    for squares in range(self.squares_numer):  
        square_file = open("Mapa/Zooms/zoom_level_%s/square_%s" % (self.zoom_level, squares), mode="w+b")

        self.calc_square(squares)  #obliczanie rozmiaru kafelka
        self.write_array_data(square_file, self.sq_coordinates, 'f')  #wpisanie koordynatów kafelka

        self.export_objects()  #szukanie i eksportowanie wszystkich obiektów które znajdują się w kafelku

        #Po przejsicu przez caly plik dla danego kafelka i jego eksportowaniu połącz je i usun zbedne pliki
        self.write_n_bytes(square_file, size_info_file_2.all_obj_types_size, file_2_info.all_objects_type) 
        for object_types in range(0,file_2_info.all_objects_type):
            object_file = open("Mapa/Zooms/zoom_level_%s/%s.obj" % (self.zoom_level, self.zoom_n_info.objects[self.created_objects_types[object_types]]), mode="r+b")  #open file
            #Wpisz brakujace dane 
            object_file.seek(1)
            self.write_n_bytes(object_file, size_info_file_2.objects_qnty_size, file_2_info.objects_qnty[self.created_objects_types[object_types]]+1)
            object_file.seek(0)
            square_file.write(object_file.read())

        object_file.close()
        square_file.close()
        for object_types in range(0,file_2_info.all_objects_type):
            os.remove("Mapa/Zooms/zoom_level_%s/%s.obj"%(self.zoom_level, self.zoom_n_info.objects[self.created_objects_types[object_types]]))
        self.created_objects_types.clear()
        file_2_info.all_objects_type = 0
        file_2_info.objects_qnty = [0]*32

Spełnia ona główną rolę w procesie parsowania mapy i tworzenia mapy kafelkowej. Ponownie funkcja rozpoczyna się pętlą, która wykona się tyle razy na ile mamy podzielić naszą mapę. Tworzony jest n-ty plik z nazwą square_n i rozpoczyna się istotny proces obliczania obszaru, jaki ma zostać wyeksportowany w ramach tego kafelka. Jak wiemy, wszystkie kafelki mają taki sam rozmiar, więc dla każdego eksportowanego kafelka nasze współrzędne zapisane w file_2_info.block_width musimy przesuwać o jego szerokość lub wysokość, ale w z góry ustalonej kolejności. Pozwolę to sobie wyjaśnić na podstawie rysunku.

Czerwonym kolorem został zaznaczony obszar mapy, a czarnym podział kafelków. Numery 1,2,3,4 oznaczają kolejność eksportowania kafelków jak również ich numer identyfikacyjny. Teraz, jeżeli chcemy np. eksportować kafelek 4 i obiekty w nim się znajdujące to musimy poznać jego wymiary, czyli współrzędne geograficzne. W związku z tym należy z punktu X(0,0) przesunąć się o wektor XZ[1,1]. Następnie posiadając wiedzę na temat szerokości i wysokości pojedynczego kafelka (co zostało obliczone wcześniej), możemy określić, jakie punkty go definiują. W tym wypadku byłyby to Z(1,1) oraz Y(2,2). Analogicznie należy napisać jedynie równanie, które będzie zamieniało numer kafelka na właśnie ten wektor XZ i przemnażał współrzędną x-ową przez bok „a”, natomiast współrzędną y-ową przez bok „b”. W ten sposób otrzymaliśmy punkt Z. Aby otrzymać punkt Y należy do punktu Z dodać analogicznie bok „a” oraz bok „b”. 

 

Chwila, chwila. Zanim napiszę kolejny wzór na punkt Y chcę nadmienić, że jestem świadom, iż w drugim wzorze mianownik się skraca i zostaję ze wzorem:

Tak by było w świecie rzeczywistym, ale nie zero jedynkowym. Zastosowałem tutaj pewien trik nazwany rzutowaniem. Po prostu w kodzie działanie:

 

rzutuję na typ integer, dzięki czemu działanie zostanie zaokrąglone „w dół” i nic mi się nie skróci. Warto dodać, że to zdanie jest tylko prawdą dla wyniku dodatniego, ale innego tutaj nie przewidujemy. 
Kontynuując:

gdzie:
            x₀ – x-owa punktu X
            x₁ – y-owa punktu X
            n – ilość kafelków

Największą zaletą tego rozwiązania jest to, że w bardzo łatwy sposób można zidentyfikować współrzędne pojedynczego kafelka podczas kodowania jak również dekodowania formatu.

Po tym lekkim aczkolwiek istotnym offtopie możemy wrócić do algorytmu. Obliczyliśmy współrzędne naszego kafelka, więc możemy je wpisać do pliku .ltd. Teraz czas przeskanować wszystkie obiekty, i dodać do pliku tylko te, które znajdują w obszarze kafelka. Dodatkowo obiekty te muszą spełnić nasze wymagania dotyczące filtrów. Szybciej jest odczytać tag obiektu i sprawdzić czy jego typ oraz rodzaj jest dodany w naszym filtrze, dlatego zaczynamy od funkcji:

def export_objects(self):
    for way in self.root.iter('way'):
        for tags in way.findall('tag'):
            keys = (tags.get('k'))  # objects
            values = (tags.get('v'))  # subobjects
            if (keys in self.zoom_n_info.objects): #object jest wspierany przez konfigurator
                subobj_list = getattr(self.zoom_n_info, keys)
                if (values in subobj_list):  #subobject jest wspierany przez konfigurator
                    #Znajdz wszystkie 'nd' w tym tagu
                    for nodes in way.findall('nd'):
                        self.node_number.append(int(nodes.get('ref'))) 
                    self.export_object_in_square(keys,values)
                self.node_number.clear()
                break

Wykorzystujemy tutaj XML API, które robi za nas całą robotę i przeskakuje w mapie od obiektu do obiektu. Z każdego obiektu jest pobierany jego tag, a następnie sprawdzamy czy jego key oraz value (czyli typ i rodzaj) znajduje się w naszym filtrze. Jeżeli tak, to rozpoczynamy pobieranie wszystkich numerów ID punktów, z jakich składa się ten obiekt. Następnie przechodzimy do kolejnej funkcji, która nie tylko sprawdza czy jakikolwiek punkt obiektu znajduje się w obszarze, ale również wykonuje pewien mechanizm, który umożliwia nam tworzenie warstw w mapie.

def export_object_in_square(self, object_type, subobject_type):
    self.node_location.clear()
    for x in range(len(self.node_number)):
        id_number = self.id.index(self.node_number[x])  
        lat = self.lat[id_number]
        lon = self.lon[id_number]
        self.node_location.append(lat)
        self.node_location.append(lon)
    if self.point_in_square() == 1:
        object_id = self.zoom_n_info.objects.index(object_type)
        subobject_id = getattr(self.zoom_n_info, object_type).index(subobject_type)  #zamiana stringu na numer ID
        node_qnty = len(self.node_location)  # number of nodes
        file_found = self.find(("%s.obj"%object_type), "Mapa/Zooms/zoom_level_%s"%self.zoom_level) #look for file

        if file_found == 1:  #jeżeli plik istnieje
            file_2_info.objects_qnty[object_id] += 1
            self.new_file = open("Mapa/Zooms/zoom_level_%s/%s.obj" % (self.zoom_level,object_type), mode="a+b")  
            self.write_n_bytes(self.new_file, size_info_file_2.subobject_type_size, subobject_id)
            self.write_n_bytes(self.new_file, size_info_file_2.point_qnty_size, node_qnty)
            self.write_array_data(self.new_file, self.node_location, 'f')
            self.new_file.close() 
        elif file_found == 0:  
            file_2_info.all_objects_type += 1
            self.created_objects_types.append(object_id)
            self.new_file = open("Mapa/Zooms/zoom_level_%s/%s.obj" % (self.zoom_level,object_type), mode="w+b")  
            self.write_n_bytes(self.new_file, size_info_file_2.object_type_size, object_id) 
            self.write_n_bytes(self.new_file, size_info_file_2.objects_qnty_size, 0)  
            self.write_n_bytes(self.new_file, size_info_file_2.subobject_type_size, subobject_id)
            self.write_n_bytes(self.new_file, size_info_file_2.point_qnty_size, node_qnty)
            self.write_array_data(self.new_file, self.node_location, 'f')  
            self.new_file.close()  

Zacznijmy od tego, że na ten moment posiadamy:

• Listę, która jest wypełniona numerami ID punktów znajdujących się w obiekcie:

self.node_number = []

• Listę wszystkich punktów znajdujących się w mapie:

self.id = []

Musimy zdekodować numery ID punktów i otrzymać ich współrzędne geograficzne. W tym celu na wstępie, w pętli for dekodujemy numery ID punktów obiektu, tworzymy nową listę i wypełniamy ją współrzędnymi geograficznymi punków znajdujących się w obiekcie

self.node_location = []

Gdy wszystkie punkty zostaną zdekodowane wywołujemy funkcję, która zwraca logiczną jedynkę,  jeśli jakikolwiek punkt znajduje się w kafelku.

If self.point_in_square() == 1:

Jeżeli tak się stanie, to musimy ten obiekt wyeksportować do kafelka. W tym celu ponownie wykorzystujemy nasz konfigurator zoom_info.py i zamieniamy typ wykrytego obiektu oraz jego rodzaj na wartość liczbową. Dodatkowo zapisujemy z ilu punktów składa się ten obiekt oraz rozpoczynamy mechanizm segregacji typów obiektów.
Aby, móc umieścić typy obiektów w pliku .ltd w odpowiedniej kolejności musimy je wpierw pogrupować poza tym plikiem (albo cashować je w pamięci). W takim razie otwieramy ten plik, który zawiera zakodowany tylko ten typ obiektów(w formacie .ltd), jak nasz aktualny, który chcemy dopisać. Jeżeli takiego pliku nie ma, ponieważ jest to pierwszy taki typ obiektu, jaki kiedykolwiek podczas pracy algorytmu został wykryty to zostaje utworzony nowy plik. Ten plik będzie posiadał taką samą nazwę jak nasz typ obiektu. Cały ten proces jest realizowany w tym fragmencie kodu.

File_found = self.find((„%s.obj”%object_type), „Mapa/Zooms/zoom_level_%s”%self.zoom_level) 
if file_found == 1:  # if file exists
	*
	*
	*
	*
elif file_found == 0:  # if file doesn’t exist
	*
	*
	*
	*

W zależności od tego czy jest to kolejny obiekt do dodania, czy też kompletnie nowy typ obiektów, dane zostaną zakodowane z różnym nagłówkiem. Kiedy wszystkie obiekty należące do aktualnie wypełnianego kafelka zostały znalezione, pozostało jedynie połączyć utworzone przed chwilą pliki typów obiektów w dogodny dla nas sposób. Dogodny to znaczy taki, żeby podczas wyświetlania mapy mniej istotne typy obiektów były schowane pod tymi bardziej istotnymi. Zanim wrócimy do funkcji export_squares(self, level) spójrzmy jeszcze tylko na format .ltd i dane tuż po utworzeniu kafelka.

Format zapisania informacji o obiektach w kafelku (plik II)

Dla pierwszego bajtu mamy informację o rodzaju obiektu i możemy ją wypełnić w pliku. Niestety nie mamy pojęcia o ilości obiektów w tym pliku. Tę informację będziemy posiadać dopiero po przeprasowaniu całej mapy. Jedyne co możemy zrobić to wpisać teraz 0x00, a po zakończonym procesie parsowania dopełnić brakujące dane. Stąd bierze się poniższa funkcja, która wypełnia pole zerami.

Self.write_n_bytes(self.new_file, size_info_file_2.objects_qnty_size, 0) 

 

Kiedy skanowanie obiektów skończyło się wykonywać  kontynuujemy kodowanie w funkcji:

def export_squares(self, level):

pierwsza funkcja tuż po powrocie to:

self.write_n_bytes(square_file, size_info_file_2.all_obj_types_size, file_2_info.all_objects_type) 

która wpisuje do wcześniej utworzonego pliku z kafelkiem ilość typów obiektów w nim się znajdujących.
Następnie wchodzimy do pętli:

for object_types in range(0,file_2_info.all_objects_type):

W niej wpierw zostanie otworzony w odpowiedniej kolejności zakodowany w formacie .ltd plik z obiektami, a następnie wskaźnik R/W powędruje jeden bajt do przodu, aby wykonać nadpisanie ilości obiektów dla tego typu. Następnie plik ten już w pełni gotowy plik zostanie dołączony do pliku z kafelkami. Dzieje się tak dla każdego z utworzonych typów obiektów. Na sam koniec zbędne dane są kasowane. Cały ten mozolny proces zaczynając od wejścia do funkcji export_squares(self, level) jest powtarzany tyle razy na ile kafelków jest podzielony stopień zbliżenia. Jako rezultat pracy otrzymujemy wiele plików, które są zakodowanymi kafelkami.

 

Łączenie wszystkich plików

Pozostał ostatni etap, czyli utworzenie pełnego pliku z rozszerzeniem .ltd. To już jest proste zadanie i polega na łączeniu kafelków w kolejności rosnącej od 0 do n. Wracamy do funkcji:

def export_zoom_headers(self, zoom_level):

i tworzymy nowy plik:

square_file = open("Mapa/Zooms/zoom_level_%s/all_squares_%s" % (self.zoom_level, self.zoom_level), mode="w+b")  # create square file

To w tym pliku połączymy nasze wszystkie wcześniej utworzone kafelki. Wszystko się dzieje w pętli linijkę kodu niżej. Dodatkowo z każdym połączeniem plików kafelków, jest zapisywany ich rozmiar w bajtach. To się za chwile przyda, ponieważ trzeba jeszcze dołączyć nagłówek.
Sprawdzamy teraz ile bajtów jest potrzebne, aby zamieścić adres do ostatniego kafelka. Adres ten jest pomniejszony o ilość bajtów jakie są potrzebne na zapis nagłówka.

b_len = max(file_2_info.square_addr).bit_length()

W zależności od zwróconej wartości, wpisujemy zapisujemy 1,2,3,4 lub 8 bajtów.
Tworzymy nowy plik:

zoom_header_file = open("Mapa/Zooms/zoom_level_%s/%s_%s.ltd" % (self.zoom_level, map_name, self.zoom_level), mode="a+b")  # create zoom file

a następnie wpisujemy file_2_info.addr_size. Kolejno w pętli:

for squares in range(0,self.squares_numer):

wpisujemy adresy do kafelków, które już za chwile się pojawią w tym pliku. Teraz nic już nas nie zatrzymuje przed połączeniem nagłówka poziomu zbliżenia wraz z kafelkami jakie się w nim znajdują. Służy do tego wywołanie funkcji:

zoom_header_file.write(square_file.read())

Czyścimy zbędne dane i koniec!
Koniec generowania pliku z  pierwszym poziomem zbliżenia. Teraz jeszcze tylko powtórzyć to wszystko, cały algorytm tyle razy ile chcemy mieć poziomów. Etapy tworzenia plików można obejrzeć na poniższym gifie.

Pliku utworzone w procesie kodowania plików .ltd

 

Uruchomienie kodera

W folderze Format_export_v2 musi się znajdować plik .osm z mapą, którą chcemy eksportować. Polecam zacząć wpierw od małych wycinków i rozmiarach plików do kilku MB. W pliku export.py wpisujemy nazwę tej mapy (bez rozszerzenia) do:

map_name = ''

Możemy przejść do eksportowania pliku. Na wstępie zostanie utworzony plik z rozszerzeniem .hdr w folderze /Mapa. Po skończonym procesie kodowania formatu w folderze /Mapa/Zooms zostanie utworzonych tyle folderów ile zadeklarowaliśmy stopni zbliżeń. W każdym z tych plików można znaleźć te z rozszerzeniem .ltd. To właśnie one są nam potrzebne i tworzą spójną całość z plikiem .hdr. Należy każdy z plików .ltd umieścić wraz z plikiem .hdr w oddzielnym folderze. Ten folder będzie zawierał wszystkie pliki potrzebne do dekodowania mapy.

Za każdym uruchomieniem kodera należy manualnie usunąć foldery znajdujące się w /Mapa/Zooms oraz plik .hdr. Programy koderów dwóch formatów przedstawionych w poprzedniej części znajdują się w załączniku. Do ich stworzenia korzystałem z IDE PyCharm

 

Podsumowanie

Jeżeli dotrwałeś do tego momentu to jest mi niezmiernie miło. Obiecuję, że w następnej części artykułu będziemy obserwować pierwsze efekty naszej mozolnej pracy. Myślę, że po przeczytaniu tej części problematyka zagadnienia związana z przetwarzaniem map jest już znacznie bardziej rozumiana. Teraz, po stworzeniu formatu jak i kodera od zera można zobaczyć, gdzie tracimy najwięcej czasu podczas kodowania. Wpierw musimy odczytać i zapisać wszystkie punkty obsługiwane w ramach parsowanej mapy. Następnie dla każdego kafelka musimy skanować wszystkie obiekty w mapie, po to aby sprawdzić który z nich znajduje się w tymże kafelku. Niestety obiekty mogą być wieloliniami lub poligonami, więc musimy skanować wszystkie punkty obiektu i za każdym razem sprawdzać czy jakikolwiek z tych punktów znajduje się w kafelku. Bardzo dużo danych do skanowania i bez wydajnych algorytmów dużo się nie zdziała. Lecz wydajność kodera nie była celem mojego programu, chodziło tylko o przedstawienie idei oraz formatu map. Teraz jedyne co nam pozostało to wgrać mapę na kartę pamięci lub inny nośnik i rozpocząć dekodowanie na naszym systemie wbudowanym, które dzięki temu, że z pieczołowitością zakodowaliśmy nasz format, będzie znacznie, znacznie prostsze.

Spis treści:

1. Przetwarzanie OpenStreetMap na systemie wbudowanym #1 - Format .osm
2. Przetwarzanie OpenStreetMap na systemie wbudowanym #2 - Parsowanie formatu .osm
3. Przetwarzanie OpenStreetMap na systemie wbudowanym #3 - Kodowanie formatu .ltd
4. Przetwarzanie OpenStreetMap na systemie wbudowanym #4 - Dekodowanie formatu .ltd

Koder_formatu.zip

[Treker (Damian Szymański)]

@kronikary artykuł został właśnie zatwierdzony i jest już widoczny publicznie 🚀