| Version 22 (modified by , 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 |
| 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, 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 );
}
