Clever data structure to represent layered circle

Question

I'm making a game and I need to represent a "layered" circle in some clever datastructure.

A circle can have any number of layers. Each layer has a number of "slices", they can be of different lengths and pieces can be missing. The innermost layer is always a full circle. Each segment has a color, multiple segments with the same color can be next to each other.

circle with layers http://webbfarbror.se/dump/datastructure.gif

Realistically a circle wont have more than about 40 layers or about 1500 individual slices.

I will need to be able to easily find adjacent pieces to a specific piece, see if a piece is "hanging in free air" (imagine gravity towards the center), and to remove pieces leaving a hole in their place.

I've already got a few ideas for how to store this, but I thought it was an interesting question so I figured I'd post it here for kicks.

I will be coding this in Actionscript 3.0, but feel free to post ideas in any language.

Answer 1

Just thinking quickly about this, I could see some kind of directed graph with different kind of edges. Probably something like this

Node:
 + List<Node *> ParentLevel: a list of nodes at the level above (ie. more external)
 + List<Node *> ChildrenLevel: a list of nodes at the level below (ie. more internal)
 + Node * ClockwiseNeighbourgh
 + Node * AntiClockwiseNeighbourg

You would have two set nodes, one being the center circle and one representing a ficticious most outter circle.

You can then easily navigate between levels, from neighbourgh to neighbourgh in any direction. To find all the slices which are "in the air", you can start from the inner or outer node and find any slice that does not have a parent or a child.

The only thing this does not handle is the case where there is two disjunct parts to your layered circle, ie. with a fully missing layer. It could support it though by adding weights on the edges to represent the distance.

Answer 2

Think of the Mercator projection for a map of the Northern (or if you prefer Southern) hemisphere. Draw on some lines of longitude and latitude. Now, bearing in mind that a standard Mercator projection cannot show +/-90 lat think of the topmost latitude band as representing the circle around the Pole of your map. Draw the grid sufficient for your purposes. Now you have a nice planar 2D array on which to represent your data with the adjacency property that you want (remembering to wrap at the prime anti-meridian). You'll have to represent empty slices by assigning some null value to them.

I hope this rather hurried explanation is sufficient, and I'm sorry if a 2D array isn't a clever enough data structure.