Shapely

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 1 z 8. Być może jesteś przyzwyczajony do traktowania geometrii na mapie jako zwykłych list współrzędnych, używanych głównie do rysowania kształtów na ekranie. Ale kiedy musisz obliczyć, czy ślad GPS przekracza konkretną granicę, prosta logika rysowania po prostu zawodzi. Aby przeprowadzić prawdziwą, matematyczną analizę przestrzenną, potrzebujesz Spatial Data Model. Najpierw musimy wyjaśnić częste źródło nieporozumień związanych z tym modelem. Shapely działa ściśle na płaskiej, dwuwymiarowej płaszczyźnie kartezjańskiej. Możesz podać współrzędne X, Y i Z podczas tworzenia swoich geometrii. Shapely je sparsuje, a nawet zapisze tę wartość Z w pamięci. Ale całkowicie ignoruje współrzędną Z podczas jakiejkolwiek analizy przestrzennej. Jeśli zapytasz o dystans między dwoma punktami, Shapely obliczy płaską odległość 2D. Nie oblicza objętości 3D ani dystansów 3D. To biblioteka czysto planarna. Oto kluczowa sprawa. Shapely opiera się na matematycznej teorii zbiorów punktów. Nie postrzega kształtu tylko jako garstki wierzchołków, które wpisałeś w kodzie. Zamiast tego traktuje każdą geometrię jako rygorystyczny zbiór zawierający nieskończoną liczbę punktów. W tym modelu każda geometria dzieli całą płaszczyznę 2D na trzy odrębne części. Wnętrze to właściwa substancja kształtu. Granica to krawędź, która ten kształt otacza. Zewnętrze to cała reszta nieskończonej płaszczyzny, która nie jest częścią tego kształtu. Wyobraź sobie modelowanie parku miejskiego, żeby zobaczyć, jak te trzy koncepcje działają w praktyce. Zaczynasz od fontanny, reprezentowanej jako geometria Point. Point jest zerowymiarowy. Reprezentuje pojedynczą, dokładną lokalizację na płaszczyźnie. Ponieważ nie ma długości ani pola powierzchni, jego wnętrze składa się wyłącznie z tej jednej, konkretnej współrzędnej. Point w ogóle nie ma granicy. Każda inna współrzędna na całej płaszczyźnie kartezjańskiej tworzy jego zewnętrze. Następnie dodajesz ścieżkę prowadzącą do fontanny. Jest ona modelowana jako LineString. LineString to jednowymiarowa geometria zdefiniowana przez uporządkowaną sekwencję wierzchołków współrzędnych. Nawet jeśli przekażesz mu tylko współrzędną początkową i końcową, Shapely rozumie LineString jako nieskończony zbiór punktów tworzących ciągłą ścieżkę między nimi. Wnętrze to cała ciągła długość tej ścieżki. Granica składa się z dokładnie dwóch punktów: pierwszej współrzędnej początkowej i ostatniej współrzędnej końcowej. Na koniec modelujesz zarys samego parku za pomocą geometrii Polygon. Polygon to dwuwymiarowa geometria o mierzalnym polu powierzchni. Definiujesz go za pomocą zamkniętego pierścienia współrzędnych, co oznacza, że pierwszy i ostatni punkt są identyczne. Ten zewnętrzny pierścień tworzy granicę Polygonu. Wnętrze to nieskończony zbiór punktów zamkniętych wewnątrz tej granicy. Polygony mogą również zawierać otwory, takie jak zamknięta strefa ochrony przyrody wewnątrz parku. Krawędź tego otworu działa po prostu jako wewnętrzna granica, czysto oddzielając właściwe wnętrze parku od pustej przestrzeni zewnętrznej wewnątrz tego otworu. Shapely nie postrzega twojej geometrii jako pustego szkieletu ze współrzędnych; widzi ciągły obszar przestrzeni matematycznie podzielony na wnętrze, granicę i zewnętrze. Jeśli uważasz, że te odcinki są pomocne i chcesz wesprzeć podcast, wyszukaj DevStoriesEU w serwisie Patreon. To wszystko w tym odcinku. Dzięki za wysłuchanie i twórz dalej!

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 2 z 8. Przetwarzasz batch współrzędnych przestrzennych. Piszesz pętlę, żeby przekształcić każdą parę współrzędnych w kształt, jedna po drugiej. To działa, ale gdy twój dataset rozrasta się do milionów punktów, twoja aplikacja całkowicie się zatrzymuje. Problemem jest overhead Pythona, a rozwiązanie wymaga całkowitego pominięcia standardowego tworzenia obiektów. Ten odcinek jest o tworzeniu geometrii i serializacji. Tworzenie kształtów to logiczny punkt wyjścia. Jeśli masz do czynienia z pojedynczą lokalizacją, utworzenie instancji geometrii jest proste. Importujesz pojedynczą klasę Point i przekazujesz jej wartości X i Y. Jest to czytelne, ale powolne. Oto kluczowa sprawa. Shapely udostępnia zwektoryzowane funkcje uniwersalne, które operują bezpośrednio na tablicach NumPy. Zamiast używać pojedynczej klasy Point w pętli Pythona, używasz funkcji shapely dot points w liczbie mnogiej. Przekazujesz jej dwuwymiarową tablicę współrzędnych, a ona spycha całą iterację do wysoce zoptymalizowanego poziomu w C. W rezultacie otrzymujesz tablicę obiektów geometrycznych zwróconą w ułamku czasu. Dotyczy to wszystkiego, z funkcjami w liczbie mnogiej dostępnymi dla obiektów typu LineString, Polygon i LinearRing. Załóżmy, że budujesz narzędzie do routingu i musisz załadować dataset tysiąca punktów dostawy. Dane przychodzą jako tablica payloadów GeoJSON. To prowadzi nas do serializacji. Musisz sparsować te stringi na rzeczywiste obiekty geometryczne w pamięci. Może cię kusić, żeby użyć standardowego parsowania JSON i ręcznie wyciągnąć współrzędne, aby zbudować swoje kształty. Nie rób tego. Shapely ma wbudowane funkcje wejścia i wyjścia dla trzech głównych formatów przestrzennych: Well-Known Text, Well-Known Binary i GeoJSON. Podobnie jak tworzenie geometrii, te funkcje parsujące są zwektoryzowane. Bierzesz całą swoją tablicę tysiąca stringów GeoJSON i przekazujesz ją bezpośrednio do funkcji shapely dot from geojson. Parsuje ona cały batch na raz i zwraca wysokowydajną tablicę geometrii. Gdyby twoje dane były w formacie tekstowym, użyłbyś shapely dot from wkt. Gdyby były w formacie binarnym, użyłbyś shapely dot from wkb. To tyle, jeśli chodzi o wejścia. A co z wyjściami? Kiedy skończysz przetwarzać swoje punkty dostawy, musisz je zapisać lub wysłać do bazy danych. Odwracasz ten proces, używając funkcji eksportujących. Jeśli debugujesz i musisz odczytać współrzędne na własne oczy, używasz shapely dot to wkt. Well-Known Text daje ci czytelny dla człowieka string, wypisujący typ geometrii, a po nim współrzędne. Jednak parsowanie tekstu jest kosztowne i zajmuje dużo miejsca. Jeśli wysyłasz te dane do przestrzennej bazy danych lub zapisujesz je na później, powinieneś użyć shapely dot to wkb. Well-Known Binary to surowa reprezentacja bajtowa geometrii. Ten format jest znacznie mniejszy, pozwala uniknąć utraty precyzji przy konwersji zmiennoprzecinkowej na stringi i jest znacznie szybszy do odczytu i zapisu dla maszyn. Przekazujesz swoją tablicę geometrii do shapely dot to wkb i otrzymujesz tablicę byte stringów gotową do zapisu. Zawsze, gdy przenosisz dane przestrzenne do lub z aplikacji, pamiętaj, że pętle w Pythonie to twój wróg. Najważniejszym nawykiem dla wydajności jest przekazywanie pełnych tablic do funkcji Shapely w liczbie mnogiej, pozwalając podległej bibliotece w C wykonać najcięższą pracę w jednym przebiegu. Dzięki za wysłuchanie, miłego kodowania wszystkim!

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 3 z 8. Zwykła odległość mówi ci, jak blisko siebie znajdują się dwie linie. Ale jeśli chcesz wiedzieć, jak maksymalnie mogą się od siebie oddalić, zwykła odległość jest całkowicie bezużyteczna. Żeby na to odpowiedzieć, musisz zrozumieć Measurement i Properties. Każdy obiekt geometryczny w Shapely ma wbudowane atrybuty, które opisują jego fizyczne wymiary. Te najbardziej podstawowe to area, length i bounds. Property area podaje ci dwuwymiarową przestrzeń zajmowaną przez dany kształt. Dla poligonu jest to liczba dodatnia. Dla punktów i linii, area wynosi dokładnie zero. Property length zwraca jednowymiarowy rozmiar geometrii. Dla linii jest to odległość od początku do końca ścieżki. Property bounds podaje dokładne limity współrzędnych twojego kształtu. Zwraca czteroelementową tuplę reprezentującą minimalne X, minimalne Y, maksymalne X i maksymalne Y. To jest twój bounding box. Wyobraź sobie scenariusz, w którym masz dwa ślady GPS biegaczy, oba reprezentowane jako LineStrings. Odczytujesz property length, żeby sprawdzić całkowity dystans pokonany przez każdą osobę. Odczytujesz property bounds, żeby zdefiniować dokładny, prostokątny viewport potrzebny do wyświetlenia obu tras na ekranie. Matematyka staje się trudniejsza, kiedy musisz zmierzyć przestrzeń między tymi dwoma śladami. Standardowy pomiar odległości zwraca absolutnie najkrótszą przerwę między dwiema geometriami. Skanuje ślad A, skanuje ślad B i znajduje jedną, najbliższą sobie parę punktów. Jeśli dwaj biegacze skrzyżowali swoje ścieżki na skrzyżowaniu w połowie biegu, standardowa odległość między ich śladami wynosi zero. I tu jest kluczowa sprawa. Ludzie często mylą zwykłą odległość z Hausdorff distance. Zwykła odległość znajduje najbliższe punkty. Hausdorff distance znajduje największą odległość między najbliższymi punktami. Pomyśl o Hausdorff distance jako o pomiarze maksymalnego odchylenia. Reprezentuje najdłuższą przerwę, którą musiałbyś pokonać, gdyby ktoś umieścił cię w najgorszym możliwym miejscu na jednym śladzie i kazał ci iść do najbliższego punktu na drugim śladzie. Jeśli nasi dwaj biegacze wystartowali z tego samego miejsca, rozdzielili się na dwie mile w połowie treningu i skończyli w tym samym miejscu, zwykła odległość wynosi zero. Hausdorff distance wynosi dwie mile. Definiuje to separację w najgorszym przypadku na całej długości obu geometrii. Jest jeszcze jedna funkcja pomiarowa, która nazywa się minimum clearance. Ta nie porównuje dwóch różnych obiektów. Mierzy stabilność strukturalną pojedynczej geometrii. Minimum clearance oblicza najmniejszą odległość, o jaką może przesunąć się dowolny node, zanim geometria zapadnie się do nieprawidłowego stanu, na przykład linii nakładającej się na samą siebie. Jeśli twoja geometria ma bardzo małe minimum clearance, współrzędne są ściśnięte blisko siebie. Drobny błąd zaokrąglenia podczas eksportu z bazy danych może całkowicie zepsuć kształt. Jeśli chcesz uprościć dane biegaczy, żeby zmniejszyć rozmiar pliku, sprawdzenie minimum clearance powie ci dokładnie, jak daleko możesz przesunąć punkty, zanim geometria sama się zepsuje. Wiedza o tym, jak blisko siebie znajdują się dwa kształty, załatwia sprawę podstawowych kolizji. Znajomość absolutnego, maksymalnego limitu ich separacji decyduje o tym, jak dobrze naprawdę rozumiesz relację przestrzenną między nimi. Dzięki za spędzenie ze mną tych kilku minut. Do usłyszenia następnym razem, trzymaj się.

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 4 z 8. Wytyczasz nową linię metra w pobliżu chronionych mokradeł. Musisz wiedzieć, czy tor idzie prosto przez wodę, czy tylko biegnie jej skrajem. Jak komputer właściwie to oblicza od strony matematycznej? Używa sprytnej macierzy trzy na trzy, aby odpowiedzieć na to pytanie. To prowadzi nas do predykatów przestrzennych i wymiarowo rozszerzonego modelu dziewięciu przecięć, czyli DE-9IM. Predykaty przestrzenne to funkcje binarne. Porównują dwie geometrie i zwracają dokładnie jedną rzecz: True albo False. Nie tworzą nowych kształtów. Nie obliczają nakładających się obszarów. Po prostu odpowiadają tak lub nie na pytania o relacje topologiczne. Pod spodem Shapely ocenia te relacje za pomocą DE-9IM. Każda geometria składa się z trzech części: wnętrza, granicy i zewnętrza. DE-9IM to macierz, która testuje przecięcia tych trzech części pierwszej geometrii z trzema częściami drugiej geometrii. Trzy części razy trzy części dają dziewięć możliwych przecięć. W zależności od tego, które z tych przecięć daje w wyniku zbiór pusty, punkt, linię lub obszar, Shapely określa dokładną relację. Zastosujmy to do naszej linii metra i mokradeł. Najszerszym predykatem jest intersects. Jeśli tor dzieli z mokradłami jakikolwiek punkt, linię lub obszar, intersects zwraca True. To taki podstawowy wariant, który wyłapuje wszystko. Jeśli intersects zwraca False, te dwie geometrie są całkowicie oddzielone w przestrzeni. Ale często potrzebujesz większej precyzji. Chcesz wiedzieć, czy linia metra faktycznie przecina mokradła. Do tego używasz crosses. Linia przecina wielokąt, jeśli jej wnętrze przecina się z wnętrzem wielokąta, ale linia wychodzi także poza ten wielokąt. Macierz DE-9IM sprawdza, czy przecięcie ich wnętrz jest linią, i czy wnętrze linii przecina się również z zewnętrzem wielokąta. Jeśli oba warunki są spełnione, crosses zwraca True. A co, jeśli tor biegnie dokładnie wzdłuż granicy mokradeł, nie wchodząc do wody? Wtedy do gry wchodzi touches. Dwie geometrie stykają się, jeśli mają co najmniej jeden wspólny punkt, ale ich wnętrza w ogóle się nie przecinają. Oddziałują na siebie tylko ich granice. Jeśli tor wejdzie choćby na milimetr we wnętrze mokradeł, touches zwraca False. Teraz wyobraź sobie stację metra zbudowaną całkowicie wewnątrz mokradeł. Tutaj sprawdzasz zawieranie. Ludzie często mylą contains i within, ale to po prostu operacje odwrotne względem siebie. Jeśli mokradła zawierają stację, to stacja jest wewnątrz mokradeł. Geometrycznie oznacza to, że wnętrze i granica stacji są całkowicie otoczone przez wnętrze mokradeł. Żadna część stacji nie przecina się z zewnętrzem mokradeł. Możesz napisać kod sprawdzający, czy mokradła zawierają stację używając contains, albo sprawdzający, czy stacja jest wewnątrz mokradeł używając within. Wynik jest dokładnie taki sam. Oto kluczowy wniosek. Nie musisz uczyć się na pamięć macierzy dziewięciu przecięć, żeby wytyczyć linię metra, ale świadomość jej istnienia wyjaśnia, dlaczego te binarne sprawdzenia są tak niezawodne. Każdy nazwany predykat przestrzenny to po prostu konkretny wzorzec flag True i False w tej matematycznej macierzy pod spodem. Dzięki za wspólnie spędzony czas. Mam nadzieję, że dowiedziałeś się czegoś nowego.

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 5 z 8. Diagramy Venna to nie tylko zbiory logiczne czy zapytania do bazy danych. Możesz użyć dokładnie tych samych zasad matematycznych, żeby fizycznie podzielić geografię w prawdziwym świecie. Żeby to zrobić, potrzebujesz operacji na zbiorach. W Shapely każda geometria to w zasadzie nieskończony zbiór punktów na dwuwymiarowej płaszczyźnie. Ponieważ są to zbiory, możesz nimi manipulować przy użyciu klasycznej teorii mnogości. Najpierw musimy wyjaśnić częste źródło nieporozumień. Predykaty przestrzenne, takie jak sprawdzanie, czy dwa kształty się stykają lub przecinają, sprawdzają warunek i zwracają proste True lub False. Operacje na zbiorach robią coś zupełnie innego. Zwracają zupełnie nowe obiekty geometryczne. Biorą dwa kształty wejściowe, analizują ich punkty wspólne i konstruują zupełnie nowy, trzeci kształt jako output. Weźmy konkretny scenariusz. Masz dwa zbiory danych z poligonami. Jeden reprezentuje starą mapę strefy powodziowej. Drugi to nowo zaktualizowany model ryzyka powodziowego. Musisz obliczyć dokładny obszar, w którym te dwa modele się pokrywają. Do tego używasz metody intersection. Wywołujesz intersection na pierwszej geometrii i przekazujesz drugą geometrię jako argument. Shapely analizuje przestrzenne nakładanie się i zwraca nowy poligon zawierający tylko te punkty, które istnieją zarówno na starej, jak i na nowej mapie. Jeśli te dwa kształty w ogóle się nie nakładają, zwraca pustą geometrię. A co, jeśli musisz znaleźć wyłącznie nowe obszary ryzyka? To te okolice, które były bezpieczne na starej mapie, ale teraz znajdują się w zaktualizowanej strefie powodziowej. Tutaj używasz metody difference. Bierzesz geometrię nowego modelu powodziowego i wywołujesz difference, przekazując geometrię starej mapy. To zwraca kształt zawierający wszystkie punkty z nowego modelu, z wyraźnym pominięciem tych punktów, które były już w starym. Kolejność ma tu kluczowe znaczenie. Jeśli ją odwrócisz i wywołasz difference na starej mapie, przekazując nowy model, otrzymasz zupełnie inny wynik. Otrzymasz obszary, które nie są już uważane za zagrożone. To po prostu przestrzenne odejmowanie. Czasami nie chcesz porównywać kształtów, chcesz je po prostu połączyć. Jeśli służby ratunkowe potrzebują głównej mapy wszystkich miejsc, które kiedykolwiek oznaczono jako zagrożone powodzią, używasz metody union. Wywołujesz union na jednym kształcie, przekazujesz drugi, a Shapely je łączy. Jeśli kształty się nakładają, wewnętrzne granice znikają. Outputem jest pojedyncza, ciągła geometria reprezentująca wszystkie punkty z obu oryginalnych kształtów. Na koniec mamy metodę symmetric difference. Pomyśl o tym jak o przestrzennym odpowiedniku operacji exclusive OR. Zwraca ona nową geometrię zawierającą punkty, które są albo na starej, albo na nowej mapie, ale absolutnie nie na obu naraz. W naszym powodziowym scenariuszu, ta jedna operacja daje ci dokładnie te obszary, w których oba modele się nie zgadzają. Zwraca nowo dodane strefy ryzyka razem z nowo usuniętymi strefami, całkowicie wycinając obszary, w których modele są zgodne. Oto kluczowy wniosek. Kiedy przestajesz myśleć o granicach przestrzennych jak o złożonych koncepcjach geograficznych, a zaczynasz traktować je jak podstawowe zbiory matematyczne, obliczanie skomplikowanych nakładek i wykluczeń staje się przewidywalnym, całkowicie standardowym procesem. To wszystko w tym odcinku. Dzięki za wysłuchanie i buduj dalej!

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 6 z 8. Zwykły punkt matematyczny ma dokładnie zerową powierzchnię. To tylko lokalizacja. Ale co, jeśli musisz wyznaczyć promień rażenia wokół tej lokalizacji? Możesz błyskawicznie przekształcić ten zerowymiarowy punkt w ogromny, precyzyjny wielokąt. To właśnie potęga operacji konstruktywnych, a konkretnie bufferów i hulli. Operacje konstruktywne biorą istniejącą geometrię i budują z niej nową, inną geometrię na podstawie jej właściwości przestrzennych. Możesz o nich myśleć jak o ochronnych wrapperach dla twoich danych przestrzennych. Najczęściej używaną operacją konstruktywną jest buffer. Przekazujesz wartość dystansu do funkcji buffer, a Shapely zwraca wielokąt reprezentujący wszystkie punkty znajdujące się dokładnie w tej odległości od twojej oryginalnej geometrii. Jeśli masz linię reprezentującą trasę wycieku chemicznego wzdłuż autostrady i musisz wyznaczyć 50-metrową strefę bezpieczeństwa, wywołujesz metodę buffer na tej geometrii linii z dystansem 50. Wynikiem jest nowy wielokąt, który śledzi całą trasę, rozszerzając się na zewnątrz dokładnie o 50 metrów w każdym kierunku. Oto kluczowa sprawa. Buffery nie tylko rosną. Mogą się również kurczyć. Jeśli przekażesz dodatni dystans, geometria pęcznieje. Jeśli zastosujesz ujemny dystans do wielokąta, geometria się kurczy. Ujemny buffer ściąga granice do wewnątrz. Jest to niezwykle przydatne do znalezienia bezpiecznego, wewnętrznego rdzenia strefy, izolując obszar, który znajduje się w ścisłej odległości od niebezpiecznych krawędzi. Czasami nie potrzebujesz dokładnego buffera wokół złożonych kształtów. Potrzebujesz tylko absolutnych granic swoich danych. Wywołanie właściwości envelope daje ci dokładnie to. Zwraca ona bounding box, czyli najmniejszy, idealnie pionowy prostokąt, który całkowicie otacza twoją geometrię. Jest matematycznie tani w obliczeniach i idealnie nadaje się do szybkiego indeksowania przestrzennego. Ale co się stanie, gdy twoje dane nie są jednolitym kształtem, tylko rozproszonym zbiorem punktów? Jeśli masz dziesiątki próbek zanieczyszczonej gleby i musisz narysować jedną, ciągłą granicę wokół dotkniętego obszaru, potrzebujesz hulla. Shapely daje ci dwa główne sposoby, aby to zrobić. Convex hull oblicza najmniejszy wypukły wielokąt, który zawiera wszystkie twoje geometrie. Możesz to sobie wyobrazić jako naciągnięcie gumki recepturki na deskę pełną kołków. Gumka mocno zaciska się na skrajnych kołkach. Ponieważ jest wypukła, granica nigdy nie zapada się do wewnątrz. Nie ma tu kątów wewnętrznych większych niż 180 stopni. Chociaż convex hull jest niezawodny, często obejmuje dużą ilość pustej przestrzeni, jeśli twoje punkty tworzą kształt półksiężyca lub nieregularne skupisko. Jeśli potrzebujesz ściślejszego dopasowania, używasz concave hulla. Zamiast sztywnej gumki recepturki, concave hull działa jak folia termokurczliwa. Pozwala granicy zapaść się do wewnątrz, aby podążać za rzeczywistym śladem twoich danych. Kontrolujesz to, jak ściśle przylega, dostosowując parametr, który ogranicza maksymalną dozwoloną długość krawędzi granicy. Bardziej restrykcyjne limity wymuszają, aby granica zagięła się w szczeliny między punktami, dając ci bardzo dokładną i realistyczną mapę tej zanieczyszczonej gleby. Różnica między tymi narzędziami sprowadza się do tego, jak ściśle przylegają do twoich danych. Envelope daje ci szybki, luźny bounding box, convex hull rozciąga się ciasno na skrajnych punktach zewnętrznych, concave hull obkurcza się na dokładnym kształcie, a buffer ściśle powiększa krawędzie o zdefiniowany dystans. Jeśli chcesz pomóc w tworzeniu kolejnych odcinków, możesz wesprzeć program, wyszukując DevStoriesEU na platformie Patreon. To wszystko w tym odcinku. Dzięki za słuchanie i twórz dalej!

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 7 z 8. Spróbuj wyrenderować linię brzegową z miliona punktów na mapie internetowej, a szybko zawiesisz przeglądarkę użytkownika. Potrzebujesz sposobu na zmniejszenie rozmiaru tych danych do jednego procenta pierwotnej wielkości, tak aby nadal wyglądały identycznie. Wymaga to zaawansowanych operacji konstrukcyjnych. Głównym narzędziem do takiego czyszczenia danych jest funkcja simplify. Słuchacze czasami myślą, że uproszczenie kształtu oznacza po prostu pominięcie co drugiego lub trzeciego punktu w arrayu. Takie podejście niszczy geometrię. Tworzy samoprzecinające się linie, spłaszcza małe wyspy i rujnuje strukturę topologiczną. Funkcja simplify w Shapely ocenia rzeczywistą geometrię. Przekazujesz do niej swoją złożoną linię brzegową i wartość tolerancji. Funkcja usuwa wierzchołki, które nie odchylają się od głównego kształtu o więcej niż wynosi ta tolerancja. Co kluczowe, Shapely udostępnia ci flagę do zachowania topologii. Gdy jest włączona, algorytm aktywnie sprawdza, czy usunięcie punktu spowoduje, że poligon przetnie sam siebie lub podzieli się na nieprawidłowe części. To gwarantuje, że twoja mocno skompresowana linia brzegowa pozostanie matematycznie poprawna. Kiedy już uprościsz ciężką warstwę bazową, często potrzebujesz, aby inne warstwy idealnie do niej pasowały. Załóżmy, że masz działki lub granice posesji, które kończą się dokładnie na linii wody. Ponieważ właśnie uprościłeś linię brzegową, jej krawędzie nieznacznie się przesunęły. Tworzy to mikroskopijne nakładania się lub puste przestrzenie, znane jako slivery. Naprawiasz to za pomocą funkcji snap. Podajesz geometrię granicy posesji, geometrię linii brzegowej i ścisłą tolerancję dystansu. Snap patrzy na wierzchołki pierwszego kształtu. Jeśli wierzchołek znajduje się w odległości tolerancji od wierzchołka lub segmentu drugiego kształtu, zostaje bezpośrednio na niego przyciągnięty. Punkty poza tolerancją zostają dokładnie tam, gdzie były. Tworzy to szczelne, idealne dopasowanie między sąsiadującymi geometriami, bez zniekształcania reszty kształtu. To by było na tyle, jeśli chodzi o czyszczenie istniejących kształtów. Drugą stroną operacji konstrukcyjnych jest dzielenie pustej przestrzeni za pomocą punktów. Jeśli weźmiesz wierzchołki geometrii, możesz przekazać je do funkcji delaunay triangles. Łączy ona te punkty, tworząc ciągłą siatkę nienakładających się na siebie trójkątów. Logika rysuje te trójkąty tak, aby zmaksymalizować najmniejsze kąty wewnętrzne. Zapobiega to powstawaniu długich, igłowatych trójkątów, tworząc zbalansowaną siatkę, bardzo przydatną do renderowania terenu. Jeśli chcesz uzyskać tylko zarys tych połączeń, a nie wypełnione kształty, możesz ustawić flagę, aby funkcja zwróciła tylko krawędzie. Ściśle powiązana z tym jest funkcja voronoi polygons. Podczas gdy Delaunay łączy punkty, Voronoi rysuje granice między nimi. Podajesz geometrię, a Shapely używa jej wierzchołków do podzielenia otaczającego obszaru na całkowicie odrębne regiony poligonowe. Każde miejsce wewnątrz konkretnego poligonu Voronoi jest bliżej jego centralnego punktu generującego, niż jakiegokolwiek innego punktu w całym zbiorze. Jeśli analizujesz rozproszone centra dostaw, poligony Voronoi błyskawicznie mapują dokładną strefę zasięgu dla każdego z nich, bazując wyłącznie na bliskości. Podobnie jak przy Delaunay, możesz poinstruować funkcję, aby zwróciła tylko krawędzie graniczne, jeśli nie potrzebujesz pełnych poligonów. Oto kluczowy wniosek. Rzeczywiste dane przestrzenne są gęste, rozłączone i rzadko idealnie do siebie pasują. Operacje konstrukcyjne, takie jak simplify, snap i Voronoi, dają ci narzędzia do wymuszenia matematycznego porządku, dzięki czemu dane są wystarczająco lekkie do wyrenderowania i wystarczająco precyzyjne do analizy. Dzięki za spędzenie ze mną tych kilku minut. Do usłyszenia następnym razem, trzymaj się.

Cześć, tu Alex z DEV STORIES DOT EU. Shapely, odcinek 8 z 8. Porównanie pojedynczego punktu z milionem poligonów wymaga ogromnej mocy obliczeniowej, a jednak niektóre aplikacje robią to w milisekundy. Nie obliczają każdej odległości. Odfiltrowują dziewięćdziesiąt dziewięć procent danych, zanim w ogóle wykonają jakiekolwiek równanie matematyczne. Na tym właśnie polega wysokowydajne indeksowanie przestrzenne za pomocą STRtree. Załóżmy, że chcesz znaleźć najbliższą kawiarnię spośród dziesięciu tysięcy lokalizacji względem aktualnych współrzędnych GPS użytkownika. Jeśli zaczniesz liczyć dokładną odległość do każdego lokalu, twój system po prostu się zatka. Zamiast tego, indeksowanie przestrzenne wykorzystuje R-tree. Pomyśl o R-tree jak o hierarchicznym systemie folderów dla przestrzeni dwuwymiarowej. Rysuje on prosty prostokąt, nazywany bounding boxem lub envelope, wokół klastrów pobliskich geometrii. Następnie rysuje większe boxy wokół tych boxów. Sprawdzenie, czy dwa proste prostokąty się na siebie nakładają, jest operacją bardzo tanią obliczeniowo. W Shapely konkretną implementacją jest STRtree, co jest skrótem od Sort-Tile-Recursive. Tworzysz je, przekazując array geometrii do konstruktora. Pod spodem wykonuje to bulk-load indeksu. Drzewo budowane jest tylko raz i jest immutable. Po jego utworzeniu nie możesz dodawać ani usuwać elementów. Musisz przygotować cały swój dataset z góry. Kiedy drzewo już istnieje, przeszukujesz je za pomocą metody query. Przekazujesz geometrię wejściową, a metoda zwraca array NumPy z indeksami typu integer. Te indeksy mapują się bezpośrednio na oryginalną sekwencję geometrii, której użyłeś do zbudowania drzewa. Jeśli podasz wiele geometrii na raz, query zwróci dwuwymiarowy array, parując indeksy twoich danych wejściowych z pasującymi indeksami w drzewie. I tu jest kluczowa sprawa. Bazowy indeks STRtree sprawdza tylko bounding boxy, a nie dokładne geometrie. Jeśli odpytujesz złożony poligon, drzewo używa kwadratowego envelope'a tego poligonu, aby znaleźć dopasowania. To daje ci krótką listę kandydatów zawierającą false positives. Aby uzyskać dokładną odpowiedź, Shapely pozwala ci przekazać predykat przestrzenny, taki jak intersects lub contains, bezpośrednio do metody query jako argument. Drzewo najpierw używa tanich bounding boxów do znalezienia kandydatów, a następnie automatycznie ewaluuje twój dokładny predykat na tej krótkiej liście. Dzięki temu ciężka matematyczna robota pozostaje w skompilowanym kodzie C. Poza sprawdzaniem nakładania się, STRtree świetnie radzi sobie z bliskością. Wracając do naszego scenariusza z kawiarnią, nie musisz ręcznie sprawdzać envelope'ów. Używasz metody query nearest. Przekazujesz punkt GPS użytkownika, a drzewo przechodzi przez swoje hierarchiczne boxy, aby znaleźć absolutnie najbliższą geometrię bez mierzenia odległości do wszystkich dziesięciu tysięcy. Natychmiast zwraca indeks najbliższego lokalu. Możesz również podać parametr, aby zwrócić array N najbliższych sąsiadów, albo ustawić maksymalny threshold odległości, aby całkowicie ograniczyć promień wyszukiwania. Istnieje również osobna metoda nearest, która porównuje ze sobą dwa oddzielne drzewa, aby znaleźć najbliżej pasujące do siebie pary geometrii między nimi. Same operacje na geometriach są zawsze najdroższą częścią analizy przestrzennej. STRtree działa jak bezlitosny filtr. Zapobiega marnowaniu cykli procesora na geometrie, które w ogóle nie są blisko siebie, dostarczając malutką, łatwą do ogarnięcia krótką listę, dzięki czemu twoje dokładne matematyczne sprawdzenia uruchamiają się tylko wtedy, gdy jest to absolutnie konieczne. To kończy naszą serię o Shapely. Gorąco zachęcam cię do przejrzenia oficjalnej dokumentacji i wypróbowania tych koncepcji indeksowania w praktyce na twoich własnych datasetach. Jeśli masz jakieś workflowy lub narzędzia, które chciałbyś, żebyśmy omówili w przyszłych seriach, odwiedź devstories dot eu i zostaw nam sugestię. Dzięki za słuchanie. Do usłyszenia następnym razem!