Counter-clockwise polygons and dateline-crossing bounding boxen

[sgillies]

@frewsxcv 2 draft-geojson PRs have possible consequences for python-geojson: geojson/draft-geojson#42, geojson/draft-geojson#42. The first recommends counter-clockwise winding for exterior rings of polygons (aka right-hand rule) and the second makes a recommendation that bounding boxes be [west, south, east, north] instead of [min(long), min(lat), max(long), max(lat)] to make dealing with the dateline more sane. Any thoughts or comments?

A function to wind/rewind polygons accordingly could be a good feature for python-geojson.

[frewsxcv]

Sounds great. I'm a bit busy these couple weeks, but I'll get to it when I get the chance. If anyone else reads this and wants to do it earlier, I'll gladly accept pull requests :)

[Guts]

I'm pretty interested in that feature.

I read that's possible with utils.map_coords. Is that right? Maybe I can help but I don't know how...

[ChrisBarker-NOAA]

I just came here looking for just this feature. It would be good for the .valid attribute to check for ccw.

And (maybe optionally) it could be fixed when creating the Feature

Here is some code for checking winding order:

https://gist.github.com/ChrisBarker-NOAA/6fc7de7557856c1351a27df2bb281df5

maybe I'll do a PR one of these days -- but how/where would you like it done?

Automatically?

Checking in .valid?

Only when asked? (i.e. a fix_winding() method)

[ChrisBarker-NOAA]

NOTE: I was using my python code in the gist just now, and for one case of a lot of large polygons -- it's pretty darn slow:

writing the geojson went from 624 ms to 2.4 s if I added the is_clockwise() check.

So probably better not to have it done automatically.

[rayrrr]

Hi @ChrisBarker-NOAA, new project lead here. Thanks for your input on this! It guided me in a good direction, and it turns out a more efficient algorithm is available.

It's all explained in the Curve Orientation article on Wikipedia, in the "practical considerations" section.

TL;DR: Regardless of a given linear ring's cardinality, only 3 (well-chosen) points are needed to determine its winding order: a point on the convex hull and its two immediate neighbors. Also, a point with the minimum longitude/latitude in the set is guaranteed to be on the convex hull, so these 3 points are trivial to choose.

In other words, the simpler formula in your "convex" function can actually work in all cases, just by choosing the correct three vertices to use from any well-formed polygon.

For now, here is a function implementing the above which I plan to add to the codebase soon, for you to try out. Note, the input parameter is a "linear ring" in GeoJSON parlance so that's what I'm calling it.

def is_clockwise(lring):
    """
    Determine winding order based on minimum lng/lat
    coordinate and its immediate neighbors.
    :param lring: a linear ring from a Polygon
    :type lring: _linear_ring
    :return: whether the linear ring has clockwise winding order
    :rtype: boolean
    """
    lring.pop()  # remove last-same-as-first coord pair
    x = lring.index(min(lring[:-1]))  # index of min coords (on convex hull)
    det = ((lring[x][0] - lring[x-1][0]) * (lring[x+1][1] - lring[x-1][1]) 
        - (lring[x+1][0] - lring[x-1][0]) * (lring[x][1] - lring[x-1][1]))
    return det < 0

I got about a 25% performance boost with this function on a trivial example compared to your gist; please let us know how it works on one of your larger use cases if you can.

[Tafkas]

Any updates on this?