--- /dev/null
+<HTML>
+<HEAD>
+<TITLE>
+ Creating topology from raster
+</TITLE>
+<BODY>
+
+
+[<A HREF=index.html><I>f(</I><B>GIS</B><I>)</I> home</A>]
+[<A HREF=EPU.html>EPU</A>]
+<HR>
+<H1>Creating topology from raster and vice versa</H1>
+<!--CONTENT NUMBERED BACKREFS--><OL>
+<LI><A NAME="toc_entry0"></A><A HREF="#toc_section0">Generation of polygon labels</A>
+<LI><A NAME="toc_entry1"></A><A HREF="#toc_section1">Generation of vector topology from raster</A>
+<LI><A NAME="toc_entry2"></A><A HREF="#toc_section2">Rasterizing polygon coverages</A>
+</OL>
+<!-- END CONTENT -->
+
+<A NAME="toc_section0"></A><A HREF="#toc_entry0"><H3>Generation of polygon labels</H3></A>
+<A HREF=EPU.html>EPU</A> border command should have option to generate
+polygon labels along with polygon boundaries.
+<P>
+This would allow to import polygon maps into vector-based systems like
+Arc/Info and also have some additional applications like plotting barchart
+and piecharts on the map.
+<P>
+Currently both EPPL7 and Arc/Info are able to generate polygon labels
+given raster map (EPPL7) or correct set of polygon boundaries (ARC/Info).
+But their algorithms both have shortcomings. EPPL7 always and Arc/Info in case
+of polygon with complex shape put label point too close to polygon boundary.
+<P>
+While it can be bearable if sole purpose of this label point is to identify
+polygon in vector topology map, it is not good for plotting charts other
+possible applications of label points.
+<P>
+So following algorithm is proposed:
+<OL>
+<LI> Generate unique numbers for polygons (EPU <B>cluster</b> command
+ already can do this)
+<LI> Calculate distance of each raster cell to nearest polygon boundary
+ (combination of EPPL7 <B>border</B>(epp) and <B>radius</B> commands
+ can do this and
+ EPU <B>thiessen</B> command eventually would)
+
+<LI> Find out maximal distance from boundaries for each polygon
+ (<B>outtable</B> command)
+<LI> Retrieve coordinates of any point with given distance and polygon
+ ID and use it as label point. (can be done with EPPL7
+ <B>intable</B> and <B>evaluate</B> and is trivial thing if coded
+ in C.
+</OL>
+
+Analysis of this algorithm shows that it can be performed using at most
+two passes over raster, given that all intermediate structures are kept
+in memory.
+<P>
+<I>First pass</I> perform cluster and radius operations in parallel.
+Write three intermediate rasters, two of which contain low and high half-words of uniquie polygon numbers and third - distance to boundaries. During
+this pass table of maximal distance for each polygon should be accumulated.
+<P>
+<I>Second pass</I> Find a point for each entry of polygon-distance table and
+write its coordinates along with polygon ID.
+<P>
+
+<A NAME="toc_section1"></A><A HREF="#toc_entry1"><H3>Generation of vector topology from raster</H3></A>
+
+Vector topology as used by arc/info consist of following parts
+<OL>
+ <LI> No arc in coverage should intersect each other
+ <LI> Each polygon should have exactly one label
+ <LI> Each arc should have atributes denoting left and right polygons.
+ <LI> Each point where arcs are joined (node) should have a record
+ which lists IDs of arcs joined in it.
+</OL>
+If we are building polygon coverage from file, generated via EPPL7 or EPU
+<B>border</B> commands, constraints 1 and 2 are ensured by border algorithm.
+If we are using algorithm described above, for label points, we have
+enough information to assign left and right polygon IDs for any polyline
+(arc), provided that polylines are generated on second pass of above algorithm.
+<P>
+So, only thing we need is to create list of nodes. It is also much simplier
+to do during raster scan, than processing vector file, becouse while we are
+passing location of node, we have all lines joined here at hand, while in
+the vector file they can be very far from each other, becouse lines which
+<I>starts</I> at this node would be written to the file only when they would
+<I>end</I>.
+<P>
+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
+and requiring user to do time-consuming CLEAN or BUILD operation, is closeness of ARC/Info export format.
+<A NAME="toc_section2"></A><A HREF="#toc_entry2"><H3>Rasterizing polygon coverages</H3></A>
+
+EPPL7 <B>rasterize</B> command operates on non-topological vector files.
+Therefore it have to do three passes over file and often leave small
+holes which have to be eliminated using <b>fill</B> command. But it works
+very fast and have (especially in incarnation of EPU <B>cluster</B> command)
+almost no limitation concerning raster size and polygon complexity.
+<P>
+ARC/Info <B>polygrid</B> command produces raster without holes, but it works
+very slowly (it seems that it scans entire vector file for each point of
+generated raster. In PC Arc/Info 3.5 it also have some very restrictive size
+limitation (5000x5000) and doesn't understand EPPL format correctly (doesn't
+write coordinate information into header, doesn't support 16-bit rasters).
+<P>
+But combining of these two algorithms can produce rasterization algorithm
+which would be even faster than EPPL7 rasterize and work without holes.
+<P>
+Idea is that while drawing lines from vector file in the raster (as EPPL
+does on the first pass) we plot each line two-cell wide, giving left cell
+value of left polygon and right cell value of right polygon. The only thing
+left is to fill remaining parts of file by color of nearest non-offsite
+point, which is guarantied to be same for all surrounding lines, due to
+ARC/Info topology.
+<P>
+This algorithm can be implemented without knowledge of ARC/Info propieritary
+formats, becouse lines from coverage along with their unique IDs can
+be legitimately exported into open GEN format, and arc attribute table,
+which contains IDs of right and left polygons can be exported into RDBMS,
+as well as polygon attribute table which contain information we really
+want to plot.
+
+
+</BODY>
+</HTML>
+
+
+
+
projects / sites / home_page.git / blobdiff