# potential issue with region

Patrick Dowler patrick.dowler at nrc-cnrc.gc.ca
Tue Feb 26 10:39:52 PST 2008

```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
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