[geos-devel] Geometry/Rectangle Intersection: winding order

[Mika Heiskanen]

On 09/15/2014 06:35 PM, Sandro Santilli wrote:
> On Mon, Sep 15, 2014 at 04:58:44PM +0200, Sandro Santilli wrote:
>> On Mon, Sep 15, 2014 at 04:53:43PM +0200, Sandro Santilli wrote:
>>> On Mon, Sep 15, 2014 at 04:12:04PM +0200, Sandro Santilli wrote:
>>>> On Mon, Sep 15, 2014 at 03:16:16PM +0200, Sandro Santilli wrote:
>>>>
>>>>> I wonder if the RectangleIntersection class should check winding order
>>>>> and reverse rings if needed...
>>>>
>>>> I've added a check for winding order in the rectangle clipping code.
>>>> This adds one more full vertices scan for each hole. It doesn't look
>>>> like code winding order would affect the algorithm, am I right ?
>>>>
>>>> See commit 4ae01eb0711baac11c102a847b90952619379b0d
>>>
>>> I was wrong, it was easy to find a case of failure with counterclockwise
>>> shell. I'll add shell winding checking too. It'll add yet another full
>>> vertex scan for the exterior ring, further degrading performances ...
>>
>> Mika, do you think RectangleIntersectionBuilder::reconnectPolygons could
>> accept an additional argument saying if the shell was CW or CCW ?
>> That way we could skip the additional full scan of the shell whenever
>> it is fully contained in the rectangle OR it fully contains it...
>
> FYI: I've added such parameter to reconnectPolygons, if the shell is
> clockwise, lines will be reversed. Seems to work fine.

Sorry, I couldn't keep up with you today.

The winding rule requirement was given in one of the algorithms I
researched for implementing the rectangle clipper. If the shells
are clockwise and the holes counter-clockwise, finding the next
linestring by looking clockwise around the rectangle and checking
the first vertex only will find the correct linestring to connect to
and the linestring will be in the correct order. The extra boolean
would indicate whether we need to compare the first or last vertex
of the linestring when deciding which linestring to connect next.
Sounds like you may have solved it already that way.

Regards,

Mika Heiskanen / Finnish Meteorological Institute