问如何有效地从八叉树/四叉树中获得结果？
EN

Stack Overflow用户

提问于 2010-06-16 17:34:03

回答 2查看 2.4K关注 0票数 3

我正在开发一款3D软件，它有时必须在大量曲线(有时约为100,000条)之间执行相交操作。最自然的方法是执行N^2边界框检查，然后边界框重叠的曲线相交。

我听说了一些关于八叉树的好消息，所以我决定尝试实现一个八叉树，看看我的性能是否会有所提高。

这是我的设计:每个八叉树节点都被实现为一个类，其中包含一个子节点列表和一个有序的对象索引列表。

当添加一个对象时，它被添加到完全包含该对象的最低节点，或者如果该对象没有填满所有的子节点，则添加到该节点的一些子节点。

现在，我要做的是检索与给定对象共享一个树节点的所有对象。为此，我遍历所有树节点，如果它们包含给定的索引，则将它们的所有其他索引添加到有序列表中。

这是高效的，因为每个节点中的索引已经排序，所以查找每个索引是否已经在列表中是很快的。然而，列表最终必须调整大小，这占用了算法中的大部分时间。所以我需要的是某种树状的数据结构，它能让我高效地添加有序数据，同时也能高效地占用内存。

有什么建议吗？

performance

graphics

data-structures

回答 2

Stack Overflow用户

回答已采纳

发布于 2010-06-16 17:42:28

SortedDictionary (.NET 2+)或SortedSet (仅限.NET 4)可能是您想要的。它们是树形结构。

SortedList是一个哑类，在结构上与List没有什么不同。

然而，我仍然不完全清楚为什么你需要这个排序的列表。也许如果你能详细说明这件事，我们可以找到一个你根本不需要排序的解决方案。例如，一个简单的HashSet就可以做到。如果散列处理得当，它在查找和插入方面都比SortedList或任何树结构都要快。

好的，现在当我清楚你想要合并排序列表时，我可以试着写一个实现。

首先，我使用SortedDictionary来存储所有数组的头部来实现合并。在每次迭代中，我从字典中删除了最小的元素，并从同一数组中添加了下一个元素。性能测试表明，SortedDictionary的开销很大，几乎不可能让它比简单的concatenation+sorting更快。它甚至很难在小型测试中与SortedList的性能相匹敌。

然后，我用定制的二进制堆实现替换了SortedDictionary。性能提升非常显著(超过6倍)。这种堆实现甚至在某些测试中击败了.Distinct() (通常是最快的)。

下面是我的代码：

class Heap<T>
{
    public Heap(int limit, IComparer<T> comparer)
    {
        this.comparer = comparer;
        data = new T[limit];
    }

    int count = 0;
    T[] data;

    public void Add(T t)
    {
        data[count++] = t;
        promote(count-1);
    }

    IComparer<T> comparer;

    public int Count { get { return count; } }

    public T Pop()
    {
        T result = data[0];
        fill(0);
        return result;
    }

    bool less(T a, T b)
    {
        return comparer.Compare(a,b)<0;
    }

    void fill(int index)
    {
        int child1 = index*2+1;
        int child2 = index*2+2;
        if(child1 >= Count)
        {
            data[index] = data[--count];
            if(index!=count)
                promote(index);
        }
        else
        {
            int bestChild = child1;
            if(child2 < Count && less(data[child2], data[child1]))
            {
                bestChild = child2;
            }

            data[index] = data[bestChild];
            fill(bestChild);
        }
    }

    void promote(int index)
    {
        if(index==0)
            return;
        int parent = (index-1)/2;
        if(less(data[index], data[parent]))
        {
            T tmp = data[parent];
            data[parent] = data[index];
            data[index] = tmp;
            promote(parent);
        }
    }
}

struct ArrayCursor<T>
{
    public T [] Array {get;set;}
    public int Index {get;set;}
    public bool Finished {get{return Array.Length == Index;}}
    public T Value{get{return Array[Index];}}
}

class ArrayComparer<T> : IComparer<ArrayCursor<T>>
{
    IComparer<T> comparer;
    public ArrayComparer(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public int Compare (ArrayCursor<T> a, ArrayCursor<T> b)
    {
        return comparer.Compare(a.Value, b.Value);
    }
}

static class HeapMerger
{
    public static IEnumerable<T> MergeUnique<T>(this T[][] arrays)
    {
        bool first = true;
        T last = default(T);
        IEqualityComparer<T> eq = EqualityComparer<T>.Default;
        foreach(T i in Merge(arrays))
            if(first || !eq.Equals(last,i))
            {
                yield return i;
                last = i;
                first = false;
            }
    }

    public static IEnumerable<T> Merge<T>(this T[][] arrays)
    {
        var map = new Heap<ArrayCursor<T>>(arrays.Length, new ArrayComparer<T>(Comparer<T>.Default));

        Action<ArrayCursor<T>> tryAdd = (a)=>
        {
            if(!a.Finished)
                map.Add(a);
        };

        for(int i=0;i<arrays.Length;i++)
            tryAdd(new ArrayCursor<T>{Array=arrays[i], Index=0});

        while(map.Count>0)
        {
            ArrayCursor<T> lowest = map.Pop();
            yield return lowest.Value;
            lowest.Index++;
            tryAdd(lowest);
        }
    }
}

票数 0

Stack Overflow用户

发布于 2010-06-16 17:46:53

假设您将OctTree的大小作为树的一个属性，那么您应该能够预先分配一个大于您可以放入的内容的数量的列表。预分配大小将阻止调整大小，只要大小大于您所需的大小。我假设您正在使用SortedList来保存您的有序结果。

var results = new SortedList<Node>( octTree.Count );
// now find the node and add the points
results = result.TrimToSize(); // reclaim space as needed