Construct a tree from ancestry

Since no one's replied to this yet, I'll go ahead and ask: can you describe the brute-force algorithm you're using currently?

It's seems there's at least two parts to the problem: performing the containment tests, and building the graphs. Regarding the first part, it's clear that in the general case it shouldn't be necessary to test every unique pair.

A single containment test (presumably) can yield one of the following results: A contains B, B contains A, or A and B are disjoint. In same cases the results can be inferred based on previous results. For example:

- If A contains B and B contains C, it's known that A contains C and that test can be skipped.
- If A contains B and C contains D, and if A and C are disjoint, then it's known that B and D are disjoint and that test can be skipped.

And so on.

Also, what's the range of the number of polygons that you're dealing with? If it's not a very large number, it seems a 2-d array storing the results could be used (or perhaps a triangular array or hash table if memory is a concern). The table could be filled in progressively, inferring the result from previous results where possible, else performing the intersection test and determining the result from that.

It also seems that the performance of the graph-building process could be related to the order in which the polygons are processed, in that certain processing orders might be able to make better use of existing information than others. For example, a polygon can never (?) contain another polygon whose area is greater, which a) could be used to early-out on some containment tests, and B) suggests that sorting the polygons by area might accelerate the process.

This is all just speculation though. (It seems like this is something for which there might be known formal methods that could be applied; nothing's coming to mind at the moment, but maybe someone else can offer a suggestion in that area.)

Thanks for the answer.

The polygons are fairly small, so memory is not a concern. My containment test shoots a horizontal ray from the first vertex of polygon 1 and counts the intersections with polygon 2. Polygon 1 is contained in polygon 2 if and only if the number of intersections is odd. So that's not a symmetric test (i.e. I don't know afterwards if polygon 2 is contained in polygon 1). That test could be accelerated by sorting all edges by their y-coordinates, so I can sort out edges quickly that can't intersect with the horizontal ray.

The brute force method iterated through all polygons Pn, found the root (the one that contains Pn, but is not contained in any polygon), then found all the descendants of root (all polygons contained in root), and then iteratively built the graph from there. This method is at least O(N^2) in the number of polygons.

In the mean time, I've found a somewhat better way to find the graph than the brute-force method. It's like qsort. First I pick some pivot polygon P, e.g. the first one. Then I find all children C of P and the "non-children" NC, which is simply the rest. I call the method recursively for the set C and NC of polygons. The tree resulting from C is the children of P. P might be a child or a root-level sibling of NC, so I just insert it there. If the number of children per level is bounded, this method should be about N (log N)^2. Here's the pseudo code:

struct Tree
{
Polygon Root;
List Children;
}

List CreateTrees(List plist)
{
Polygon pivot = plist[0];
List children, nonChildren;
for each Polygon p in plist (without pivot)
{
if (p is contained in pivot)
children.Add(p);
else
nonChildren.Add(p);

List childTrees = CreateTrees(children);
List nonChildTrees = CreateTrees(nonChildren);

Tree pivotTree = new Tree() { Root = pivot, Children = childTrees };
InsertChild(nonChildTrees, pivotTree);
}
}

InsertChild just iterates through each level of the tree, finds the polygon that pivot is contained in, and adds pivotTree as a child at the leaf that's found.
If pivot is not contained in any polygon, pivotTree is added as a sibling (then pivot itself is a root).

You can come at this bro from a more formal point of view.

You may notice that your containment graph IS NOT NECESSARILY A TREE, or a forest (a set of trees): take the bounding boxes given by
( (0, 0), (40, 40) )
( (20, 20) (50, 50) )
( (20, 20), (40, 40))

Your containment relation is transitive and antisymmetric. If you make it reflexive (you assume a shape is contained in itself) you've got yourself a partial order, so you know you'll always be dealing with a directed acyclic graph and can apply other useful knowledge that holds for partial orderings.

Next you can notice that if you only allow containment tests between the given shapes there will be cases where building this graph will take quadratic time (all shapes disjoint means you need to test each shape against each other shape, as you can't use containment transitivity to cut down on your search space).

So something cleverer needs to be done. My choice would be to build a spatial accelerator (see techniques for building bounding volume hierarchies, quadtrees, spatial hashes, whatever) and use that to cut down on containment tests to build your explicit graph representation (for example, adjancency lists).

Let's just introduce nomenclature:
T[] - array of trees (empty at the beginning)
P - polygons to insert into trees

I would consider following algorithm.
For each polygon p in P:
{
- remove p from P
- for each T in T[]
{
- if T is inside p, add p as new parent of T
- if p is inside T, we will find recursively its place inside T
}
- if p was not added to any T inside T[], just add p to T[] as new root node
}

Finding recursively place of p inside T is similar - you check all children of particular node (root at the beginning). If p is inside that child you call this method recursively for that child, if some child is inside p you add it between current node and that child, else you add it as a new child of the current node.

I suppose that this algorithm is quite similar to yours, but maybe it would give you any idea about further optimizations