[geos-devel] Geometry/Rectangle Intersection: line touching rectangle

[Sandro Santilli]

On Tue, Sep 09, 2014 at 06:20:04PM +0300, Mika Heiskanen wrote:
> On 09/09/2014 05:56 PM, Sandro Santilli wrote:
> >Another case where output differs from ST_Intersection:
> >
> >   Rectangle: 0,0 10,10
> >    Geometry: LINESTRING(10 0, 20 0)
> >    Expected: POINT(10, 0)
> >    Obtained: EMPTY
> >
> >   +----------+
> >   |          |
> >   |          |
> >   |          |
> >   +----------O------------+
> >
> >That is, the intersection of a rectangle and a linestring whose endpoint
> >is on one of its corners is expected to yeld the corner point.
> 
> Well, this is unfortunate. As implied earlier, I did not check any
> standards on how such things are resolved, I merely programmed it
> as quickly as I could from the perspective of rendering. Our
> algorithm produces only linestrings and polygons for respective
> input. Points are generated only for pointlike input.
> 
> If this is how clipping is to be defined, it is going to have
> a serious impact on the algorithm. There aren't that many special
> cases, but handling them within the already complex if-else
> sequences could be a nasty task.
> 
> The special cases are as far as the current code would be concerned are:
> 
> * a vertex is on a rectangle edge
> * a vertex is on a rectangle corner
> * an edge passes through a corner of the rectangle

I found another:

 * an edge goes on a rectangle edge:

  Rectangle: 0,0 10,10
   Geometry: LINESTRING (0 3,0 5,0 7)
   Expected: LINESTRING (0 3,0 5,0 7)
   Obtained: EMPTY

> The RectangleClipBuilder API would have to be enlarged to
> handle individual points. The implementation should probably
> merge all such points into a multipoint.
> 
> I'd like to see a reference where all such special cases
> are defined explicitly. (No, I never looked for one, as explained
> before.) In your previous example a linestring was split in half
> because a vertex is on the rectangle edge. This is kind of consistent
> with the interpretation that the vertex is considered to be out.
> However, the example presented here is consistent with the
> interpretation that the vertex should be considered to be in.

Indeed the results are formally confusing.
I hope Martin Davis can chime in, being the author of the currently
used algorithm.

--strk;

 ()  ASCII ribbon campaign  --  Keep it simple !
 /\  http://strk.keybit.net/rants/ascii_mails.txt