Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-02-28 13:56:14
Volker Schöch wrote:
>I can see two approaches to fix the library: Either allow this kind of polygons as input for all algorithms; or enhance the correct() algorithm to take input like this
>and create a polygon from it that is valid input to all other algorithms. Obviously, in the latter case, your algorithms should never produce a result that requires
>calling correct() before it can be passed as input to another algorithm.
I talked to Barend and he didn't object to my suggesting to you that you look the Boost.Polygon library. Polygon is integer coordinates based and robust to both numerical issues and all input geometries. Self-intersecting/self-touching polygons are not a problem, nor is open-closed or winding orientation a problem. The algorithm should never fail for any input. It also has a special implementation of all the operations specifically for axis-parallel manhattan geometry with integer coordinates, which is the case you seem to have. The special implementation is a performance optimization of the general algorithm. Barend and I agree that it is unlikely that you overlooked the existence of Polygon, but perhaps it could help you. You ought to be able to adapt your legacy type system to the Polygon concepts fairly easily. It would be very interesting to see a type system adapted to both Polygon and Geometry concepts so that the APIs of both libraries are available to the application programmer to mix and match functionality.
Geometry list run by mateusz at loskot.net