Estimation of Accumulated Upstream Drainage Values in Braided Streams Using Augmented Directed Graphs

Presentation Transcript

Estimation of Accumulated Upstream Drainage Values in Braided Streams Using Augmented Directed Graphs Lawrence Stanislawski, Science Applications International Corporation (SAIC) Michael Finn, U.S. Land Survey Michael Starbuck, U.S. Topographical Survey E. Lynn Usery, U.S. Geographical Survey Patrick Turley, U.S. Geographical Survey 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Overview of The National Map National Hydrography Dataset (NHD) – seepage organize Generalization Process for NHD Pruning of Drainage Network Methods Augmented Directed Graph Brute Force Tracing Test Results Summary 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Consistent structure for geographic learning required by the Nation Provides free to high caliber, geospatial information and data from numerous accomplices to help bolster basic leadership by asset supervisors and people in general. Result of a consortium of Federal, State, and nearby accomplices who give geospatial information to upgrade America's capacity to get to, incorporate, and apply geospatial information at worldwide, national, and neighborhood scales. Incorporates eight essential information topics: Orthoimagery, Elevation, Hydrography, Transportation, Structures, Boundaries, Geographic names, Land utilize/arrive cover, Most subjects are populated, and substance will keep on being included and refreshed The National Map 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Created from numerous information sources and Web Map Services (WMS) possessed by numerous associations. Information sources are electronically put away at different scales and resolutions. Therefore, when information are extricated from a few WMS and evenly coordinated in geospatial information applications, the contrasts between information sources get to be distinctly clear. The capacity to render at least one sizes of The National Map data into a fitting, or practically equal, representation at a client determined scale could considerably enhance investigation abilities of these information. Look into Topic: advancement of mechanized speculation approach that renders a practically proportional dataset at a user-indicated scale, concentrating on the National Hydrography Dataset (NHD) layer of The National Map . The National Map 2006 AutoCarto Conference, June 25-28. Vancouver, WA

National Hydrography Dataset Vector information layer of The National Map speaking to surface waters of the United States. Incorporates an arrangement of surface water achieves Reach: noteworthy portion of surface water having comparative hydrologic attributes, for example, an extend of stream between two conjunctions, a lake, or a lake. An interesting location, called an achieve code, is allocated to each achieve, which empowers connecting of subordinate information to particular elements and areas on the NHD. Achieve code from Lower Mississippi subbasin 08 01 00 000413 area subregion - bookkeeping unit - subbasin - achieve number 08010100000413 The National Map National Hydrography Dataset (NHD) 08010100000696 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Linear Canal/Ditch Areal Lake/Pond Linear Streams Areal Stream/River Linear Connector Areal Lake/Pond NHD Features Artificial Paths

National Hydrography Dataset Divided and dispersed at watershed bowl and subbasin limits. Put away in an ArcGIS geographic database (geodatabase) demonstrate. Three levels of detail (resolutions) Medium (1:100,000-scale source) just total layer High (1:24,000-scale source) 75% finish Local (1:12,000 or bigger source) The National Map National Hydrography Dataset (NHD) Subregions along northern shore of Gulf of Mexico 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Develop a speculation technique that can be executed on subsets of the NHD. Procedure ought to create a dataset in the NHD demonstrate design that keeps up: highlight definitions, achieve outlines, include connections, and stream associations between staying summed up elements. Extricated dataset ought to work with NHD applications less detail speedier handling speed Extracted level of detail: client determined Generalization Development of such a speculation procedure could dispense with the need to store and keep up everything except the most elevated determination NHD information layer. 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Base information: most astounding determination NHD that spreads sought range. Highlight pruning – evacuation of components that are too little for fancied yield scale. select a subset of system elements select a subset of zone elements evacuate point highlights related with pruned line or territory highlights Feature rearrangements expulsion of vertices total, amalgamation, combining, and so forth. Center: organize pruning Generalization 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Gasconade-Osage subregion (1029) falls in the Interior Plains and Interior Highlands physiographic divisions. Speculation: Network Pruning Example 2005 ESRI International User Conference, July 25-29. San Diego, CA.

Feature pruning – expulsion of highlight that are too little for wanted yield scale. select a subset of system components Generalization: Network Pruning Example Pruning test on Gasconade-Osage subregion (1029) Green: 1:100,000 Blue: 1:500,000 Red: 1:2,000,000 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Simple Hydrographic Network 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Braided Network 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Complex Coastal Area Network with Cycles 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Directed Graphs Vector Data Layer Nodes Directed Edges (Arcs) Direction speaks to stream

a,(a) (a+b) b,(b) e,(a+b+e) (c+d) c,(c) f, (c+d+f) d,(d) Upstream Drainage Area (a+b+c+d+e+f)

Methods Brute Force Trace – Traces upstream from every hub summing up all waste ranges that are experienced. Exact Slow Augmented Directed Graph Method – Exploits the Arc Suite polygon information structure inside the scope demonstrate, and uses an arrangement of tables to touch base at a speedier final product. Roughly 20x-40x speedier Needs more tests hurried to find exactness 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Augmented Directed Graph Method (One-in-one-out polygon) a,(a) (a) b,(a+b) c,(c+a) (an) (a+b+a+c-a) 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Augmented Directed Graph Method (One-in-mulitple-out polygon) N2 b,(a+b,T1) (d+e+f+h,T3) h d f a,(a) (a,T1) N3 (d+e+f,T2) e N1 i T3 = T1 = c,(a+c,T1) N4 T2 = (d+e+f+i,T4) T4 = 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Node: Sum = Sum – ((Freq – 1) * Value) Augmented Directed Graph Method (Convergence with tables) z,(a+b+c+z,T1) T3 = T1 = (a+b+c+z+a+b+c+y,T3) ∀ N2 (a+b+c+z+y,T3) y,(a+b+c+y,T2) T2 = 2006 AutoCarto Conference, June 25-28. Vancouver, WA

The Cycle Complex Cycles have ended up being the greatest obstruction we have needed to defeat It is imperative to notice that all circular segments on a cycle will have the same upstream waste region Tables ought to likewise be settled and kept up throughout each edge of the cycle complex in question Cycles are the primary explanation behind the vacillation in speed of the expanded chart strategy 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Future Work Convert program to C++ Use ArcObjects to keep a similar usefulness without reevaluating the wheel ArcObjects permits the software engineer to have more control. This will permit the software engineer to expel unnecessary steps Implement a parallel preparing plan Begin handling on the sub bowl level This plan would build the speed of the process by the quantity of processors in the group with a most extreme of the quantity of sub bowls in the United States 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Build a polygon to basic hub table – table recognizes the one-in-one-out and many-out polygons and the related hubs. 2. For each edge streaming out of a zero in-degree hub, set the edge total equivalent to the esteem doled out to the edge, and push the edge total to the entirety on the downstream hub. 3. At each concurrent hub with an entire in-streaming edge total, handle merging tables as expected to lessen the hub whole. 4. At each merged hub with an entire in-streaming edge aggregate, that likewise shuts a one-in-one-out polygon, lessen the hub total by the esteem appointed to the related different polygon. 5. At each unique hub of a one-in-one-out polygon, dole out the hub incentive to the related one-in-one-out polygon, however decrease the hub esteem by qualities in the related hub table, in the event that one exists. 6. For each edge streaming out of a hub with a finished aggregate, add the hub entirety to the edge esteem and push this incentive into the whole on the downstream hub. 7. Rehash steps 3-6 until all edges have values, or cycles are experienced. 8. On the off chance that any cycles are discovered, prepare each cycle complex independently. For each cycle complex, follow upstream edges from one hub in the cycle and allot the whole of the followed edges to one edge in the cycle complex. Rehash steps 3-6 exceptionally for all cycle edges. 9. Rehash step 3-8 until all edges have values. Diagram of Augmented Directed Graph Algorithm 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Results Fabricated dataset Brute drive same as ADG on all circular segments (diff < 0.001 sq km). 111 curves, 1 cycle complex Monotonically Increasing: All tnode values >= edge values. Record FREQUENCY MIN-UPSTR_SQ_KM MAX-UPSTR_SQ_KM 1 111 0.33288 4577.87846 2006 AutoCarto Conference, June 25-28. Vancouver, WA

Results Pomme De Terre subbasin (10290107) in Gasconade-Osag