Creating topology from raster and vice versa

1. Generation of polygon labels
2. Generation of vector topology from raster
3. Rasterizing polygon coverages

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.

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.

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.

So following algorithm is proposed:

1. Generate unique numbers for polygons (EPU cluster command already can do this)
2. Calculate distance of each raster cell to nearest polygon boundary (combination of EPPL7 border(epp) and radius commands can do this and EPU thiessen command eventually would)
3. Find out maximal distance from boundaries for each polygon (outtable command)
4. Retrieve coordinates of any point with given distance and polygon ID and use it as label point. (can be done with EPPL7 intable and evaluate and is trivial thing if coded in C.

First pass 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.

Second pass Find a point for each entry of polygon-distance table and write its coordinates along with polygon ID.

Generation of vector topology from raster

1. No arc in coverage should intersect each other
2. Each polygon should have exactly one label
3. Each arc should have atributes denoting left and right polygons.
4. Each point where arcs are joined (node) should have a record which lists IDs of arcs joined in it.

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 starts at this node would be written to the file only when they would end.

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.

Rasterizing polygon coverages

ARC/Info polygrid 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).

But combining of these two algorithms can produce rasterization algorithm which would be even faster than EPPL7 rasterize and work without holes.

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.

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.