potential issue with region

[Patrick Dowler]

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:
- 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.)