MS RFC 5: MapServer Horizon Reprojection Improvements

[Frank Warmerdam]

Folks, 

Yet another promised RFC.  Really just a bug fix, but substantial 
enough that I thought an RFC discussion might be appropriate. 

Best regards,

-- 
---------------------------------------+--------------------------------------
I set the clouds in motion - turn up   | Frank Warmerdam, warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | Geospatial Programmer for Rent



=====================================================
MS RFC 5: MapServer Horizon Reprojection Improvements
=====================================================

:Date:  2005/09/16
:Author: Frank Warmerdam
:Contact: warmerdam at pobox.com
:Last Edited: $Date: 2005/09/16 17:07:27 $
:Status: proposed


Purpose
-------

To provide a practical solution to MapServer Bug 411 - Clipping Issue
with Ortho Projection:

  http://mapserver.gis.umn.edu/bugs/show_bug.cgi?id=411


Approach
--------

The msProjectShape() function would be altered support reprojection
of shapes where some, but not all, vertices fail to transform due to issues
such as falling over the horizon.  An iterative method would be used to 
preserve a reduced geometry approximating the portion that can be transformed.


Point Features
--------------

 o Point features will be handled as they are now.  The either transform
   successfully or not.  Those that fail to transform are dropped. 


Line Features
-------------

 o Line strings would potentially be split into multiple line strings, if
   there were more than one discontiguous portion of a line string that 
   transforms. 

 o Interpolated (horizon) points would be computed by transforming points
   along the line segment between the last successful point and the first 
   unsuccessful point.  A binary search algorithm will be used to find the
   closest point within our tolerance distance. 

 o Line strings where no vertices transform successfully will still be dropped.


Area Features
-------------

 o Each ring will be treated distinctly, without regard to the other rings. 
   This means no there is no assurance that an inner ring will remain 
   completely within the outer ring after clipping.  In particular, where
   the horizon passes through an area and a hole in the area, it is likely 
   that the hole edge will touch over even overlap the outer area edge a bit.
   Genreally this should not matter much in the MapServer context since a
   simple scanline rasterization (winding number based) technique is used. 
   So polygon "correctness" is not paramount.  

 o A similar technique to that for lines is used to interpolate the edge
   vertices when clipping is to be applied. 

 o For polygons there will be two (or possibly 4, 6, 8...) interpolated
   horizon points.  These will be connected with a straight line segment. 
   For very large polygons spanning a significant portion of the horizon
   (ie. dozens of degrees of arc of the horizon) this will result in part of
   the circle of the horizon getting clipped off.  Optionally an iterative 
   method could be applied to address this curvature issue (not priced into
   this proposal). 


Tolerances
----------

MapServer will need make a decision on how detailed to get when doing the
iterative horizon determination.   The tolerance will be fixed as half the
size of a pixel in the current map rendering.   In normal map drawing this
should mean that the final rendering is effectively exact. 

However, communicating the tolerance into msProjectShape() will require
substantial work as the msProjectShape() function does not normally know
anything about the map or current rendering information.  To communicate 
this information to msProjectShape(), I will add a transformation options
structure with this information (and possibly other flags controlling 
transformation) which will be passed into msProjectShape().  If NULL 
particular defaults will be used.  

All appropriate uses of msProjectShape() will need to be updated to reflect
this change, and to setup the transformation options information ahead of
time.  layerObj level PROCESSING options will also be provided to control
(override) the default transformation options. 


Caveats
-------

1) msProjectShape() may produce slightly invalid polygons from a GIS
   point of view, though it shouldn't matter much for rendering purposes. 

2) The straight line segment for "area horizon edges" will result in visible
   "clipping" of the horizon for very large polygons (ie. the Soviet Union).

3) This change is too disruptive to back port to the stable 4.6.x release,
   so it would only be available as part of CVS based MapServer builds
   (aka 4.7) until such time as the 4.8 release is made, likely in December
   or January.


Mapfile Implications
--------------------

There will be no changes to the mapfile.


MapScript Implications
----------------------

There will be no changes to mapscript. 


Backward Compatibility Issues
-----------------------------

Some maps that previous dropped incompletely reprojected features will now
produce clipped features.  I don't forsee this causing obvious problems
other than a slight change (improvement!) in appearance. 


Staffing and Timeline
---------------------

The new feature will be implemented by October 15th in time for inclusion
in MapServer 4.8.   It will be implemented by Frank Warmerdam with generous
funding from TMC Technologies.