wiki:FDORfc48

Version 22 (modified by leaf, 14 years ago) ( diff )

--

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
AuthorOrest Halustchak, Dan Stoica, Gavin Cramer, Leaf Li
RFC StatusAdopted
Implementation StatusPending
Proposed Milestone3.5.0.0
Assigned PSC guide(s)Orest Halustchak
Voting HistoryJuly 15, 2010
+1Orest Halustchak, Greg Boone, Haris Kurtagic
+0Jason 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, July 30, 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 answer for this question depends on users' preference. The following enums and methods will be introduced to address it.

/// \brief
/// FdoFixPolygonVertexOrderAction is an enumeration of the action taken 
/// when fixing polygon vertex order.
///
enum FdoFixPolygonVertexOrderAction
{
    /// No processing.
    FdoFixPolygonVertexOrderAction_None = 0,

    /// Reverse polygon vertex.
    FdoFixPolygonVertexOrderAction_Reverse = 1,

    /// Check polygon vertex order and fix it if necessary.
    FdoFixPolygonVertexOrderAction_CheckAndFix = 2
};

/// \brief
/// FdoFixPolygonVertexOrderPreference represents the preference
/// when fixing polygon vertex order.
///
enum FdoFixPolygonVertexOrderPreference
{
    /// Prefer high performance. It guarantees that polygons in the target have 
    /// the correct vertex order if the target is enforced.
    FdoFixPolygonVertexOrderPreference_HighPerformance = 0,

    /// Prefer correctness. It guarantees that polygons in the target have 
    /// the correct vertex order if the vertex order rule of the target isn't none.
    FdoFixPolygonVertexOrderPreference_Correctness = 1
};


/// \brief
/// Spatial utility class
///
class FdoSpatialUtility
{
public:
    /// \brief
    /// Given the vertex order and strictness rule of the source and the target,
    /// get what action should be taken to fix polygon.
    ///
    /// \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.
    /// \param preference
    /// Input the preference when fixing polygon vertex order.
    /// 
    /// \return
    /// Returns the action taken to fixing polygon vertex order.
    /// 
    FDO_SPATIAL_API static FdoBulkCopyFixPolygonVertexOrderAction GetFixPolygonVertexOrderAction(
        FdoPolygonVertexOrderRule sourceVertexOrderRule,
        FdoBoolean sourceStrictnessRule,
        FdoPolygonVertexOrderRule targetVertexOrderRule,
        FdoBoolean targetStrictnessRule,
        FdoFixPolygonVertexOrderPreference preference);
};

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

static FdoBulkCopyFixPolygonVertexOrderAction table1[36] = {
                                                    // From Order    From Strict    To Order    To Strict     NonSense
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CCW         Enforced
    FdoFixPolygonVertexOrderAction_None,            // CCW           Enforced       CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CW          Enforced
    FdoFixPolygonVertexOrderAction_Reverse,         // CCW           Enforced       CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CCW           Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CCW           Enforced       None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CCW         Enforce
    FdoFixPolygonVertexOrderAction_None,            // CCW           Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_Reverse,         // CCW           Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CCW         Enforced
    FdoFixPolygonVertexOrderAction_Reverse,         // CW            Enforced       CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CW          Enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Enforced       CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CW            Enforced       None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Not enforced   CCW         Enforced
    FdoFixPolygonVertexOrderAction_Reverse,         // CW            Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CW            Not enforced   None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CCW         Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       CCW         Not enforced  True
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CW          Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       CW          Not enforced  True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       None        Not enforced  True

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CCW         Enforced
    FdoFixPolygonVertexOrderAction_None,            // None          Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_None,            // None          Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // None          Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None             // None          Not enforced   None        Not enforced
};

static FdoBulkCopyFixPolygonVertexOrderAction table2[36] = {
                                                    // From Order    From Strict    To Order    To Strict     NonSense
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CCW         Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CW          Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Enforced       CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CCW           Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CCW           Enforced       None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CCW         Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CCW           Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CCW           Not enforced   None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CCW         Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CW          Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Enforced       CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CW            Enforced       None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Not enforced   CCW         Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // CW            Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,    // CW            Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // CW            Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // CW            Not enforced   None        Not enforced

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CCW         Enforced      True
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CCW         Not enforced  True
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CW          Enforced      True
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Enforced       CW          Not enforced  True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       None        Enforced      True
    FdoFixPolygonVertexOrderAction_None,            // None          Enforced       None        Not enforced  True

    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CCW         Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CCW         Not enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CW          Enforced
    FdoFixPolygonVertexOrderAction_CheckAndFix,     // None          Not enforced   CW          Not enforced
    FdoFixPolygonVertexOrderAction_None,            // None          Not enforced   None        Enforced      True
    FdoFixPolygonVertexOrderAction_None             // None          Not enforced   None        Not enforced
};

If users perfer performance to correctness, method GetFixPolygonVertexOrderAction will use table1. It guarantees that polygons in the target will have the correct vertex order if the target is enforced. If users perfer correctness to performance, method GetFixPolygonVertexOrderAction will use table2. It guarantees that polygons in the target will have the correct vertex order if the vertex order rule of the target isn't none.

Considering performance, an additional parameter 'FdoBoolean checkInteriorRings' will be added for method FdoSpatialUtility::ReversePolygonVertexOrder(...). If users know the input polygon is a valid polygon, they can pass false for parameter checkInteriorRings to reverse its vertex order. Otherwise, pass true. Method !FdoSpatialUtility::ReversePolygonVertexOrder(...) will check whether interior rings have the different vertex order with exterior ring and guarantee the returned polygon is a valid polygon after reversing the vertex order of the input polygon.

class FdoSpatialUtility
{
public:
    /// \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.
    /// \param checkInteriorRings
    /// true  - Check whether interior rings have the different vertex order with
    ///         exterior ring and guarantee the returned polygon is a valid polygon
    ///         after reversing the vertex order of the input polygon.
    /// false - Reverse the vertex order of interior rings and exterior ring directly
    ///         no matter interior rings have the different vertex order with exterior ring.
    ///
    /// \return
    /// Returns the modified polygon. 
    ///
    FDO_SPATIAL_API static FdoIGeometry* ReversePolygonVertexOrder (
                              FdoIGeometry * geometry,
                              FdoBoolean checkInteriorRings = false );
}
Note: See TracWiki for help on using the wiki.