Geometry Boost List: Re: [geometry] self intersection doesn't find collinear intersection types

Subject: Re: [geometry] self intersection doesn't find collinear intersection types
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2016-05-11 14:01:41

Hi Sergei,

Sergei Benkovich wrote:
> Hey Adam,
> thank you very much for the response.
> my original polygon example was bad.
> but, i tried on this polygon :
>   Polygon poly { { { 10, 10 }, { 20, 10 }, { 20, 5 }, { 25, 5 }, { 25, 
> 7 }, { 30, 7 }, { 30, 3 }, { 25, 3 }, { 25, 5 }, { 20, 5 }, { 20, 0 }, 
> { 10, 0 }, { 10, 10 } }};
>
> and all i get is that there are two intersection points, and both are 
> "touch".
> and when i ran on your examples i got 4 collinear.
> is it a bug? am i doing something wrong?

No, everything is ok. The turns are oriented, so they reflect how 
segments interact with each other when the edges of both geometries are 
traversed clockwise. The only difference between 2-parameter version and 
self-intersection version is that the turns for the same segments are 
not generated because they'd all be equal.
So in your example at 2 points the edges touch and later goes in 
different ways. For {20, 5} the touch turn is generated with 
block/intersection operations, for {25, 5} it's also touch turn but the 
operations are intersection/block. It's because if we wanted to 
calculate the intersection (a set operation, set product of areas) of 
these geometries at point {20,5} we should go to {20, 0}, not to the 
{25,5} which is the next point on the edge and at {25,5} it's the opposite.

In this case:
Polygon poly{ { {0, 0},{0, 10}, {10, 10}, {10, 0}, { 10, 10 },{ 0, 10 
},{ 0, 0 } } };

4 x (equal, collinear/collinear) turns are generated because if they 
were different geometries and we wanted to calculate intersection or 
union we could follow any of the edges in both cases.

In my second example:
Polygon poly{ { { 0, 0 },{ 0, 10 },{ 10, 10 },{ 10, 0 },{ 0, 0 },{ 0, 10 
},{ 10, 10 },{ 10, 0 },{ 0, 0 } } };

2x (touch, block/block) turns are generated because we shouldn't follow 
any of these points if we wanted to calculate union (sum of areas) or 
intersection (common areas). The are collinear-opposite so if Polygons 
were valid some other turns should be generated besides these, some 
union/block or intersection/block so we'd follow them and ignore 
block/block ones.

Regards,
Adam