ppt_sablona_pozadi Kartografické modelování VIII – Modelování vzdálenosti jaro 2015 Petr Kubíček kubicek@geogr.muni.cz Laboratory on Geoinformatics and Cartography (LGC) Institute of Geography Masaryk University Czech Republic logo_mu ppt_sablona_pozadi Vzdálenostní funkce •Obalová/Nárazníková zóna •Obalová/Nárazníková zóna – buffer •Nákladové vzdálenosti –Funkce šíření a proudění •VEKTOR RASTR •Základem je Euklidovská vzdálenost •Matice vzdáleností •Identifikace nejbližšího souseda ppt_sablona_pozadi Kartografické modelování Analýza vzdáleností - opakování •Tvorba obálek (buffer) •Konvexní obálka (convex hull) •Nearest - geometrie •Analýzy sousedství (Proximy analysis) – Thiesen polygons, Voronoi – konstrukce?? • ppt_sablona_pozadi Kartografické modelování [USEMAP] Konstrukce bufferu - vektor • Buffer illustration ppt_sablona_pozadi Kartografické modelování Konvexní obálka • ppt_sablona_pozadi Vzdálenost objektů •Nejbližší objekt • • • • • •Vzdálenost všech objektů near ptdist_arc ppt_sablona_pozadi Kartografické modelování Principy výpočtu vzdáleností •Výpočet vzdálenosti závisí na typu geometrie (a souřadnicovém systému). Tři hlavní pravidla určující způsob výpočtu: –Vzdálenost mezi body je přímá spojnice obou bodů. –Vzdálenost mezi bodem a linií je buďto kolmice, nebo vzdálenost k nejbližšímu vrcholu. –Vzdálenost mezi liniemi je určena vzdálenostmi vrcholů jednotlivých segmentů (více možností, počítá se nejkratší). • ppt_sablona_pozadi Kartografické modelování • How distances are calculated between features ppt_sablona_pozadi ppt_sablona_pozadi Kartografické modelování Euklidovské vzdálenosti Euclidean Distance illustration ppt_sablona_pozadi Kartografické modelování Euklidovské vzdálenosti (2) EUKLID_RASTER The Euclidean distance output raster contains the measured distance from every cell to the nearest source. The distances are measured as the crow flies (Euclidean distance) in the projection units of the raster, such as feet or meters, and are computed from cell center to cell center. The Euclidean Distance tool is used frequently as a stand-alone tool for applications, such as finding the nearest hospital for an emergency helicopter flight. Alternatively, this tool can be used when creating a suitability map, when data representing the distance from a certain object is needed. In the example below, the distance to each town is identified. This type of information could be extremely useful for planning a hiking trip. You may want to stay within a certain distance of a town in case of emergency or know how much farther you have to travel to pick up supplies. ppt_sablona_pozadi Kartografické modelování Další eukleidovské míry •Směr k nejbližšímu zdroji – úhel ve stupních k nejbližšímu zdroji. •360 st., 0=S, The Euclidean direction output raster contains the azimuth direction from each cell to the nearest source. Euclidean direction assigns the direction of each cell in degrees to its nearest source. A 360-degree circle or compass is used, with 360 being to the north and 1 to the east; the remaining values increase clockwise. The value 0 is reserved for the source cells. In the example below, the direction to the nearest town is found from every location. This could provide useful information for an emergency helicopter when transporting an injured hiker to the nearest town for medical treatment. ppt_sablona_pozadi Kartografické modelování Přiřazení nejbližšího zdroje •Každá buňka je přiřazena ke zdroji, ke kterému je nejblíže na základě eukleidovské vzdálenosti. •Buňce je přiřazena hodnota podle cílové buňky. Every cell in the Euclidean allocation output raster is assigned the value of the source to which it is closest, as determined by the Euclidean distance algorithm. Each cell in an allocation receives the value of the zone to which it will be allocated. A source is any cell or set of cells with the same value or belonging to the same zone. If a zone is disconnected, the value assigned to the cells allocated to that zone is the distance of the closest region of the zone. ppt_sablona_pozadi Kartografické modelování Neuklidovské vzdálenosti •Sférická vzdálenost •Manhattan distance •Nákladové vzdálenosti File:Manhattan distance.svg \sqrt{72} \approx 8.4853 ppt_sablona_pozadi Kartografické modelování Vážené vzdálenosti •Vážená vzdálenost si všímá jedné podstatné vlastnosti, a to, že při běžných vzdálenostních analýzách se vůbec neuvažují vlivy okolí, vše je měřeno vzdušnou čarou za ideálních podmínek. •V reálném světě ale tento model zdaleka neodpovídá skutečnosti. ppt_sablona_pozadi Kartografické modelování Vážené vzdálenosti •Reálná vzdálenost často neodpovídá vzdálenosti „vzdušnou čarou“ („as the crow flies“). –Má na ni vliv tvar terénu (do kopce se jde hůře než z kopce), tvar komunikační sítě, povrch a jeho prostupnost a další. –Tyto faktory lze do analýzy zahrnout právě pomocí vážené vzdálenosti. •Nejprve se vytváří povrch nákladů / nákladový vzdálenostní povrch (cost surface). –Tento povrch zahrnuje všechny možné vlastnosti reálného světa - faktory, které mohou ovlivnit reálnou vzdálenost (lépe řečeno dobu přepravy) mezi dvěma objekty. Lze jej charakterizovat jako povrch, jehož „každá buňka ví, jak drahé je její překonání“. –Jeho správná tvorba je klíčová pro to, aby následující analýzy dávaly reálné výsledky. ppt_sablona_pozadi Kartografické modelování Faktory ovlivňující vzdálenost •Vlastnosti reálného světa ovlivňující reálnou vzdálenost: –objekty (antropogenní prvky, krajinný pokryv) nacházející se na povrchu, –průběh terénu, s ním související převýšení, –převládající směr větru, •následně se modelují jako faktory ... •Faktory modelující vlastnosti reálného světa: –frikční povrch, –faktor terénu (reliéfu), –vertikální faktor, –horizontální faktor, •se skládají do výsledného povrchu nákladů (nákladového vzdálenostního povrchu) ppt_sablona_pozadi Kartografické modelování Frikční povrch („povrch odporu krajinného pokryvu“) •vzniká reklasifikací DMÚ (/využití půdy – Land Use) podle nákladovosti na překonání jednotlivých buněk, •každé buňce se přiřadí informace o tom jak snadno či obtížně se po ní lze pohybovat, •zohledňuje objekty (antropogenní prvky, krajinný pokryv) nacházející se na povrchu. ppt_sablona_pozadi Kartografické modelování Faktor terénu (reliéfu) •Izotropní (nezávislá na směru), nezáleží na směru pohybu (počítá se z DMR). ppt_sablona_pozadi Kartografické modelování Vertikální faktor •anizotropní, záleží na směru pohybu (počítá se ze sklonů svahů). •d‘ ppt_sablona_pozadi Kartografické modelování Horizontální faktor •anizotropní •účinek převládajícího horizontálního směru působení faktoru na energii, kterou musíme vynaložit abychom překonali buňku. ppt_sablona_pozadi Kartografické modelování Povrch nákladů •Je pak počítán jako funkce všech faktorů. •Každý z modelovaných faktorů má jiný rozsah hodnot. –Např. metry pro rovinnou vzdálenost mohou mít jinou váhu než, metry pro převýšení (vertikální vzdálenost). S metry je dále třeba sjednotit jednotky z frikčního povrchu. •Obecně nejtěžší část geografických analýz – dokázat vymyslet takový vztah (funkci) aby analýza skutečně dobře fungovala. •Povrch nákladů lze charakterizovat jako povrch, jehož každá buňka ví, „jak drahé je její překonání“. •Zanedbáme-li všechny další faktory, můžeme za základní povrch nákladů považovat i frikční povrch. ppt_sablona_pozadi Kartografické modelování Povrch vážené vzdálenosti •počítá se z povrchu nákladů •lze jej charakterizovat, jako povrch, který má minimum v cílovém bodě a každá jeho buňka ví kudy se dostat do cílového bodu nejrychleji. •Lze jej popsat jako "hrbolatý trychtýř", jehož ústím je právě cílový bod. ppt_sablona_pozadi ppt_sablona_pozadi Kartografické modelování Výpočet frikčního povrchu(cost distance) •Ve výstupním rastru jsou buňkám přiřazeny hodnoty akumulované vzdálenosti k nejbližší zdrojové buňce. •Výpočet používá teorii grafů – hrana a uzel (střed buňky a jejich spojnice). •Každá spojnice má určitý odpor závisející na hodnotě váhy buněk. Odpor se odvozuje z buněk na obou koncích hran. •Výpočet závisí na: –Velikosti buňky (v základních měřících jednotkách – pixel) –Prostorové orientaci uzlů – přímý x šikmý. The Cost Distance tool creates an output raster in which each cell is assigned the accumulative cost to the closest source cell. The algorithm utilizes the node/link cell representation used in graph theory. In the node/link representation, each center of a cell is considered a node and each node is connected to its adjacent nodes by multiple links. Every link has an impedance associated with it. The impedance is derived from the costs associated with the cells at each end of the link (from the cost surface) and from the direction of movement through the cells. The cost assigned to each cell represents the cost per unit distance for moving through the cell. The final value per cell is the cell size multiplied by the cost value. For example, if the cost raster has a cell size of 30, and a particular cell has a cost value of 10, the final cost of that cell is 300 units. Node travel costs The cost to travel between one node and the next is dependent on the spatial orientation of the nodes. How the cells are connected also impacts the travel cost. ppt_sablona_pozadi Kartografické modelování Výpočet ceny pro sousední buňky •1,4142?? ppt_sablona_pozadi Kartografické modelování Příklad vytváření •Vstupní rastry – zdroje a váhy (ceny). •První přiblížení – pro okolní buňky. •0 = zdroj Accumulative cost cell list Creating an accumulative cost-distance raster using graph theory can be viewed as an attempt to identify the lowest-cost cell and add it to an output list. It is an iterative process that begins with the source cells. The goal of each cell is to be assigned quickly to the output cost-distance raster. In the first iteration, the source cells are identified and assigned 0 since there is no accumulative cost to return to themselves. Next, all the source cell's neighbors are activated, and a cost is assigned to the links between the source cell nodes and the neighboring cells' nodes using the above accumulative cost formulas. Each of these neighborhood cells can reach a source; consequently, they can be chosen or assigned to the output accumulative cost raster. To be assigned to the output raster, a cell must have the next least-cost path to a source. The accumulative cost values are arranged in a list from the lowest accumulative cost to the highest. ppt_sablona_pozadi Kartografické modelování Příklad výpočtu pokračování •Vybrána buňka s nejnižší hodnotou a ta je přiřazena k výstupnímu rastru. •Je rozšířen seznam aktivních buněk (žlutá) a proběhne další iterace. The lowest cost cell is chosen from the active accumulative cost cell list, and the value for that cell location is assigned to the output cost-distance raster. The list of active cells expands to include the neighbors of the chosen cell, because those cells now have a way to reach a source. Only those cells that can possibly reach a source can be active in the list. The cost to move into these cells is calculated using the accumulative cost formulas. ppt_sablona_pozadi Kartografické modelování Příklad výpočtu pokračování •Pokračující iterace. •Zapojení dalších buněk do výpočtu. ppt_sablona_pozadi Kartografické modelování Výsledek Cost distance •0 – je pro zdrojové buňky. •No data – zůstávají bez hodnot. Cost Distance illustration •Eukleid ppt_sablona_pozadi Kartografické modelování Cesta k nejbližšímu zdroji – backlink rastr • „Road map“ - identifikuje „nejlevnější“ cestu mezi buňkou a nejbližším zdrojem. •Využívá algoritmu podobnému D8 Direction coding Directionality to the closest source location, it does not show which source cell to return to or how to get there. The Cost Back Link tool returns a direction raster as output, providing what is essentially a road map that identifies the route to take from any cell, along the least-cost path, back to the nearest source. The algorithm for computing the back link raster assigns a code to each cell. The code is a sequence of integers from 0 to 8. The value 0 is used to represent the source locations, since they have essentially already reached the goal (the source). The values 1 through 8 encode the direction in a clockwise manner starting from the right. Following is the default symbology applied to the directional output, accompanied by an arrow diagram matching directional arrows to the color symbology: ppt_sablona_pozadi Kartografické modelování Cost backlink vstupy a výstup • Cost Back Link illustration Direction coding Direction coding ppt_sablona_pozadi Kartografické modelování Nalezení nejlevnější cesty •Povrch vážené vzdálenosti a hledání nejlevnější cesty •V praxi je hledání nejlevnější cesty řešeno nad povrchem vážené vzdálenosti tak, že z vybrané buňky se postupuje vždy do té buňky z jejího okolí, do které je to „nejvíce z kopce“ (D8). •Cesta je jeden pixel široká. •Využívá výsledků cost distance and back link raster. •Příklad – hořlavost povrchového materiálu, znečištění ovzduší… The least-cost path travels from the destination to the source. This path is one cell wide, travels from the destination to the source, and is guaranteed to be the cheapest route relative to the cost units defined by the original cost raster that was input into the weighted-distance tool. Use the Cost Path tool to find the best route for a new road in terms of construction costs or to identify the path to take from several suburban locations (sources) to the closest shopping mall (destination). When applying the tool to a road construction example, the resulting path is the cheapest route for constructing a road from the destination to the source (the existing intersection). ppt_sablona_pozadi Kartografické modelování Nalezení nejlevnější cesty •Alternativy v závislosti na váze jednotlivých faktorů. • Frikční povrch (land use) + sklon svahu (vertikální faktor) – výsledek závisí na jejich vahách. • Least-cost paths with two different weights You can see two potential paths for the new road in the diagram above (in purple and red). The purple line represents the path created using a cost raster in which each input raster (land use and slope) had the same influence. The red line represents the path created using a cost raster in which the slope input raster had a weight (influence) of 66 percent. By giving the slope input raster a higher weight, more attention was given to avoiding steeper slopes in the red path. ppt_sablona_pozadi Kartografické modelování Příklad •Cesta s mezi dvěma body minimálním sklonem (jedu na kole s vozíkem J). ppt_sablona_pozadi Kartografické modelování • •Slope •Cost distance • •Back Link ppt_sablona_pozadi Kartografické modelování •