Geometry Boost List: [ggl] Intersection of two polygons returning empty result

Subject: [ggl] Intersection of two polygons returning empty result
From: Barend Gehrels (barend)
Date: 2011-07-01 15:43:13

Hi Phillip,

On 27-6-2011 23:45, Barend Gehrels wrote:
> Hi Phillip,
>
> Thanks for the report.
>
>
>
> On 27-6-2011 22:10, Phillip Seaver wrote:
>>
>> I think I found a bug in intersection().  I have two polygons for 
>> which intersects() correctly returns true, but intersect() results in 
>> an empty multi-polygon instead of the intersection:
>>
>> 537.99678544791459, 124.30517362077681
>> 437.36539413622404, 142.02728895075373
>> 456.33031803043468, 249.50296671450121
>> 556.96217263181723, 231.78347688272990
>> 537.99678544791459, 124.30517362077681
>>
>> and
>>
>> 437.35, 142.03
>> 461.94, 281.32
>> 564.5, 263.26
>> 539.9, 123.97
>> 437.35, 142.03
>>
>> The first polygon is the result of intersecting several other 
>> polygons, which is why there are so many numbers after the decimal 
>> place.  When I cut it down to two numbers after the decimal, it 
>> worked correctly.
>>
>> (These polygons are all from a PDF file.  Each time you set a 
>> clipping path in a PDF, the result is the intersection of the current 
>> clipping path and the new path)
>>
>> I also have a relatively short program that intersects those 
>> polygons, if you want it.  I updated my copy from the boost trunk 
>> from this morning after finding the problem.  It occurred with the 
>> older code and the newer code.
>
> Right, I can reproduce it. This is indeed an issue. I will see if it 
> can be solved. However, if you are using high precision arithmetic, 
> the intersection will result in a valid multi-polygon with one 
> polygon. I'm using this polygon-type now:
>
>     typedef boost::geometry::model::d2::point_xy<ttmath_big> point;
>
> which runs OK. It gives me an area of 
> 11151.661763015599545531972518842496488 (Don't use ttmath::Big<1,4> 
> because its default constructor is non-defined instead of zero). 
> ttmath_big is defined in the extensions/contrib folder
>
> But I'll check (probably next weekend) what is the exact reason for 
> failing with a double type, and if it (hopefully) can be solved.

Just to let know, I'm busy with it. There are no intersections found, 
which is no problem. But the "within" later on detects an inconsistent 
result. I will look at this in closer detail.

SQL Server and PostGIS do not agree, this statements:

select geometry::STGeomFromText('POINT(487.68108979206932 
133.16623128576526)',0).STWithin(geometry::STGeomFromText('POLYGON((437.35 
142.03,461.94 281.32,564.5 263.26,539.9 123.97,437.35 142.03))',0))

and, for PostGIS:
select ST_Within(ST_GeomFromText('POINT(487.68108979206932 
133.16623128576526)',0),ST_GeomFromText('POLYGON((437.35 142.03,461.94 
281.32,564.5 263.26,539.9 123.97,437.35 142.03))',0))

give true and false, respectively... Boost.Geometry returns false (so 
not within, and it is also not on the border). The point is a point 
halfway between the first and second point of the first polygon.

Regards, Barend