22

Two days ago I asked a question about the internal storing order for the vertices of a polygon in ESRI shapefiles. That question was answered (Are polygons stored clockwise or counterclockwise in a shapefile?) and it was also answered in an old post (Polygon creation (Clockwise rotation or not))

But now my question is more general, and I don't know if it has an unique answer. Is the clockwise order only for ESRI shapefiles or for general GIS formats? And what about the internal representation for a GIS software? For example, if I use QGIS and I read a *.shp containing polygons I suppose the internal representation of the outer bound is clockwise as in the original shapefile, but what about for all the file formats supported by QGIS? And for ArcGIS? And in the case there exists a file format with polygons stored in counterclockwise, if these files are loaded in QGIS, ArcGIS, etc., is the orientation changed internally, so if I read the data using PyQGIS, for example, the polygons are clockwise ordered?

My purpose is to write a plugin for QGIS, but the source of data can be ESRI shapefiles or other formats. As I need to check the angles between consecutive sides of polygons using their azimuths I need to known if the order is clockwise. One solution is computing the area of each polygon and, if I remember correctly, if it is positive the order is clockwise and if negative the order is counterclockwise.

Area computation is not an intensive task, so it will not slow my plugin so much. But in the special case of QGIS, anybody knows if it stores the polygons clockwise or counterclockwise, regardless the order in the original source? By now I'm working with ESRI shapefiles and the coordinates in layer.getFeatures().geometry().asPolygon() are stored in clockwise for the outer border and counterclockwise for the holes, i. e. as in the original *.shp.

26

In the OGC specification, which can be downloaded [here],(http://www.opengeospatial.org/standards/sfs) they state:

"Polygon rotation is not defined by this standard; actual polygon rotation may be in a clockwise or counter-clockwise direction."

In the Oracle docs, it is clearly stated that exterior ring boundaries are oriented counterclockwise, and interior ring boundaries, clockwise. Likewise, in SQL Server Spatial, the geography datatype follows a counter-clockwise rule for the exterior ring, and clockwise for the interior rings -- see this MicroSoft blog for more details. Postgis seems to allow it either way, for geometries, and has functions that will force a polygon's geometry to follow either a right or left hand rule, see ST_ForceRHR and ForceLHR. JTS/Geos seem to have followed the right-hand rule, ie, a clockwise orientation of the outer ring, so it is all a bit unclear, really.

In general it makes sense for a geography datatype to force orientation, as otherwise it would be impossible to tell if a small polygon was just that or the inner ring of a whole world polygon. With a geometry datatype on a planar surface, this confusion cannot arise, as the outer ring and inner ring follow in order, and if there is only a single ring, it will be enclosing (no matter what the orientation), unlike on a globe, which wraps round.


From a comment by @mxfh: OGC's OpenGIS Simple Features Access (ISO 19125-1) specifies a counter-clockwise direction for outer rings as of version 1.2.1 document [OGC 06-103r4] 6.1.11.1/page 26 from opengeospatial.org/standards/sfa. The change got introduced between version 1.1.0 and 1.2.0 in 2006 latest. The footnote you're citing from hasn't been updated since 2005

  • Nice answer John. I'm not sure that using an ordering of nodes to identify interior vs. exterior rings is the only way that a vector data format could achieve that though. I'll agree with you though that some mechanism needs to be in place. With GeoJSON for example, the first list of nodes is designated as the exterior and all subsequent lists are interior holes. That works as (if not more) effectively. – WhiteboxDev Oct 21 '14 at 15:38
  • Yes, this is true of WKT for geometries too. For geographies it clearly matters more. – John Powell Oct 21 '14 at 15:40
  • That's very true ;) – WhiteboxDev Oct 21 '14 at 15:42
  • @WhiteboxDev the reason winding orders of nested rings alternate is, that calculating the area with the Shoelace Method computes signed areas depending on the ring direction. In general nested rings of first order are considered holes and have the alternate direction of the outer ring. Their contributing area value is negative. Where as outer ring is positive; so are nested rings of even order. So the total area of all ring features is the sum of all signed areas. – mxfh Jul 28 '15 at 9:37
  • 1
    @mxfh: strictly speaking, "winding orders of nested rings" is moot for OCG (and many other) Polygons.... as it is not allowed. The way to represent an nested polygon inside the "hole" of another would be to use a MultiPolygon... in which case, each constituent Polygon follows the original winding rules. OK, OK: this is tantamount to alternating the winding of "nested LinearRings"... but just pointing out that it is not the Polygon -- per se -- that allows this, but rather the definition of the MultiPolygon. – Dan H Aug 5 '15 at 23:21
22

Ring (boundary) directions are needed to prevent ambiguities for geographic coordinate systems that cover a finite surface, since the boundary would define two areas, one left and one right of the boundary along it's direction. Determining which of those two areas is the bigger one is possible, but still leaves the ambiguity.

Here is an overview on outer ring directions of polygons in various formats by their specifications:

Illustration of winding order of Shapefiles and Simple Features

  • Simple Feature Access (ISO 19125-1) also used in WKT/GML/KML and various SQL implementations:

    • exterior rings: counter-clockwise
    • interior rings (holes): clockwise direction.

    A Polygon is a planar Surface defined by 1 exterior boundary and 0 or more interior boundaries. Each interior boundary defines a hole in the Polygon. [...]

    The exterior boundary LinearRing defines the “top” of the surface which is the side of the surface from which the exterior boundary appears to traverse the boundary in a counter clockwise direction. The interior LinearRings will have the opposite orientation, and appear as clockwise when viewed from the “top”... Simple Feature Access specs

    In most implementations the order of rings in a POLYGON is important (as opposed to shapefiles)

    For a polygon with holes, its first subelement is its exterior ring, its second subelement is its first interior ring, its third subelement is its second interior ring, and so on. Oracle Spatial

    Deeper nestings, aka island-in-a-lake-on-an-island-... have to be represented as MultiPolygons (see figure 2.10 (4)), since there can be only one exterior border and deeper nestings than interior rings are not defined.

  • ESRI Shapefiles/ SHP:

    • exterior rings: clockwise
    • interior rings: counter-clockwise

    A polygon consists of one or more rings. A ring is a connected sequence of four or more points that form a closed, non-self-intersecting loop. A polygon may contain multiple outer rings. The order of vertices or orientation for a ring indicates which side of the ring is the interior of the polygon. The neighborhood to the right of an observer walking along the ring in vertex order is the neighborhood inside the polygon. Vertices of rings defining holes in polygons are in a counterclockwise direction. Vertices for a single, ringed polygon are, therefore, always in clockwise order. [...]

    The order of rings in the points array is not significant. ESRI Whitepaper

    Since multiple outer boundaries are allowed island-in-a-lake-on-an-island configurations are possible with this polygon definition. Topologically the island in a lake would be just another clockwise outer ring. Effectively this makes an ESRI Shapefile Polygon a Simple Feature MultiPolygon

    If you don’t order the points correctly you’ll just have overlapping polygons. pyshp

  • GeoJSON (RFC7946):

    NOTE: Original GeoJSON 2008 spec had no winding order enforced

    • winding order: exterior ring is counter-clockwise (right hand rule)
    • interior rings are clockwise
    • order of rings is important:

      For Polygons with multiple rings, the first must be the exterior ring and any others must be interior rings or holes. GeoJSON spec

  • TopoJSON: forces exterior rings clockwise by default

Illustration of winding order of Shapefiles and Simple Features

Excursion:

The mathematical reasoning on why winding orders of nested rings alternate is, that calculating the area with the shoelace formula (visual explanation) computes signed areas depending on the ring direction.

In general nested rings (interior boundaries) are considered holes and have the alternate direction of the outer ring. Their contributing signed area value is negative. Where as outer rings are positive. The total area of all ring features is the sum of all signed areas.

As implemented by ESRI see this Knowledge Base entry: What algorithm is used by ArcGIS to determine a polygon's area?

Proposed Mnemonic

Open ends of letterforms interpreted as arrows:

  • Shapefile: S → ᔑ → ↻
  • Simple Features: e → ᘓ (winding outwards cc-wise) → ↺
  • GeoJSON: G (stem of G is arrow) → ↺
4

I don't know that anybody will be able to provide a definitive answer for your question since each vector file format is different and each GIS, in terms of how they internally handle these data, will also be different. But I can tell you for certain that the clockwise ordering is not only for ESRI Shapefiles. There are other formats that use a similar designation of clockwise ordering for external rings and counter-clockwise for interior hole polygons. For example, the JTS vector polygon structure uses a similar format. In fact, it is stated here, that historically this was to be similar to the ESRI approach. I can also definitively say that no, not all formats have this requirement. For example, the GeoJSON format specifications make no such requirement about the ordering of vertices in their polygon format. The KML specification actually state:

The for polygons must be specified in counterclockwise order. Polygons follow the "right-hand rule," which states that if you place the fingers of your right hand in the direction in which the coordinates are specified, your thumb points in the general direction of the geometric normal for the polygon.

So the full range of options exist and are implemented out there. It's a wild world!

  • 1
    Note that KML's "right-hand rule" is what has been conventionally been called "left hand rule" (when you walk the perimeter with your arms outstretched, your left hand will inside the figure). Esri has multiple approaches, since shapefiles are the only format that uses right hand rule (enterprise geodatabases use left hand rule internally, but the 'C' API will let you request in either order). GML only requires that interior rings be in opposite order of exterior rings, and that the first ring be exterior. – Vince Oct 21 '14 at 16:41
  • @Vince I didn't know that. Isn't that nuts? Thanks for letting me know. I think I like GML's approach best of all; doesn't matter the ordering as long as they are opposite. That makes a lot of sense. – WhiteboxDev Oct 21 '14 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.