Geometry Boost List: [geometry] difference algorithm produces invalid polygon?

Subject: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-14 11:49:48

Hi,

I'm stuck with the following situation. It seems to me that the (asymmetric) difference algorithm produces invalid output from valid input:

 

Step 1:

Input A: (((((1920, 1462), (3720, 1462), (3720, 3262), (1920, 3262)))))

Input B: (((((1918, 1957), (1918, 1657), (2218, 2189), (1918, 1957)))(((3718, 1957), (3360, 2233), (3718, 1561), (3718, 1957)))(((3360, 2233), (2818, 3253), (2218, 2189), (2818, 2653), (3360, 2233)))))

Output: (((((1920, 1660), (1920, 1462), (3720, 1462), (3720, 3262), (1920, 3262), (1920, 1958), (2218, 2189), (1920, 1660)), ((3718, 1957), (3718, 1561), (3360, 2233), (3718, 1957)), ((3360, 2233), (2818, 2653), (2218, 2189), (2818, 3253), (3360, 2233)))))

 

Step 2:

Input A: Output from step 1

Input B: (((((1918, 2155), (1918, 1957), (2818, 2653), (3718, 1957), (3718, 2155), (2818, 3055), (1918, 2155)))))

Output: (((((2218, 2189), (1920, 1660), (1920, 1462), (3720, 1462), (3720, 3262), (1920, 3262), (1920, 2157), (2561, 2798), (2818, 3253), (3042, 2830), (3718, 2155), (3718, 1957), (3718, 1561), (3360, 2233), (3718, 1957), (3359, 2234), (3360, 2233), (2818, 2653), (2218, 2189)), ((2218, 2189), (1920, 1958), (2218, 2189)))))

 

Step 3:

Input A: Output from step 2

Input B: (((((1918, 2455), (1918, 2155), (2218, 2455), (1918, 2455)))(((3718, 2455), (3418, 2455), (3718, 2155), (3718, 2455)))(((2218, 2455), (3418, 2455), (2818, 3055), (2218, 2455)))))

Result: Boost.Geometry Overlay invalid input exception

 

Input B to Step 3 seems to be valid, at least it can be processed without an exception when using Input A from step 1. Thus I conclude that the output from step 2 is invalid. Can you confirm that this is a problem in GGL, possibly related to the fact that I use an integral numeric base type? If not, what's wrong with my input?

 

I am using boost 1.48.0.

 

Regards

   Volker

--
Volker Schöch | vschoech_at_[hidden]
Senior Software Engineer
think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany
http://www.think-cell.com | phone [phone] | US phone [phone]
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl