Supergons are generalised polygons allowing for non-contiguity and nested holes.
In the context of a lecture about special problems in GISystems, a suggested exercise was to write a small program that implements a data structure representing non-contiguous polygons with holes, which in turn may contain further 'holes'. By a simple generalisation we allow grouping of polygons at the top level, but the grouping of polygons and holes at any level (e.g. a group of islands with a common name). For lack of better ideas I called this structure a supergon, because it is slightly more than what is commonly understood by a polygon in the GIS field.
The definition of supergons is quite recursive (here we use the language of Forms; see my MSc thesis):
Supergon: Coproduct(Group, Polygon)
Polygon: Product(Boundary, Holes)
Boundary: Syn(Ring)
Holes: Powerset(Supergon)
Group: Powerset(Supergon)
This translates to English as follows: A supergon is either a group of supergons or a polygon with a boundary and an arbitrary number of holes which in turn are supergons. The recursive base of this nested structure is given by primitive polygon boundaries, which in the context of GIS are sometimes called rings.
The supergon structure is a tree. Each node is of one of three types:
In the figure above, upper-case letters denote "islands", lower-case letters denote "holes", and node names in italics are virtual, i.e. groups of supergons. If the depth of a node in the tree is even, the node is a "hole" and if the depth is odd, it's an "island" (where virtual nodes do not contribute to the depth).
This tree structure is implemented as a Java class, Supergon.java, which extends java.awt.Shape. It also provides some methods to determine the depth of a polygon containing a given point, to render a textual description, to draw the polygons on a canvas, etc.
The java source files were written in summer 1999.
You may download this Java source file.
/* SS99, GIS3, Urs-Jakob Rüetschi, see paper documentation! */
import java.awt.*;
// NOTE: be careful about the distinction between
// Supergon.contains() and Supergon.poly.contains() !!!
public class Supergon implements Shape {
String name; // this may be handy
Polygon poly; // the primitive polygon
Supergon sibling, childlist; // tree data structure
Supergon parent; // parent
Color color; // only for selected supergons
/* each Supergon is either simple, complex, or virtual */
public boolean isVirtual() { return poly == null; }
public boolean isSimple() { return poly != null && childlist == null; }
public boolean isComplex() { return poly != null && childlist != null; }
public Supergon getParent() { return parent; }
/* return the narrowest containing Supergon of p */
public Supergon container(Point p) {
if (poly != null && !poly.contains(p)) return null;
Supergon current = childlist, backup = (isVirtual() ? null : this);
while (current != null) { // depth-first search
if (current.isVirtual()) {
current = current.childlist;
} else if (current.poly.contains(p)) {
backup = current;
current = current.childlist;
} else current = current.sibling;
}
return backup;
}
/* p is inside the supergon iff its depth is odd */
public boolean contains(Point p) { return (depth(p) % 2) != 0; }
/* measure the depth to the supergon containing p */
public int depth(Point p) {
if (poly != null && !poly.contains(p)) return 0;
// p is contained in this; test also it's children
Supergon candidate = childlist; int max = 0;
while (candidate != null) { // effizienter wäre Breitensuche!
int d = candidate.depth(p);
if (d > max) max = d;
candidate = candidate.sibling;
}
return max + (isVirtual() ? 0 : 1);
}
/* return the overall depth of this supergon */
public int depth() {
Supergon candidate = childlist; int max = 0;
while (candidate != null) { // depth-first search
int d = candidate.depth();
if (d > max) max = d;
candidate = candidate.sibling;
}
return max + (isVirtual() ? 0 : 1);
}
public void print() {
if (isVirtual()) System.out.print(name+"{");
else System.out.print(name+"(");
if (childlist != null) childlist.print();
if (isVirtual()) System.out.print("}");
else System.out.print(")");
if (sibling != null) { System.out.print(", "); sibling.print(); }
}
public Rectangle getBounds() { // required by java.awt.Shape
if (isVirtual()) {
Supergon candidate = childlist;
Rectangle bounds = null;
while (candidate != null) {
bounds = candidate.getBounds().union(bounds);
candidate = candidate.sibling;
}
return bounds;
} else return poly.getBounds();
}
public void paint(Graphics g, boolean filled) {
g.setColor((filled) ? Color.gray : Color.white);
// special color for selected supergon:
if (color != null) g.setColor(color);
if (!isVirtual()) g.fillPolygon(this.poly);
if (sibling != null) sibling.paint(g, filled);
if (childlist != null)
childlist.paint(g, isVirtual() ? filled : !filled);
}
public Supergon(String name, Polygon poly, Supergon parent) {
this.name = name;
this.poly = poly;
this.sibling = null;
this.childlist = null;
this.color = null;
this.parent = parent;
}
public Supergon() { this("", null, null); }
public void select(Color color) { this.color = color; }
public void deselect() { this.color = null; }
// Insertion of a polygon into a supergon, which in general
// is non-trivial. To trivialize it, we impose an assumption:
// 'newPoly' is assumed to be entirely contained by a simple
// supergon. We do not test if this assumption holds and chaos
// will reign if it doesn't.
//
// Remember this when creating polygons using TestProg.java!
// Better: Rewrite insert() to handle the general case...
public void insert(Polygon newPoly, String name) throws Exception {
/**/System.out.println("insert(): name="+name+", newPoly="+newPoly);
Supergon supi = new Supergon(name, newPoly, this); // new instance
Point p = new Point(newPoly.xpoints[0], newPoly.ypoints[0]);
Supergon holder = container(p);
/**/System.out.println("try insert(): holder="+holder+", refpt="+p);
if (holder != null) { // inside: ok
/**/System.out.println("testing...");
for (int i=1; i<newPoly.npoints; i++)
if (container(p) != holder)
throw new Exception();
}
else if (isVirtual()) { // add to this group (= virtual supergon)
/**/System.out.println("adding to virtual group supergon");
holder = this;
}
else throw new Exception(); // outside: not our business
// ok, insert new supergon
/**/System.out.println("all tests passed, adding newPoly!");
supi.sibling = holder.childlist;
holder.childlist = supi;
// now search for all supergons within the new one
// TODO
}
public void remove(Supergon supergon) {
// TODO
}
public void virtualize() { poly = null; } // make this supergon virtual
public String toString() { return (name == null) ? "<anon>" : name; }
}
The Supergon class uses the existing class java.awt.Polygon for the representation of the primitive polygon contours.
public class Polygon implements Shape {
public int npoints;
public int [] xpoints;
public int [] ypoints;
public Polygon();
public Polygon(int [] xpoints, int [] ypoints, int npoints);
public void addPoint(int x, int y);
public boolean contains(int x, int y);
public Rectangle getBounds(); // from Shape
public void translate(int deltaX, int deltaY);
...
}
Instances are passed to:
Inspecting the source code (java/awt/Polygon.java v1.1.7) reveals:
There's a small and crude test application in the file TestProg.java, which essentially creates a frame and lets you draw polygons in it. Use the radio buttons to determine how mouse clicks are to be interpreted. Double click to finish drawing a polygon. The print button prints a textual representation of the current state of the supergon to the console. The selected supergon is shown in red, all others in grey. Selecting a supergon which is part of a group also selects all the other members of the group (this is to make the grouping visible). Note that not all features are implemented, in particular, deleting a supergon doesn't work.
