Subject: [geometry] Reliable invariants of geometry representation? Validation tests?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-09 12:01:32
Is there a guarantee that the intersection of two disjunct polygons is an empty multi container? I.e., is it fair game to check for multi_polygon::empty()? I don't want to use the intersects algorithm b/c if the polygons intersect, I need the result of the intersection anyway. Thus I can as well calculate the intersection in the first place and then test the result for emptyness, if this can be done efficiently (calling area is not considered efficient).
Can you point me to a documentation (kidding...) or maybe just explain which invariants of geometry representation your algorithms rely on, and on which invariants I can rely with regard to your algorithms? Is there any validation function available that I could use, e.g., in debug builds, to check whether these invariants hold at specific times? Is there a check for orientation? For closedness? For overlapping multi-polygons or overlapping holes?
What is the area of a polygon that does not have begin==end, if explicitly using a closed polygon model (specified by way of template parameter)? Is the result well-defined? Why doesn't this trigger some assert/throw some exception in the first place? I understand that you probably avoid checking for performance reasons. However, do you have the means for me to perform the checks when I decide it's appropriate (see above)? I am aware of the correct() algorithm, but I don't want to have problems silently fixed -- I want to be made aware and fix them at their origin.
I just came across my first GGL exception. Entirely unsuspectingly. Nowhere is it mentioned that has_self_intersections throws (which is called by top level algorithm intersection). I miss information in the documentation, but even more I miss a corresponding throw(...) declaration in the source code. Therefore please give me some guidance: Can all algorithms throw? Is there a way to turn off exceptions globally (for the GGL)? And why do you call has_self_intersections at all, if performance is your primary objective and the caller is responsible for well-formed input (as seems to be the case with regard to begin==end)?
Fun side note: has_self_intersections never returns true -- only throws or returns false. If BOOST_GEOMETRY_OVERLAY_NO_THROW is defined, it still returns false even if it has detected self-intersections.
And by the way, what's the reason why you chose clockwise as your default orientation when the convention is to view a counter-clockwise oriented polygon as filled on the inside? Is this computer science way of thinking with the origin of the coordinate system in the upper left corner of the screen? ;-)
Along the same lines -- I know you're not going to change this design any time soon, but why did you choose to require closed polygons having begin==end? One more thing to go wrong. One more line of glue code to ensure that this holds. And how do you ensure that those points don't drift apart, e.g, due to floating point rounding issues...? Looking at the surface this approach seems to create more problems than it solves.
As I said before, I am glad that the GGL is available for me to use. There are just a few things that strike me as odd, but I'll get over it...
-- 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 +49 30 666473-10 | US phone +1 800 891 8091 Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl
Geometry list run by mateusz at loskot.net