FDO RFC 48 - Polygon Vertex Order

This page contains an change request (RFC) for the FDO Open Source project. More FDO RFCs can be found on the RFCs page.

Status

RFC Template Version	(1.0)
Submission Date	May. 06, 2010
Last Modified	Leaf Li - 07/06/10:10:13
Author	Orest Halustchak, Dan Stoica, Gavin Cramer, Leaf Li
RFC Status	Adopted
Implementation Status	Pending
Proposed Milestone	3.5.0.0
Assigned PSC guide(s)	Orest Halustchak
Voting History	July 15, 2010
+1	Orest Halustchak, Greg Boone, Haris Kurtagic
+0	Jason Birch, Traian Stanev, Jackie Ng
-0
-1

Motivation

Currently there are some inconsistencies and missing capability in dealing with the vertex order of polygon loops for different FDO Providers. Some of data sources use clockwise vertex order rule. Some of data sources use counterclockwise vertex order rule. For example, SHP file follows clockwise vertex order rule and Oracle follows counterclockwise rule.

When inserting or updating a geometry, the current strategy of FDO Provider is focused on the user being responsible for the geometry and not having the providers fix it. FDO Providers may even throw exceptions rather than automatically try to fix a user’s geometry. So FDO should provide a way for users to get the vertex order rule and the vertex order strictness rule so that users can insert or modify polygon correctly.

This purpose of this RFC is to resolve polygon vertex order issue. It outlines changes that are required in the FDO API.

Overview

Currently there are two inconsistencies in dealing with polygon vertex order. The first inconsistency is the vertex order rule in a polygon loop.

• For most systems where there is a specific rule for the order of vertices in a polygon boundary, the rule is that exterior loops follow a counterclockwise order whereas inner loops follow a clockwise order. This is the rule that OGC has defined and applies to 2D polygons.
• The exception to this rule is the SHP file format specification. SHP follows a clockwise rule; however the SHP format was defined before OGC existed.

The second inconsistency is the vertex order strictness when inserting or updating a polygon.

• SQL Server 2008 Spatial has two data types that support geometry. They are Geometry and Geography. Both of these support polygons but the Geography type has a constraint that the vertex order around loops must be counterclockwise for outer loops and clockwise for inner loops. Polygons that fail this test will be rejected. The FDO SQL Server Spatial provider does not attempt to fix these polygons.
• Oracle also uses the counterclockwise loop order rule, but is not as stringent about enforcing it. It will allow polygons to be inserted with either order. Area calculations will always be positive. A validity function however will indicate which are valid and which are invalid.
• SHP follows a clockwise polygon loop vertex order in contrast to the other formats. While applications that process SHP files may be fairly lax in requiring that polygons follow a clockwise vertex order. !ESRI ArcView can render polygons with counterclockwise loops correctly and display negative areas for them. OSGEO FDO SHP provider does not change the vertex order of polygons. However, the FME SHP provider does correct the vertex order of polygons.

We are not going to change the current strategy of FDO Provider to fix polygon vertex order error automatically by FDO Provider because users may want to save their modification to geometry temporarily before they fix all of geometry errors. Moreover, it may result in performance issue. So what FDO Provider should provide is the following two functionalities.

• Provides a way for users to get the vertex order rule and the vertex order strictness rule.
• Provides utility methods to help users fix polygon vertex order issues. Users can call these methods to fix polygon vertex order error anytime according to the polygon vertex strictness of a geometry.

Proposed Solution

Add the two capability functions in class FdoClassCapabilities to get the polygon vertex rule and the vertex order strictness of the geometry in a feature class. These will apply to 2D polygons. For 3D polygons, e.g. ones that are completely vertical, these could be in either direction depending on which way is "up".

SQL Server 2008 adds a complication. SQL Server 2008 handles spatial data with two separate data types, geography for geodetic data and geometry for others. The geography type has the strict enforcement of the CCW order. The geometry type has the same rule, but does not have strict enforcement. We could have the capabilities tied to a particular geometry property, which would make the capability handling more complex for providers and for applications. Alternatively we can just make these schema level capabilities and have SQL Server advertise a general strict enforcement of the vertex order rule. Unfortunately, this messes up the capability-based copying of polygons from one provider to another when the source is SQL Server. Existing geometry data may not follow the rules if it uses the SQL Server geometry type. Another alternative is to have the capability function take a coordinate system definition as a parameter. But, that adds complexity as well, and requires providers to analyze the coordinate system definition. So, we’ll stick to defining the capability function for this against the geometry property.

/// \brief
/// The FdoPolygonVertexOrderRule enumeration defines the vertex order rule in a 
/// polygon loop. FdoPolygonOrderVertexRule values are typically counterclockwise, 
/// clockwise and none. None value means the vertex order rule is unknown, 
/// undefined or not care.
///
enum FdoPolygonVertexOrderRule {
	FdoPolygonVertexOrderRule_CCW,
	FdoPolygonVertexOrderRule_CW,
	FdoPolygonVertexOrderRule_None
};

/// \brief
/// The FdoClassCapabilities class describes various capabilities
/// for a particular FDO class definition and an FDO Provider datastore.
///
class FdoClassCapabilities  
{
    ......
    /// \brief
    /// Gets the vertex order rule of the specified geometry property.
    ///
    /// \param geometryPropName
    /// Input the geometry property name
    /// \return
    /// Returns the vertex order rule that the specified geometry property follows.
    ///
    FDO_API FdoPolygonVertexOrderRule GetPolygonVertexOrderRule( 
                     FdoString* geometryPropName );
    /// \brief
    /// Sets the vertex order rule of the specified geometry property.
    ///
    /// \param geometryPropName
    /// Input the geometry property name to set vertex order rule
    /// \param vertexOrderRule
    /// Input vertex order rule that the specified geometry follows.
    ///
    FDO_API void SetPolygonVertexOrderRule  ( 
                     FdoString* geometryPropName,
                     FdoPolygonVertexOrderRule vertexOrderRule );
    /// \brief
    /// Gets the vertex order strictness of the specified geometry property.
    /// \param geometryPropName
    /// Input the geometry property name
    /// \return
    /// Returns true if the vertex order of the specified geometry property is enforced. 
    /// Returns false if it is loose.
    ///
    FDO_API FdoBoolean GetPolygonVertexOrderStrictness  ( 
                     FdoString* geometryPropName );
    /// \brief
    /// Sets the vertex order strictness of the specified geometry property.
    /// \param geometryPropName
    /// Input the geometry property name
    /// \param value
    /// Input true if the vertex order of the specified geometry property is enforced. 
    /// Input false if it is loose. 
    ///  
    FDO_API void SetPolygonVertexOrderStrictness ( 
                     FdoString* geometryPropName
                     FdoBoolean value );
    ......
};

Add the following three functions in class FdoSpatialUtility to fix the polygon vertex order error. The first function is used to check the polygon vertex order and fix it as needed. The second function is used to reverse polygon vertex order directly. When the polygon vertex order is known, the second function can be used because it is more efficient.

/// \brief
/// Spatial utility class
///
class FdoSpatialUtility
{
    ......
    /// \brief
    /// Check whether the vertex order of the input polygon follows the specified
    /// vertex order rule. If not, fix it.
    ///
    /// \param geometry
    /// Input the polygon geometry to be fixed. It can be a polygon, multipolygon,
    /// curvepolygon, or multicurvepolygon.
    /// \return
    /// Returns the modified polygon.  
    ///
    FDO_SPATIAL_API static FdoIGeometry* FixPolygonVertexOrder (
                              FdoIGeometry * geometry, 
                              FdoPolygonVertexOrderRule vertexOrderRule );

    /// \brief
    /// Reverse the vertex order of the input polygon.
    ///
    /// \param geometry
    /// Input the polygon geometry to be reversed. It can be a polygon, multipolygon,
    /// curvepolygon, or multicurvepolygon.
    /// \return
    /// Returns the modified polygon. 
    ///
    FDO_SPATIAL_API static FdoIGeometry* ReversePolygonVertexOrder (
                              FdoIGeometry * geometry );

    /// \brief
    /// Get the vertex order of the input polygon.
    ///
    /// \param geometry
    /// Input geometry to be checked. It can be a polygon, multipolygon,
    /// curvepolygon, or multicurvepolygon.
    /// \return
    /// Returns the vertex order of the input polygon.
    /// 
    FDO_SPATIAL_API static FdoPolygonVertexOrderRule CheckPolygonVertexOrder(FdoIGeometry* geometry);
    ......
};

Managed FDO API

The FDO Managed Interfaces will be updated in a similar manner to reflect the proposed changes.

Provider Implementation

All FDO providers will be updated to return the correct polygon vertex order rule value and polygon vertex strictness value. For King FDO providers, we will try to find some volunteers from the community to update them.

Test Plan

Existing FDO core unit tests will be expanded to test the proposed enhancements defined above. Provider specific unit tests will be added to test the proposed enhancements defined above.

Funding/Resources

Autodesk to provide resources / funding.

Addendum, Aug. 9, 2010

This RFC provides some utility methods to check polygon vertex order and fix polygon vertex order errors. However, what action should be taken when copying a polygon from one feature source to another feature source isn't addressed in this RFC. The following enum and method will be introduced to address it.

/// \brief
/// FdoFixPolygonVertexOrderAction is an enumeration of the action taken 
/// when copying polygon from a source provider to a target provider.
///
enum FdoPolygonVertexOrderAction
{
    /// No processing.
    FdoPolygonVertexOrderAction_None = 0,

    /// Reverse polygon vertex.
    FdoPolygonVertexOrderAction_Reverse = 1,

    /// Check polygon vertex order and reverse it if necessary.
    FdoPolygonVertexOrderAction_CheckAndReverse = 2
};


/// \brief
/// Spatial utility class
///
class FdoSpatialUtility
{
public:
    /// \brief
    /// Given the vertex order and strictness rule of the source and the target,
    /// get the action taken when copying polygon from a source provider to 
    /// a target provider.
    ///
    /// \param sourceVertexOrderRule
    /// Input the vertex order rule of the source.
    /// \param sourceStrictnessRule
    /// Input the vertex order strictness rule of the source.
    /// \param targetVertexOrderRule
    /// Input the vertex order rule of the target.
    /// \param targetStrictnessRule
    /// Input the vertex order strictness rule of the target.
    /// 
    /// \return
    /// Returns the action taken when copying polygon from a source provider 
    /// to a target provider.
    /// 
    FDO_SPATIAL_API static FdoPolygonVertexOrderAction GetPolygonVertexOrderAction(
        FdoPolygonVertexOrderRule sourceVertexOrderRule,
        FdoBoolean sourceStrictnessRule,
        FdoPolygonVertexOrderRule targetVertexOrderRule,
        FdoBoolean targetStrictnessRule);
};

Method GetPolygonVertexOrderAction is used to get what action should be taken when copying a polygon from one feature source to another feature source. The following table is defined in this method.

static FdoPolygonVertexOrderAction table[36] = {
                                                 // From Order    From Strict    To Order    To Strict     NonSense
    FdoPolygonVertexOrderAction_CheckAndReverse, // CCW           Enforced       CCW         Enforced
    FdoPolygonVertexOrderAction_None,            // CCW           Enforced       CCW         Not enforced
    FdoPolygonVertexOrderAction_CheckAndReverse, // CCW           Enforced       CW          Enforced
    FdoPolygonVertexOrderAction_Reverse,         // CCW           Enforced       CW          Not enforced
    FdoPolygonVertexOrderAction_None,            // CCW           Enforced       None        Enforced      True
    FdoPolygonVertexOrderAction_None,            // CCW           Enforced       None        Not enforced

    FdoPolygonVertexOrderAction_CheckAndReverse, // CCW           Not enforced   CCW         Enforce
    FdoPolygonVertexOrderAction_None,            // CCW           Not enforced   CCW         Not enforced
    FdoPolygonVertexOrderAction_CheckAndReverse, // CCW           Not enforced   CW          Enforced
    FdoPolygonVertexOrderAction_Reverse,         // CCW           Not enforced   CW          Not enforced
    FdoPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Enforced      True
    FdoPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Not enforced

    FdoPolygonVertexOrderAction_CheckAndReverse, // CW            Enforced       CCW         Enforced
    FdoPolygonVertexOrderAction_Reverse,         // CW            Enforced       CCW         Not enforced
    FdoPolygonVertexOrderAction_CheckAndReverse, // CW            Enforced       CW          Enforced
    FdoPolygonVertexOrderAction_None,            // CW            Enforced       CW          Not enforced
    FdoPolygonVertexOrderAction_None,            // CW            Enforced       None        Enforced      True
    FdoPolygonVertexOrderAction_None,            // CW            Enforced       None        Not enforced

    FdoPolygonVertexOrderAction_CheckAndReverse, // CW            Not enforced   CCW         Enforced
    FdoPolygonVertexOrderAction_Reverse,         // CW            Not enforced   CCW         Not enforced
    FdoPolygonVertexOrderAction_CheckAndReverse, // CW            Not enforced   CW          Enforced
    FdoPolygonVertexOrderAction_None,            // CW            Not enforced   CW          Not enforced
    FdoPolygonVertexOrderAction_None,            // CW            Not enforced   None        Enforced      True
    FdoPolygonVertexOrderAction_None,            // CW            Not enforced   None        Not enforced

    FdoPolygonVertexOrderAction_CheckAndReverse, // None          Enforced       CCW         Enforced      True
    FdoPolygonVertexOrderAction_None,            // None          Enforced       CCW         Not enforced  True
    FdoPolygonVertexOrderAction_CheckAndReverse, // None          Enforced       CW          Enforced      True
    FdoPolygonVertexOrderAction_None,            // None          Enforced       CW          Not enforced  True
    FdoPolygonVertexOrderAction_None,            // None          Enforced       None        Enforced      True
    FdoPolygonVertexOrderAction_None,            // None          Enforced       None        Not enforced  True

    FdoPolygonVertexOrderAction_CheckAndReverse, // None          Not enforced   CCW         Enforced
    FdoPolygonVertexOrderAction_None,            // None          Not enforced   CCW         Not enforced
    FdoPolygonVertexOrderAction_CheckAndReverse, // None          Not enforced   CW          Enforced
    FdoPolygonVertexOrderAction_None,            // None          Not enforced   CW          Not enforced
    FdoPolygonVertexOrderAction_None,            // None          Not enforced   None        Enforced      True
    FdoPolygonVertexOrderAction_None             // None          Not enforced   None        Not enforced
};

Actions defined in the table above will guarantee that polygons in the target will have the correct vertex order if the target is enforced when copying a polygon from one feature source to another feature source.