There is one potential issue with the simplified region model we have in the current document, specifically the Polygon. I wanted to get this out so we could discuss it at the telecon. We do not necessarily have to change or chose anything (see IMPORTANT BIT at the bottom). And sorry - this is a rather long message :)
-- The model can support a simple polygon (convex or concave) with a single contained area (no multiple disconnected areas) and no holes. This is fine for basic descriptive geometry. However, when people have geometry constructs in their toolbox, the next thing they want are operators that create new shapes, eg intersection and union. With intersection, we would be able to support polygon intersection polygon as that makes another simple concave or convex polygon. However, circle-circle and circle-polygon can make shapes we cannot describe. With union, there are numerous issues:Received on 2008-02-26Z19:34:01
- if two polygons do not intersect, the union is disjoint (two disconnected
areas)
- the union of 2 polygons (need at least 3 convex polygons) can make a new
polygon with a hole in it
- like circle-circle or circle-polygon, union can make shapes we cannot
describe here Practical experience: In CVO we store polygon bounds for observations in our database. We have some applications that conpute and store the intersection and union of these polygons (for different purposes). We started with the simple polygon model we have in ADQL now, but when we got to using union we had to extend it to handle holes and disjoint polygons. We found several solutions: (acronym: CAG == Constructive Area Geometry) 1. define a polygon as an outer boundary and zero or more inner boundaries (to describe holes) -- this is what the OpenGIS polygon class does, handles holes only 2. define a container shape to hold 2+ shapes internally, optionally with an operator saying if the container is a union of the contents or intersection -- this is what STC does, if I recall, and is also what OpenGIS does with it's Multi- classes (except the OpenGIS model places some restrictions like the contents cannot overlap).... this solves the problem by simply not doing the CAG operation at all and just storing the operations needed to get the result. Further, the OpenGIS approach cannot (without further extension) describe the intersection or union of a circle and polygon - eg something with both straight and curved boundary segments. 3. from computer graphics people: in graphics the shape model (see the GeneralPath class in java.awt.geom, for example) allows for one to define a path where each segment has both starting and ending coordinates and a flag saying what kind of edge it is. Disjoint polygons are defined by having a second loop (eg move,line,line,...,close,move,line,line,...close). Holes are described by putting a second loop inside the first and going around in the opposite direction. Basically, each vertex becomes a pair of coordinates and an additional flag saying what kind of edge it is. Anyway, I mocked up all three ways to extend our simple geom library and the result was that #3 was much much simpler: it is slightly more complex when you do have only simple polygons but doesn't get much harder when you manipulate them. On the other hand, #1 only solves one of the problems. #2 makes for the most cumbersome data structure and leaves the user to redo all the geometry computations (and thus have that geometry code on the client side) to make any sense of the result). *** IMPORTANT BIT HERE *** sorry it is so far down :) The issue isn't that our current model is incorrect - rather when we desire to extend it to support CAG operations like intersection and union we will be faced with a choice: A -- an only slightly more complex model (from graphics) that is not backwards compatible (in serialisation form, each vertex requires an edge type flag) B -- extend by adding container classes, backwards compatible but much more cumbersome to use In a software environment, the clear winner was A and we did the necessary refactoring to get the best technical solution (I didn't do the fully general solution up front for the simple reason: it was more complex and I didn't foresee the need). That has paid off as we can now do lots of fancy geometry stuff. However, in a standards specification, the compatibility weighs much heavier and we *may* be forced to chose between the technically superior/elegant solution and the inferior/complex backwards compatible solution. I say may because it's possible there are options for extending to A in a backwards compatible way. It really comes down to the old design problem of designing 1.0 but being at least aware of what 1.1 or 2.0 will likely contain and not making the future too painful. In that sense, it is a question of "if we intend to or need to add intersection and union later", we should at least think about the ramifications and not make that too painful. -- Patrick Dowler Tel/Tél: (250) 363-6914 | fax/télécopieur: (250) 363-0045 Canadian Astronomy Data Centre | Centre canadien de donnees astronomiques National Research Council Canada | Conseil national de recherches Canada Government of Canada | Gouvernement du Canada 5071 West Saanich Road | 5071, chemin West Saanich Victoria, BC | Victoria (C.-B.)