Geometry Boost List: Re: [geometry] Reliable invariants of geometry representation? Validation tests?

Subject: Re: [geometry] Reliable invariants of geometry representation? Validation tests?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-10 05:49:57

Hi Barend,

> The input should be valid. Valid means valid w.r.t. OGC requirements: a so-called simple (multi)polygon, not self-intersecting, self-tangencies are allowed, correct orientation of exterior ring, and interior rings, correct closure.

Obviously, there is some broader-consensus definition of a valid polygon representation you are referring to. I was quickly searching the http://www.opengeospatial.org website, but only found the "Glossary of Terms" which mentions polygons but does not offer a very formal definition. I would appreciate it if you could point me to an authoritative source; and if such a webpage conventiently exists, may I suggest to add that reference to the documentation, too. Such a formal definition could probably answer many of my questions without the need to bother the mailing list.

> > 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? ;-)

> It has always been. No, it is not a computer science way - I have a GIS origin.

For instance, I checked Wikipedia and, more authoritative, Wolfram's Mathworld:
http://en.wikipedia.org/wiki/Polygon
http://mathworld.wolfram.com/PolygonArea.html
"Note that the area of a convex polygon is defined to be positive if the points are arranged in a counterclockwise order, and negative if they are in clockwise order (Beyer 1987)." (from Mathworld)

That's why our polygons have counter-clockwise orientation, just to give you some background. I assume that using GGL with ClockWise=false does not have any implications, performance- or otherwise?

> > [...] why did you choose to require closed polygons having begin==end? 

> It is not required. This is optional either. Opened/closed. Most (probably all) algorithms are checked on this.

Huh. Can you elaborate? Correct me if I'm wrong: Are you saying that begin==end is "optional", i.e., that all algorithms should return the same results, with the same big-O performance, whether or not begin==end, assuming that the polygon type is templated as Closed=true?

That would be greatly appreciated. We would rather have our closed polygons not carry that additional appendix-point. However, I was under the impression that leaving out that point returned a different area for the otherwise same polygon. So I am really not yet clear about this.

Because this has not been explicitly answered in your last email, let me ask again: 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?

> All this is not checked before (reason: performance). [...] There will be an is_valid algorithm.

<opinion>
These two form a really strong team. Much better than the has_self_intersections hack. I think your paradigm "shoot first ask questions later" is great for the purpose of a geometry library. Leave responsibility for valid input to the caller (but, obviously, the reponsibility to create valid output from any valid input stays with the library). I'd like to encourage that approach, and obviously it requires some tools for the caller to check for validity of input beforehand. Stick with your paradigm, provide us with some tools to check our input, and ditch has_self_intersections and similar ugly ducklings. And get rid of any (all? most?) unsuspectingly throwing exceptions along the way. Invalid input results in invalid (undefined) output, that's fair enough as long as it is QUICK. :-)
</opinion>

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