Cleaning up around and enhance point in polygon tests around the code

[nicklas]

Today we have four different point in ring tests.

geographic and 3D we leave separate, but the two others can be merged.

pt_in_ring_2d in liblwgeom/measures.c and (counting crossing)
point_in_ring in postgis/lwgeom_functions_analytic.c (counting winding)

they do the same thing in different ways with quite differnt api.

I would like to enhance point_in_ring by reducing the calculations for segments strict above or strict below the point, and then adjust the distance functions to also use this function after moving it to lilwgeom library.

Today pt_in_ring_2d outputs 0 for point outside ring and 1 for point inside.

point_in_ring outputs 1 for point in ring, -1 for opint outside ring and 0 for point on boundary.

[strk]

I think a good plan would be: 1) Move the winding one under liblwgeom/ 2) unit-test the winding one 3) port all clients of the crossing one to the winding one 4) -OPTIONAL- update the interface of the crossing one

I'd think the optional step (4) might be nice for comparing the two algorithms.

[nicklas]

Sounds great to me

By updating interface you mean the proposed enhancement?

[nicklas]

BTW, don't hesitate if you feel like you want to do it :-)

Otherwise I think I can try to do it coming weekend.

[strk]

By updating interface I meant have it return -1, 0 or 1 with the same semantic of the other.

And no, I don't feel like I want to do it, sorry

[nicklas]

Hmm, I did forget the fifth point in polygon. The point_in_polygon_rtree.

Does anyone know if that for some reason is called from outside so Doxygen doesn't see it. If so, I guess that should be left in postgis folder and only move point_in_polygon.

BTW, I see Doxygen thinks that one of the 3d distance functions calls point_in_polygon because I have used intersects as variable name. see the graph in the bottom of this link:  http://postgis.refractions.net/documentation/postgis-doxygen/de/dd0/lwgeom__functions__analytic_8c_ac03a9d336c58e8ca7b35195ba20513c.html#ac03a9d336c58e8ca7b35195ba20513c

Is that only a doxygen problem or should I change variable name?

[strk]

don't rely on doxygen to know what's used and what not. if in dubt, rename the function (where implemented) adding a _ prefix or something and see if the code builds/link...

[nicklas]

I think I have found out what point_in_ring_rtree is. It is the prepared geometry version. A 1D index delivers all line segments that is crossing the y-value of the point. That means point_in_ring_rtree iterates through an array of line segments instead of a pointarray. So, we will need that implementation too. But I will at least try to merge pt_in_ring and point_in_ring.

[nicklas]

This one was a little harder than I thought. What I wanted to do as described above was to merge the point in polygon functions related to distance and the one related to intersects.

The problem is that the intersects version has implemented a tolerance which is not used in the distance version. The tolerance implementation seems not to be robust as described in #852. Because of that I don't want to get that into the distance-calculations and I don't dare removing it from the intersects calculations because I have difficulties to see all the consequences.

I am afraid that this is quite a big discussion hiding here about how to or how to not handle tolerances. We meet the problems of tolerance in many parts of the code and maybe it gets even more important when getting to 3D when we have the problem of coplanar polygons and linestrings.

So, can anyone guide me. Should we just move it to "future" or close the ticket as won't fix or should we find a strategy for tolerance that can be used all over PostGIS (in this case both distance and intersects)

[strk]

Fixing the current operational bug is surely higher priority than moving any code around. Only, if the bogus code is not in liblwgeom/ it would be harder to regress-test, which is the reason for steps (1) and (2) suggested in first comment.

Note that we were using "winding" and "crossing" naming before, while you talk about "intersects" and "distance" now. Which is which ? Naming and inline documentation would help a lot in reducing the confusion.

[nicklas]

Sandro

By operational bug, do you mean #852? The rest of the bugs from those areas of the code you have fixed in other tickets I think?

About winding, crossing distance and intersects, sorry for messing things up: distance functions uses counting crossings algorithm and st_intersects (the postgis part, point in polygon) uses counting winding).

[strk]

I'm concerned about #884 , dunno if dependent by #852 or not, but it's a nasty one.

[chodgson]

#884 is actually just a logical error, there is a difference in the logic between point_in_multipoly_rtree and point_in_multipoly. I'll have a fix for it committed by tomorrow.

#547 advocates removing the _rtree stuff entirely, as long as it is similarly quick to do point_in_poly tests with a prepared geos geom. We still need a postgis-level point_in_poly test for non-cached geoms though.

[strk]

too much noise in here! Nicklas: planning to do anything here for 2.0 or should I shift everything to 2.1 ?

[nicklas]

This is connected to #852. This stopped up because I don't understand this "tolerance" implementation discussed in #852 and I don't want to put that in the point in polygon test used in distance before #852 is sorted out and I don't dare removing the tolerance part to clean it up that way. So, I shift it to 2.1 .If you find it irrelevant, just close it. Right now (last year) time is not enough, but I really hope to get back.

[strk]

Alright, now #852 is closed and regress tested. I hope it'll make your life easier in moving things around.

[robe]

Can I push this one (or close). This thread is too painfully long to read.

[nicklas]

I agree. It was a little more complicated than I first thought. I close it and it we have some "cleaning up to do" it maybe should go there.