From: Tom Lane <tgl@sss.pgh.pa.us>
To: dhyan@nataraj.su
cc: pgsql-bugs@lists.postgresql.org
Subject: Re: BUG #18214: poly_contain (@>) hangs forever for input data with
 zeros and infinities
In-reply-to: <18214-891f77caa80a35cc@postgresql.org>
References: <18214-891f77caa80a35cc@postgresql.org>
Comments: In-reply-to PG Bug reporting form <noreply@postgresql.org>
	message dated "Fri, 24 Nov 2023 11:21:39 +0000"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <3331141.1700848862.1@sss.pgh.pa.us>
Date: Fri, 24 Nov 2023 13:01:02 -0500
Message-ID: <3331142.1700848862@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/3331142.1700848862%40sss.pgh.pa.us>
Precedence: bulk

PG Bug reporting form <noreply@postgresql.org> writes:
> In postgreses 14-16, you execute following query it will work "forever" 

> select '((-inf, 0), (0, inf), (-inf, 0), (0, inf), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0))'::polygon @> '((0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0,
> 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
> (-inf, 0))'::polygon;

I poked at this a bit.  v13 and earlier return quickly, although their
answer is "false" which I'm not too sure is correct.  git bisect shows
the behavior changed at

commit 8597a48d01b6cc0b09ff626253ac93c67e5516d5
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Sat Nov 21 16:46:43 2020 -0500

    Fix FPeq() and friends to get the right answers for infinities.

I'm inclined to think that poly_contain_poly, or more specifically
lseg_inside_poly, is just a broken algorithm.  I don't have much faith
that it gets the right answer (especially for non-simple polygons,
which we do try to handle correctly in e.g. point_inside), and it's
pretty obviously horrid from a time-complexity standpoint.  I think
we need to throw it away and start fresh rather than try to band-aid
it further.

I googled "polygon containment" and read about sweep-line algorithms,
which might be the way to go here, but it's not something I care to
put time into personally.

> My colleagues have poked this bug a bit, and suggested that the cause of the
> problem is probably the lseg_contain_point(LSEG *lseg, Point *pt) function,
> that gives wrong result for the infinity case.

Hmm, yeah, that pretty obviously fails for infinities, or any values
large enough to cause overflow.  I doubt that fixing it is sufficient
to rescue poly_contain_poly, but it seems worth improving anyway
because it has other callers.  Not quite sure how we should define
its behavior for infinity inputs though.  If the point has any Inf
coordinate, it seems clear that it's on the segment only if it is
equal() to one of the endpoints.  But what about a finite point
versus a segment with Inf coordinate(s)?

			regards, tom lane