Very Computer

I have a list of 2D polygons that needs to be sorted
according to drawing order.  i.e. the outer most polygons
are rendered first and then polygons within polygons are rendered
later over the tops of parent polygon.

I want to implement this as a linked or doubly linked list.  Polygons
are added in ANY order to the list and the list is built such that no
sorting is needed to render.  i.e. simply traverse the list from front
to tail.  I could have just implemented a linked list and just added
sequentially then did a bubble sort at the end, but this doesn't seem
efficient. Yet....

Seems simple enough at first but, I seem to be having problems
when a parent polygon has more then one subpolygon.

Suggestions or pointers please?
Notes: I have polygon interior/exterior tests working.
I'm working in C++.

TIA
Brian O'Brien.

This omits handling of one very important case: intersecting polygons.
You had better be sure that this never happens in your input, because
otherwise the problem is ill-defined.

Ordinary sorting algorithms won't work, because containment does not
define the type of ordering they need --- it can return "no preference
in either direction" too easily. More precisely, writing '==' for
"neither is contained in the other"

        a == b  && b==c

is not equivalent to

        a == c

for this case.

You'll probably need a graph theory based approach. You'll have to
construct a directed acyclic graph and traverse that.
--

Even if all the snow were burnt, ashes would remain.

This problem I think would be most easily implemented in a tree-type
structure.  You can't be sure about rendering the next parent, if you aren't
sure you've rendered all of the first parents children.  If you have an
unsorted list, you won't know if you've rendered all the first parents
children until you've reached the end of the list.  This means you will have
to traverse the list once for every parent - and that includes children that
are also parents ( etc. ).

Quote:> I have a list of 2D polygons that needs to be sorted
> according to drawing order.  i.e. the outer most polygons
> are rendered first and then polygons within polygons are rendered
> later over the tops of parent polygon.

> I want to implement this as a linked or doubly linked list.  Polygons
> are added in ANY order to the list and the list is built such that no
> sorting is needed to render.  i.e. simply traverse the list from front
> to tail.  I could have just implemented a linked list and just added
> sequentially then did a bubble sort at the end, but this doesn't seem
> efficient. Yet....

> Seems simple enough at first but, I seem to be having problems
> when a parent polygon has more then one subpolygon.

> Suggestions or pointers please?
> Notes: I have polygon interior/exterior tests working.
> I'm working in C++.

> TIA
> Brian O'Brien.

The polygons do not intersect.
However they may overlap completely.

"Overlap" as in: one is completely inside the other, or as in: they're
identical? If the latter, you may be in some trouble.

Otherwise, everything's fine, I think: containment defines a directed
graph of the type graph theorists call a 'forest': a collection of
tree graphs. To construct it, you'ld start at the leaves (polygons
containing no other polygons at all), and work your way upwards.
--

Even if all the snow were burnt, ashes would remain.

In that case, you can just sort them in order of area
and draw the largest first.

--
Tom Duff.  Our core competencies are office moves and corporate
apoptosis.

Oh sure.  Make everybody else look bad.  <g>

Actually.  All the idea's were good.  If only I had found the original bug
which was
my polygon bounding box was wrong! :(