geography/fGIS/topology.html

   1 <HTML>
   2 <HEAD>
   3 <TITLE>
   4  Creating topology from raster
   5 </TITLE>
   6 </HEAD>
   7 <BODY>
   8
   9
  10 [<A HREF=index.html><I>f(</I><B>GIS</B><I>)</I> home</A>]
  11 [<A HREF=EPU.html>EPU</A>]
  12 <HR>
  13 <H1>Creating topology from raster and vice versa</H1>
  14 <!--CONTENT NUMBERED BACKREFS--><OL>
  15 <LI><A NAME="toc_entry0"></A><A HREF="#toc_section0">Generation of polygon labels</A>
  16 <LI><A NAME="toc_entry1"></A><A HREF="#toc_section1">Generation of vector topology from raster</A>
  17 <LI><A NAME="toc_entry2"></A><A HREF="#toc_section2">Rasterizing polygon coverages</A>
  18 </OL>
  19 <!-- END CONTENT -->
  20
  21 <A NAME="toc_section0"></A><A HREF="#toc_entry0"><H3>Generation of polygon labels</H3></A>
  22 <A HREF=EPU.html>EPU</A> border command should have option to generate
  23 polygon labels along with polygon boundaries.
  24 <P>
  25 This would allow to import polygon maps into vector-based systems like
  26 Arc/Info and also have some additional applications like plotting barchart
  27 and piecharts on the map.
  28 <P>
  29 Currently both EPPL7 and Arc/Info are able to generate polygon labels
  30 given raster map (EPPL7) or correct set of polygon boundaries (ARC/Info).
  31 But their algorithms both have shortcomings. EPPL7 always and Arc/Info in case
  32 of polygon with complex shape put label point too close to polygon boundary.
  33 <P>
  34 While it can be bearable if sole purpose of this label point is to identify
  35 polygon in vector topology map, it is not good for plotting charts other
  36 possible applications of label points.
  37 <P>
  38 So following algorithm is proposed:
  39 <OL>
  40 <LI> Generate unique numbers for polygons (EPU <B>cluster</b> command
  41      already can do this)
  42 <LI> Calculate distance of each raster cell to nearest polygon boundary
  43      (combination of EPPL7  <B>border</B>(epp) and <B>radius</B> commands
  44      can do this and
  45       EPU <B>thiessen</B> command eventually would)
  46
  47 <LI> Find out maximal distance from boundaries for each polygon
  48     (<B>outtable</B> command)
  49 <LI> Retrieve coordinates of any point with given distance and polygon
  50      ID and use it as label point. (can be done with EPPL7
  51      <B>intable</B> and  <B>evaluate</B> and is trivial thing if coded
  52      in C.
  53 </OL>
  54
  55 Analysis of this algorithm shows that it can be performed using at most
  56 two passes over raster, given that all intermediate structures are kept
  57 in memory.
  58 <P>
  59 <I>First pass</I> perform cluster and radius operations in parallel.
  60 Write three intermediate rasters, two of which contain low and high half-words of uniquie polygon numbers and third - distance to boundaries. During
  61 this pass table of maximal distance for each polygon should be accumulated.
  62 <P>
  63 <I>Second pass</I> Find a point for each entry of polygon-distance table and
  64 write its coordinates along with polygon ID.
  65 <P>
  66
  67 <A NAME="toc_section1"></A><A HREF="#toc_entry1"><H3>Generation of vector topology from raster</H3></A>
  68
  69 Vector topology as used by arc/info consist of following parts
  70 <OL>
  71   <LI> No arc in coverage should intersect each other
  72   <LI> Each polygon should have exactly one label
  73   <LI> Each arc should have atributes denoting left and right polygons.
  74   <LI> Each point where arcs are joined (node) should have a record
  75       which lists IDs of arcs joined in it.
  76 </OL>
  77 If we are building polygon coverage from file, generated via EPPL7 or EPU
  78 <B>border</B> commands, constraints 1 and 2 are ensured by border algorithm.
  79 If we are using algorithm described above, for label points, we have
  80 enough information to assign left and right polygon IDs for any polyline
  81 (arc), provided that polylines are generated on second pass of above algorithm.
  82 <P>
  83 So, only thing we need is to create list of nodes. It is also much simplier
  84 to do during raster scan, than processing vector file, becouse while we are
  85 passing location of node, we have all lines joined here at hand, while in
  86 the vector file they can be very far from each other, becouse lines which
  87 <I>starts</I> at this node would be written to the file only when they would
  88 <I>end</I>.
  89 <P>
  90 The only thing which prevents me (and possible other authors of raster-based GIS) to export ready to use topology to ARC/Info instead of exporting GEN files
  91 and requiring user to do time-consuming CLEAN or BUILD operation, is closeness of ARC/Info export format.
  92 <A NAME="toc_section2"></A><A HREF="#toc_entry2"><H3>Rasterizing polygon coverages</H3></A>
  93
  94 EPPL7 <B>rasterize</B> command operates on non-topological vector files.
  95 Therefore it have to do three passes over file and often leave small
  96 holes which have to be eliminated using <b>fill</B> command. But it works
  97 very fast and have (especially in incarnation of EPU <B>cluster</B> command)
  98 almost no limitation concerning raster size and polygon complexity.
  99 <P>
 100 ARC/Info <B>polygrid</B> command produces raster without holes, but it works
 101 very slowly (it seems that it scans entire vector file for each point of
 102 generated raster. In PC Arc/Info 3.5 it also have some very restrictive size
 103 limitation (5000x5000) and doesn't understand EPPL format correctly (doesn't
 104 write coordinate information into header, doesn't support 16-bit rasters).
 105 <P>
 106 But combining of these two algorithms can produce rasterization algorithm
 107 which would be even faster than EPPL7 rasterize and work without holes.
 108 <P>
 109 Idea is that while drawing lines from vector file in the raster (as EPPL
 110 does on the first pass) we plot each line two-cell wide, giving left cell
 111 value of left polygon and right cell value of right polygon. The only thing
 112 left is  to fill remaining parts of file by color of nearest non-offsite
 113 point, which is guarantied to be same for all surrounding lines, due to
 114 ARC/Info topology.
 115 <P>
 116 This algorithm can be implemented without knowledge of ARC/Info propieritary
 117 formats, becouse lines from coverage along with their unique IDs can
 118 be legitimately exported into open GEN format, and arc attribute table,
 119 which contains IDs of right and left polygons can be exported into RDBMS,
 120 as well as polygon attribute table which contain information we really
 121 want to plot.
 122
 123
 124 </BODY>
 125 </HTML>
 126
 127
 128
 129