search

postgrespro / pgsphere

PgSphere provides spherical data types, functions, operators, and indexing for PostgreSQL.
https://pgsphere.org
BSD 3-Clause "New" or "Revised" License
16 stars 14 forks source link

polygon winding direction #2

Open pdowler opened 3 years ago

pdowler commented 3 years ago

The current spoly in pgsphere is allowed to be clockwise or counter clockwise and the "inside" is the smaller side of the boundary.

In the IVOA community, where postgresql+phsphere is used inn many places, the DALI standard specifies polygon as always counter clockwise with the "inside" on the left (https://www.ivoa.net/documents/DALI/20170517/REC-DALI-1.1.html#tth_sEc3.3.7). The reasons for that choice were well justified by use cases identified by the authors (me and others); I will add that material or a link in a subsequent post on this issue if needed.

The issue is that the pgsphere behaviour trips many implementers up because it is subtle and basic tests/trials work fine and the discrepancy show sup after they'd ingested a lot of data. I don't know what the solution is for this, but I'd like to start a discussion on this issue and try to find one that works. Basically, your users are often implementing IVOA standards and I think we both want that to be as easy and straightforward as possible.

obartunov commented 3 years ago

On Tue, Jul 20, 2021 at 8:47 PM Patrick Dowler @.***> wrote:

The current spoly in pgsphere is allowed to be clockwise or counter clockwise and the "inside" is the smaller side of the boundary.

In the IVOA community, where postgresql+phsphere is used inn many places, the DALI standard specifies polygon as always counter clockwise with the "inside" on the left ( https://www.ivoa.net/documents/DALI/20170517/REC-DALI-1.1.html#tth_sEc3.3.7). The reasons for that choice were well justified by use cases identified by the authors (me and others); I will add that material or a link in a subsequent post on this issue if needed.

The issue is that the pgsphere behaviour trips many implementers up because it is subtle and basic tests/trials work fine and the discrepancy show sup after they'd ingested a lot of data. I don't know what the solution is for this, but I'd like to start a discussion on this issue and try to find one that works. Basically, your users are often implementing IVOA standards and I think we both want that to be as easy and straightforward as possible.

I agreу with that issue, so what is your suggestions ? One straightforward solution is to have DALI compatible polygon 'vopoly' and let user use it.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/postgrespro/pgsphere/issues/2, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABQURYQJFBGMTZMHDRNEKMLTYWZEBANCNFSM5AWITJKQ .

-- Postgres Professional: http://www.postgrespro.com The Russian Postgres Company

pdowler commented 2 years ago

Sorry for taking so long to reply - it has been a busy few months.

Yes, I think a 'vopoly' type with compatible behaviour would be a good way to go; users could decide if they require the different behaviour/semantics and chose beteen spoly and vospoly.

On the implementation side, because 'vopoly' has a specified winding direction, it can be larger than half the sphere; there are some use cases for having a value that means and behaves (in queries) like "all sky".

A final thing (probably just to keep in mind but not necessarily implement): we will be publishing a new draft of DALI that supports a couple of new constructs:

df7cb commented 11 months ago

Does this need a new type? We could say that from some release, polygons are all left-winding, and fix all the operators to follow that convention. We'd supply a conversion function what would convert all right-winding polygons to left-winding ones that users could call as part of the upgrade.

msdemlei commented 11 months ago

On Wed, Nov 08, 2023 at 01:05:33AM -0800, Christoph Berg wrote:

Does this need a new type? We could say that from some release, polygons are all left-winding, and fix all the operators to follow that convention. We'd supply a conversion function what would convert all right-winding polygons to left-winding ones that users could call as part of the upgrade.

Hm. I'd say that's at least a really dangerous thing to do if it will silently turn small right-winding polygons into almost full-sky left-winding polygons. It is not hard to imagine the resulting symptoms: A query that before was fast and returned a few rows then is slow and returns huge result sets. And that's the best scenario because it'll be easy to notice something is wrong.

With sufficient warning, we might still want to pull it off. We could hope that pgsphere adopters are the kind of people that read release notes, in particular if we make this a major version. But I can't say I'd not wish there was a better solution.

Perhaps we can put in a magic automatic migration, i.e., see if a polygon is of the old, smaller-than-2-pi kind and turn it left-winding behind the scenes, perhaps even transparently on-disk?

pdowler commented 11 months ago

I agree that magic conversion to the specified winding direction would be undesirable as it wouldn't allow for larger than half the sphere vopoly and would probably hide bugs in s/w that generates small polygons incorrectly.

A migration mechanism for existing content would be a nice thing for operators. I would envision that as part of an alter table statement that changed the datatype of a column from spoly to vopoly. Then people chose it and in that context there would be nothing ambiguous or surprising about converting values to left-winding.

jos-de-bruijne commented 10 months ago

I am taking note of this issue, as suggested by @msdemlei when discussing possible ESDC contributions to pgsphere at ADASS 2023.

df7cb commented 10 months ago

Perhaps we can put in a magic automatic migration, i.e., see if a polygon is of the old, smaller-than-2-pi kind and turn it left-winding behind the scenes, perhaps even transparently on-disk?

spoly is a varlena type so there is room in there to stuff in extra flags. That can help make upgrading not rewrite all right-winding polygons.

But an automatic on-the-fly upgrade doesn't help with application bugs - if the app continues to put in right-winding polygons and still expects them to be "small", the database will start interpreting them as "big", and the problems are as hard to find as before.

Even a new type won't prevent this problem, if people swap in new columns with a new type, but using the old name and syntax, old apps will happily write correct or incorrect data as they like.

There will have to be a flag day where the database and all apps get switched over. (And if a new type doesn't help, we might just try to keep using the old one with better semantics.)

Related problem: scircle with radius > π/2.

vitcpp commented 10 months ago

Definitely, polygons should be oriented on the sphere, otherwise there will be some inconsistency in defining polygons. I like the idea to add a hint to spoly. By default, all the polygon data will be interpreted as it is now. We may add an optional parameter to spoly constructor. This parameter will define the input polygon data orientation: left, right or undefined orientation. By default, the undefined orientation will be used (the current behaviour). We may also introduce a new function vopoly which will interpret input data as left oriented polygons.

Internally, we may store the polygons as left oriented by reordering input point array which will be considered with undefined orientation by default. It may solve the problem with external applications, described by @df7cb. New applications will explicitly specify the orientation.