[geos-devel] Geometry/Rectangle Intersection, line merging ?

[Mika Heiskanen]

On 09/09/2014 04:06 PM, Sandro Santilli wrote:
> On Tue, Sep 09, 2014 at 03:00:44PM +0300, Mika Heiskanen wrote:
>> On 09/09/2014 01:48 PM, Sandro Santilli wrote:
>>> RE: rectangle intersection (#699)
>>>
>>> I've plugged the leak and compared the result of Geometry::intersection()
>>> and RectangleIntersection. One difference is about the linemerge operation
>>> happening in the RectangleIntersection class, that is a line going outside
>>> and then back inside the clipping rectangle gets merged by
>>> RectangleIntersection while it is not by standard intersection.
[snip]
>> I assume you are referring to these comments:
>>
>>   * Sample clip with a rectangle 0,0 --> 10,10 without reconnecting:
>>   *
>>   *   Input:   POLYGON ((5 10,0 0,10 0,5 10))
>>   *   Output:  MULTILINESTRING ((5 10,0 0),(10 0,5 10))
>>   *   Desired: LINESTRING (10 0,5 10,0 0)
>>
>> If you recall, we wrote the algorithm for rendering. In this case if we
>> do not reconnect the two linestrings line-join behaviour will be broken
>> during rendering.
>
> But this is not the ST_Intersection equivalent operation.
> That one would output POLYGON from a POLYGON input, while it would
> output LINESTRING if the input was a LINESTRING.

Then we were not discussing the same thing. I was referring to the
way the boundary of the polygon is clipped.

> One failing test (when using ST_Intersection) is this one
> (number 87 in the unit test):
>
>      // triangle corner at left edge
>      Input:   LINESTRING (3 3,0 6,3 9)
>      Desired: LINESTRING (3 3,0 6,3 9)
>
> ST_Intersection outputs this instead:
>
>      Output:  MULTILINESTRING ((0 6, 3 9), (0 6, 3 3))

I do not see why the output should be split unless it has been
agreed in some (de facto?) standard. Has it?

> I guess line-join behavior would be broken also if the vertex was
> slightly off the rectangle, if the join style would be visible inside
> of it. It's tipical to use a somewhat larger clipping box to avoid these
> issues (for rendering purposes).

In the case I was referring to the linestring is reconnected to avoid
a broken line-join *inside* the rectangle, and does not seem to be
relevant to the discussion here.

> On a closer look the RectangleIntersection output is not even due to
> clipping but rather to RectangleIntersection::clip_linestring_parts
> considering "boundary" position the same as "internal" in the "else"
> branch around line 248. There's actually no "Boundary" position known
> in the Position enum in Rectangle.h, maybe should be added...

Rectangle::onEdge is equivalent.

However, changing that particular part of the code may be quite
compilicated - the nested if-else statements are pretty nasty.
Luckily the regression tests cover the ifs pretty well.

The first thing I'd do, if you want the original GEOS behavior, would
be to change code as follows:

156  if(pos != Rectangle::Inside)

163     if(x <= rect.xmin())
164       while(i < n && cs[i].x <= rect.xmin())
165          ++i

and similarly for lines 167-177. I fear some escalation is bound to
happen after that.

Regards,

Mika