I have implemented a new contour finding algorithm. This new algorithm is based on what I can remember from a paper I discussed with Dave and Britton some time ago, but since I can't find the paper anymore, it's not necessarily a full implementation. The new strong points are that while the initial identification *may* be slower (although actually, I'm *not* sure it is!) you can essentially scroll over the contours instantly; pulling out level sets at arbitrary densities is *very* cheap, so doing dendograms and other level set identification should be basically free -- in fact, pulling out trees with exact values of density for the splits/joins should be trivial. (This assumes that there are no duplicate values; in the paper I recall they suggest jittering by random values of order float-epsilon to ensure this.)
I've placed the diff for the Cython code here:
and the test script that performs the contouring and the verification here:
(you can also download these with yt_lodgeit.py --download=...)
You'll have to re-cythonize after you apply the patch. (I've already done this on Triton, and the LCA dev group install should have these functions.)
Right now it's still slightly raw. Note that the Cython function for getting the contours out, extract_identified_contours, accepts and index rather than a density. This will probably change, and I'd also like to change it such that it will actually pull out a tree rather than the indices -- which shouldn't be too hard. The index fed in here is the index in the *sorted* system, because as you'll note the densities (or whatever other field there is) must be fed in sorted such that the joins proceed outward from the lowest-index values.
Let me know what you think. I'm going to conduct some more tests and wrap it in the familiar contour interface, with additional wrapping layers for holding the full set of topology rather than the explicitly pulled-out contours. I believe this algorithm can be parallelized relatively easily, and that will be a final step after cleaning it up.