RFC - Orientation checking and forcing functions

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

RFC - Orientation checking and forcing functions

Daniel Baston
Hi All,

I put together a pull request a couple of weeks ago that introduces four functions for checking and forcing geometry orientation.  The intent is to provide a less-ambiguous alternative to ST_ForceRHR, and an alternative to ST_Orientation that does not depend on SFCGAL.  Strk asked that I bring this up on the devel list for a review of the semantics.

The four proposed functions are.

ST_ForceCW
ST_ForceCCW
ST_IsCW
ST_IsCCW

The semantics are straightforward, in my opinion:

1.  ST_ForceCW is a synonym for ST_ForceRHR, which gives all exterior rings a clockwise orientation and all interior rings a counterclockwise orientation.  Non-polygonal geometries, including closed LineStrings, are simply passed through.
2.  ST_ForceCCW is simply a shorthand for ST_Reverse(ST_ForceCW)
3.  ST_IsCW returns true if a geometry would not be modified by ST_ForceCW.  It is essentially a synonym for ST_OrderingEquals(geom, ST_ForceCW(geom)).
4.  ST_IsCCW returns true if a geometry would not be modified by ST_ForceCCW.

A few notes:

ST_IsCW and ST_IsCCW both return false if a polygon has invalid ring orientation (i.e., exterior and interior rings are all clockwise)
ST_IsCW and ST_IsCCW both return true for geometries that have no non-empty polygonal components.


Dan

_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Paul Ramsey-3
+1 from me

P.

On Feb 7, 2017, at 4:55 PM, Daniel Baston <[hidden email]> wrote:

Hi All,

I put together a pull request a couple of weeks ago that introduces four functions for checking and forcing geometry orientation.  The intent is to provide a less-ambiguous alternative to ST_ForceRHR, and an alternative to ST_Orientation that does not depend on SFCGAL.  Strk asked that I bring this up on the devel list for a review of the semantics.

The four proposed functions are.

ST_ForceCW
ST_ForceCCW
ST_IsCW
ST_IsCCW

The semantics are straightforward, in my opinion:

1.  ST_ForceCW is a synonym for ST_ForceRHR, which gives all exterior rings a clockwise orientation and all interior rings a counterclockwise orientation.  Non-polygonal geometries, including closed LineStrings, are simply passed through.
2.  ST_ForceCCW is simply a shorthand for ST_Reverse(ST_ForceCW)
3.  ST_IsCW returns true if a geometry would not be modified by ST_ForceCW.  It is essentially a synonym for ST_OrderingEquals(geom, ST_ForceCW(geom)).
4.  ST_IsCCW returns true if a geometry would not be modified by ST_ForceCCW.

A few notes:

ST_IsCW and ST_IsCCW both return false if a polygon has invalid ring orientation (i.e., exterior and interior rings are all clockwise)
ST_IsCW and ST_IsCCW both return true for geometries that have no non-empty polygonal components.


Dan
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel

_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Regina Obe-2

+1

 

From: postgis-devel [mailto:[hidden email]] On Behalf Of Paul Ramsey
Sent: Tuesday, February 07, 2017 9:02 PM
To: PostGIS Development Discussion <[hidden email]>
Subject: Re: [postgis-devel] RFC - Orientation checking and forcing functions

 

+1 from me

P.


On Feb 7, 2017, at 4:55 PM, Daniel Baston <[hidden email]> wrote:

Hi All,

 

I put together a pull request a couple of weeks ago that introduces four functions for checking and forcing geometry orientation.  The intent is to provide a less-ambiguous alternative to ST_ForceRHR, and an alternative to ST_Orientation that does not depend on SFCGAL.  Strk asked that I bring this up on the devel list for a review of the semantics.

 

The four proposed functions are.

 

ST_ForceCW

ST_ForceCCW

ST_IsCW

ST_IsCCW

 

The semantics are straightforward, in my opinion:

 

1.  ST_ForceCW is a synonym for ST_ForceRHR, which gives all exterior rings a clockwise orientation and all interior rings a counterclockwise orientation.  Non-polygonal geometries, including closed LineStrings, are simply passed through.

2.  ST_ForceCCW is simply a shorthand for ST_Reverse(ST_ForceCW)

3.  ST_IsCW returns true if a geometry would not be modified by ST_ForceCW.  It is essentially a synonym for ST_OrderingEquals(geom, ST_ForceCW(geom)).

4.  ST_IsCCW returns true if a geometry would not be modified by ST_ForceCCW.

 

A few notes:

 

ST_IsCW and ST_IsCCW both return false if a polygon has invalid ring orientation (i.e., exterior and interior rings are all clockwise)

ST_IsCW and ST_IsCCW both return true for geometries that have no non-empty polygonal components.

 

 

Dan

_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
In reply to this post by Daniel Baston
On Tue, Feb 07, 2017 at 07:55:27PM -0500, Daniel Baston wrote:

> Non-polygonal geometries, including closed LineStrings, are
> simply passed through.

This is the part I don't like. A closed LineString is really the
only geometry that can be strictly clockwise or clounterclockwise
(while polygons want shells and hole in opposite directions) so
I find it counter-intuitive for ST_IsCW and ST_IsCCW to both return
true for them, and for ST_ForceCW and ST_ForceCCW to return them
untouched.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Daniel Baston
OK, so some alternatives I see are:

1) rename the functions to more clearly indicate that they only consider polygons (ST_ForcePolygonCW, ST_IsPolygonCW ? )
2) modify new functions and ST_ForceRHR to also consider orientation of closed LineStrings 
3) modify new functions to also consider closed LineStrings, without modifying ST_ForceRHR

I don't like the idea of modifying ST_ForceRHR, since it has existed forever, and modifying this would also suggest changes to ST_ForceLHR, whose implementation is contained within SFCGAL.

I'm inclined towards #1.  Do people have any thoughts on these alternatives, or maybe a different solution?

Dan

On Wed, Feb 8, 2017 at 6:26 AM, Sandro Santilli <[hidden email]> wrote:
On Tue, Feb 07, 2017 at 07:55:27PM -0500, Daniel Baston wrote:

> Non-polygonal geometries, including closed LineStrings, are
> simply passed through.

This is the part I don't like. A closed LineString is really the
only geometry that can be strictly clockwise or clounterclockwise
(while polygons want shells and hole in opposite directions) so
I find it counter-intuitive for ST_IsCW and ST_IsCCW to both return
true for them, and for ST_ForceCW and ST_ForceCCW to return them
untouched.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Wed, Feb 08, 2017 at 08:29:56AM -0500, Daniel Baston wrote:
> OK, so some alternatives I see are:
>
> 1) rename the functions to more clearly indicate that they only consider
> polygons (ST_ForcePolygonCW, ST_IsPolygonCW ? )

The fact that Clockwise state is different in shell and holes makes
"right hand rule" less ambiguous to me. As the ambiguity is in the
"rule" term, we could find a name making it clearer that you want
to find the polygon interior on the right while walking on its
edges. ST_ForceAreaRight / ST_ForceAreaLeft ?

> 2) modify new functions and ST_ForceRHR to also consider orientation of
> closed LineStrings

The "right hand rule" is specifically about polygons, so I don't
see a problem there to leave LineStrings untouched.

> 3) modify new functions to also consider closed LineStrings, without
> modifying ST_ForceRHR
>
> I don't like the idea of modifying ST_ForceRHR, since it has existed
> forever, and modifying this would also suggest changes to ST_ForceLHR,
> whose implementation is contained within SFCGAL.

What does ST_ForceLHR do ? Documentation doesn't say.
Is it the reverse of ST_ForceRHR or does it use the other
semantic ?

> I'm inclined towards #1.  Do people have any thoughts on these
> alternatives, or maybe a different solution?

At least for topology, it would be useful to have an ST_IsCW or
ST_IsCCW function accepting a closed linestring in input
(sounds like #3)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Daniel Baston
Sorry, I'm not sure I understand which direction you're asking me to pursue.  Are you asking that I write some new functions ST_IsCW and ST_IsCCW that apply _only_ to LineStrings, and then rename the four functions proposed in the PR to something else?

Dan

On Wed, Feb 8, 2017 at 9:22 AM, Sandro Santilli <[hidden email]> wrote:
On Wed, Feb 08, 2017 at 08:29:56AM -0500, Daniel Baston wrote:
> OK, so some alternatives I see are:
>
> 1) rename the functions to more clearly indicate that they only consider
> polygons (ST_ForcePolygonCW, ST_IsPolygonCW ? )

The fact that Clockwise state is different in shell and holes makes
"right hand rule" less ambiguous to me. As the ambiguity is in the
"rule" term, we could find a name making it clearer that you want
to find the polygon interior on the right while walking on its
edges. ST_ForceAreaRight / ST_ForceAreaLeft ?

> 2) modify new functions and ST_ForceRHR to also consider orientation of
> closed LineStrings

The "right hand rule" is specifically about polygons, so I don't
see a problem there to leave LineStrings untouched.

> 3) modify new functions to also consider closed LineStrings, without
> modifying ST_ForceRHR
>
> I don't like the idea of modifying ST_ForceRHR, since it has existed
> forever, and modifying this would also suggest changes to ST_ForceLHR,
> whose implementation is contained within SFCGAL.

What does ST_ForceLHR do ? Documentation doesn't say.
Is it the reverse of ST_ForceRHR or does it use the other
semantic ?

> I'm inclined towards #1.  Do people have any thoughts on these
> alternatives, or maybe a different solution?

At least for topology, it would be useful to have an ST_IsCW or
ST_IsCCW function accepting a closed linestring in input
(sounds like #3)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Wed, Feb 08, 2017 at 11:35:01AM -0500, Daniel Baston wrote:
> Sorry, I'm not sure I understand which direction you're asking me to
> pursue.  Are you asking that I write some new functions ST_IsCW and
> ST_IsCCW that apply _only_ to LineStrings, and then rename the four
> functions proposed in the PR to something else?

I'd love ST_IsCW, ST_IsCCW, ST_ForceCW and ST_ForceCCW that only apply
to _closed_ LineStrings, raising an error on anything else.

As for polygons, the only missing functionality I see would be an
ST_IsRHR, to be a companion to ST_ForceRHR.

I still hadn't checked what ST_ForceLHR does. Hopefully it's just
the reverse of ST_ForceRHR, in which case we could just make sure
to make it available even when SFCGAL is not in place.

That said, I remember this whole thing started in an attempt to
reduce the confusion with the "Right Hand Rule" concept. As I
agree with you about NOT changing semantic of a very old function,
I don't see how adding more functions help.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Daniel Baston
The idea was that adding functions with different names would be helpful, because "RHR" and "LHR" mean different things to different people (and therefore don't mean much of anything.)

See, for example, the fourth bullet under https://tools.ietf.org/html/rfc7946#section-3.1.6

Dan

On Wed, Feb 8, 2017 at 2:35 PM, Sandro Santilli <[hidden email]> wrote:
On Wed, Feb 08, 2017 at 11:35:01AM -0500, Daniel Baston wrote:
> Sorry, I'm not sure I understand which direction you're asking me to
> pursue.  Are you asking that I write some new functions ST_IsCW and
> ST_IsCCW that apply _only_ to LineStrings, and then rename the four
> functions proposed in the PR to something else?

I'd love ST_IsCW, ST_IsCCW, ST_ForceCW and ST_ForceCCW that only apply
to _closed_ LineStrings, raising an error on anything else.

As for polygons, the only missing functionality I see would be an
ST_IsRHR, to be a companion to ST_ForceRHR.

I still hadn't checked what ST_ForceLHR does. Hopefully it's just
the reverse of ST_ForceRHR, in which case we could just make sure
to make it available even when SFCGAL is not in place.

That said, I remember this whole thing started in an attempt to
reduce the confusion with the "Right Hand Rule" concept. As I
agree with you about NOT changing semantic of a very old function,
I don't see how adding more functions help.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Wed, Feb 08, 2017 at 03:05:33PM -0500, Daniel Baston wrote:
> The idea was that adding functions with different names would be helpful,
> because "RHR" and "LHR" mean different things to different people (and
> therefore don't mean much of anything.)

In PostGIS "RHR" and "LHR" have well-documented meaning, right ?

> See, for example, the fourth bullet under
> https://tools.ietf.org/html/rfc7946#section-3.1.6

The Wikipedia definition of the rule is about 3d and implies a 3D space,
which is not always the case within PostGIS geometries:
https://en.wikipedia.org/wiki/Right-hand_rule

If you find a name/label which means the same to everybody I'll be
happy to see a wrapper function using it. "Clockwise" for a polygon
with holes doesn't seem to be unambiguous to me (it could for example
mean "all rings are clockwise"...)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Daniel Baston
I'll try to see if I can come up with a less ambiguous name, without resorting to ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings, but I'll also note that the proposed terminology has been used by PostGIS internally since 2010:


Dan


On Wed, Feb 8, 2017 at 3:17 PM, Sandro Santilli <[hidden email]> wrote:
On Wed, Feb 08, 2017 at 03:05:33PM -0500, Daniel Baston wrote:
> The idea was that adding functions with different names would be helpful,
> because "RHR" and "LHR" mean different things to different people (and
> therefore don't mean much of anything.)

In PostGIS "RHR" and "LHR" have well-documented meaning, right ?

> See, for example, the fourth bullet under
> https://tools.ietf.org/html/rfc7946#section-3.1.6

The Wikipedia definition of the rule is about 3d and implies a 3D space,
which is not always the case within PostGIS geometries:
https://en.wikipedia.org/wiki/Right-hand_rule

If you find a name/label which means the same to everybody I'll be
happy to see a wrapper function using it. "Clockwise" for a polygon
with holes doesn't seem to be unambiguous to me (it could for example
mean "all rings are clockwise"...)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Wed, Feb 08, 2017 at 03:35:05PM -0500, Daniel Baston wrote:
> I'll try to see if I can come up with a less ambiguous name, without
> resorting to
> ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings, but
> I'll also note that the proposed terminology has been used by PostGIS
> internally since 2010:
>
> https://github.com/postgis/postgis/commit/2d07d7eb59d2bb8db9d4773cd84619cd696bc471

Interesting, that one turned LWGEOM_forceRHR_poly
into LWGEOM_force_clockwise_poly. In 2010 I was
distracted, or I'd have suggested to just add
documentation in the header file :)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Regina Obe-2
In reply to this post by Daniel Baston

Dan,

 

You should really just call it - ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings

 

strk just loves to type J

 

He may ask you to remove the ST_ though.

 

Sorry couldn't resist.

 

From: postgis-devel [mailto:[hidden email]] On Behalf Of Daniel Baston
Sent: Wednesday, February 08, 2017 3:35 PM
To: PostGIS Development Discussion <[hidden email]>
Subject: Re: [postgis-devel] RFC - Orientation checking and forcing functions

 

I'll try to see if I can come up with a less ambiguous name, without resorting to ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings, but I'll also note that the proposed terminology has been used by PostGIS internally since 2010:

 

 

Dan

 

 

On Wed, Feb 8, 2017 at 3:17 PM, Sandro Santilli <[hidden email]> wrote:

On Wed, Feb 08, 2017 at 03:05:33PM -0500, Daniel Baston wrote:
> The idea was that adding functions with different names would be helpful,
> because "RHR" and "LHR" mean different things to different people (and
> therefore don't mean much of anything.)

In PostGIS "RHR" and "LHR" have well-documented meaning, right ?

> See, for example, the fourth bullet under
> https://tools.ietf.org/html/rfc7946#section-3.1.6

The Wikipedia definition of the rule is about 3d and implies a 3D space,
which is not always the case within PostGIS geometries:
https://en.wikipedia.org/wiki/Right-hand_rule

If you find a name/label which means the same to everybody I'll be
happy to see a wrapper function using it. "Clockwise" for a polygon
with holes doesn't seem to be unambiguous to me (it could for example
mean "all rings are clockwise"...)


--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel

 


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Fri, Feb 10, 2017 at 12:29:51AM -0500, Regina Obe wrote:

> You should really just call it - ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings
> strk just loves to type :)
> He may ask you to remove the ST_ though.
>
> Sorry couldn't resist.

This was a good one :)

Anyway, RHR is pretty short already, I don't feel the need to change that.
And for the new one, CW and CCW are perfect for me :)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Daniel Baston
In reply to this post by Sandro Santilli-3
I'd like to wrap this up, if possible.

Are the proposed function additions acceptable if I rename them to the following?

ST_ForcePolygonCW
ST_ForcePolygonCCW
ST_IsPolygonCW
ST_IsPolygonCCW

Dan

On Thu, Feb 9, 2017 at 3:35 AM, Sandro Santilli <[hidden email]> wrote:
On Wed, Feb 08, 2017 at 03:35:05PM -0500, Daniel Baston wrote:
> I'll try to see if I can come up with a less ambiguous name, without
> resorting to
> ST_ForcePolygonsClockwiseExteriorRingAndCounterClockwiseInteriorRings, but
> I'll also note that the proposed terminology has been used by PostGIS
> internally since 2010:
>
> https://github.com/postgis/postgis/commit/2d07d7eb59d2bb8db9d4773cd84619cd696bc471

Interesting, that one turned LWGEOM_forceRHR_poly
into LWGEOM_force_clockwise_poly. In 2010 I was
distracted, or I'd have suggested to just add
documentation in the header file :)

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel


_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel
Reply | Threaded
Open this post in threaded view
|

Re: RFC - Orientation checking and forcing functions

Sandro Santilli-3
On Wed, Mar 15, 2017 at 04:49:32PM -0400, Daniel Baston wrote:
> I'd like to wrap this up, if possible.
>
> Are the proposed function additions acceptable if I rename them to the
> following?
>
> ST_ForcePolygonCW
> ST_ForcePolygonCCW
> ST_IsPolygonCW
> ST_IsPolygonCCW

Sounds good to me.
Just make sure to specify what happens upon passing non-poligonal inputs,
including closed linestrings.

--strk;
_______________________________________________
postgis-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/postgis-devel