Traversal

I started out by fixing the issue I had previously where my limited spanning trees were sometimes not trees. The problem was that my artificial restriction on size sometimes resulted in one tree thinking it had combined with another, but the other did not combine with it. In any case, I fixed it.

After this, I finished an algorithm that created an order in which to traverse the trees. This is not the final algorithm, but it’s good enough for now.

The algorithm works by assigning each tree to a point on the edge closest to it, then saves the trees in the order that they appear along each edge. This has some issues, mainly that two consecutive trees can be a bit far from each other, and that it assumes the order of the trees should be based purely on the start point, but it can be improved on later.

One strategy for drawing a curve around the circles in order is to do something like the following:

In this image I swap from tree to tree, just drawing a line around the perimeter of the tree. I am also looking into a strategy of using the circumcircle connecting any two nodes (and an unknown third node), but it’s still unclear to me how to deal with leaves in this strategy.

The tree traversal strategy in this image is roughly this:

In the first two trees, I traverse to a leaf, and then traverse across leaves in order until there are none left, and then return to the root. In the third strategy, I visit every node while swapping between leaves. This is the strategy I have implemented as a beginning.

Going clockwise around the polyline, here is the order in which my first algorithm plans to visit the nodes:

My algorithm still has bugs. As mentioned earlier, the tree selection algorithm is not great. As well, I attempt to traverse every exterior tree in a clockwise manner and every interior tree in a counter-clockwise manner, but it seems like my current implementation is bugged.

Along the way I also fixed a bug preventing circles from generating at a small distance away from the exterior of the polyline. The circles can now be packed properly.