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

[Mika Heiskanen]

On 09/16/2014 10:54 AM, Sandro Santilli wrote:
>> 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.
>
> Uhm, given this description I might have not, as I'm only swapping
> the order of line components and their vertices IFF the outer shell
> is counterclockwise. If both the outer and the holes are clockwise
> there would be no reversing. Instead I understand there would need
> to be a per-ring reordering of lines depending on the winding.

I guess in the simplest terms the idea is that if you traverse the outer 
shell clockwise, then you will also have to reconnect the
linestrings by going clockwise around the rectangle. Holes you
traverse counter-clockwise, but reconnect them by going clockwise
as before. So, if no winding rule is enforced, and we process the
rings in the actual order of the vertices, then in the reconnecting
phase

    CW shell  connects from the start point
    CCW shell connects from the end point
    CCW hole  connects from the start point
    CW hole   connects from the end point

and all connecting would be done by going clockwise around the rectangle 
looking for the next vertex. The next vertex may be
the start point of the ring that is being built.

An alternative algorithm is described in

   http://dna.fernuni-hagen.de/papers/GeoInfo-2007.pdf

but it does not seem to be any simpler.

Regards,

Mika Heiskanen / Finnish Meteorological Institute