Re: [HACKERS] Uninterruptible slow geo_ops.c

Emre Hasegeli <emre(at)hasegeli(dot)com> writes:
> I believe there is a simple flaw on the algorithm that causes it loop
> endlessly. It should stop looking at the other segments of the
> polygon after finding the touching one. The attached patch fixes the
> issue for the query posted to this thread. I suggest backpacking the
> fix.

I think this fix is wrong, because it assumes that the answer of
touched_lseg_inside_poly is authoritative, which it clearly isn't;
the blind "return true" for noncollinear segments breaks it.
That is, if "a" is an interior point on the polygon's first segment,
but "b" is outside the polygon, then lseg_inside_poly's first
on_ps_internal call will succeed, its second will not, then it
will call touched_lseg_inside_poly. All four of the latter's
tests will fail and it'll return true. Your patch would have us
break out of the loop without looking at any subsequent segments,
which is wrong.

It's a bit difficult to demonstrate the error, because lseg_inside_poly
isn't exposed directly, only through poly_contain (maybe we should add
an operator that does expose it?). But after experimenting awhile
I found a counterexample:

select '(0,0),(10,0),(0,10)'::polygon @> '(6,0),(7,0),(6,6)'::polygon;

This surely should return false, and it does in HEAD, but your patch
makes it return true.

There are other things to be unhappy about. As written, lseg_inside_poly
and touched_lseg_inside_poly can mutually recurse to a depth equal to
the number of points in the polygon, which opens a stack-overflow hazard.
I'd like to get rid of the recursion; it seems unnecessary.

Also, while it's sadly underdocumented what touched_lseg_inside_poly is
meant to accomplish at all, I think what it's there for is to deal with
cases involving collinear polygon segments. That is, if we inject some
useless points into the polygon, say

'(0,0),(5,0),(10,0),(0,10)'::polygon

then it should still be true that the line segment '(1,0),(9,0)' is
"inside" this polygon, but we won't find that out if we just consider
the (0,0),(5,0) and (5,0),(10,0) polygon segments independently.
I am not, however, convinced that this coding fixes that problem if
there are multiple polygon segments we need to match up against.
What concerns me is that if the first collinear poly segment we come
to is an interior subset of the segment-under-test, say we're
considering line segment '(1,0),(9,0)' and we find a poly segment
'(3,0),(5,0)', then we need to separately detect whether each of
'(1,0),(3,0)' and '(5,0),(9,0)' are subsets of the rest of the
polygon ... and I don't see where this code can handle that.
I've not managed to build a weaponized test case though.

regards, tom lane