algorithm - 将无序列表排序到树结构的算法

Question

我正在寻找一个算法，以排序到一个树结构无序的项目列表，使用最小数量的“是子”比较操作尽可能。
对我的具体案例有一点了解，但我想我只是在寻找一种我找不到的通用排序算法（这是一个很难完善的搜索词）。
我有一个无序的轮廓列表，这只是描述闭合多边形的坐标列表。我想创建一个表示这些等高线之间关系的树，这样最外层就是根，每个等高线都是下一级的子等高线，以此类推所以一个树结构，每个节点有零到多个子节点。
该算法的一个关键要求是将用于确定某个轮廓是否是另一个轮廓的子轮廓的测试保持在最小值，因为该操作非常昂贵。等高线可以（而且通常会）共享许多顶点，但不应相交。这些共享顶点通常出现在达到地图限制的地方-在地图的直边上画一组同心的半圆形。如果我需要在得到一个确定的答案之前通过大量的点对线测试，那么poly测试中的点是缓慢的。
这是我到目前为止提出的算法。毫无疑问，这是相当幼稚的，但确实有效。可能有一些启发式方法可能会有帮助-例如，一个轮廓只可能是另一个深度在一定范围内的轮廓的子轮廓-但我想首先确定基本算法。第一个红旗是它是指数型的。

for each candidate_contour in all_contours
    for each contour in all_contours
        // note already contains means "is direct or indirect child of"
        if contour == candidate_contour or contour already contains(candidate_contour)
            continue
        else
            list contours_to_check
            contours_to_check.add(candidate_contour)

            contour parent_contour = candidate_contour.parent
            while (parent_contour != null)
                contours_to_check.add(parent_contour)
                parent_contour = parent_contour.parent

            for each possible_move_candidate in contours_to_check (REVERSE ITERATION)
                if possible_move_candidate is within contour
                    // moving a contour moves the contour and all of its children
                    move possible_move_candidate to direct child of contour
                    break

所以这是可行的——或者至少看起来是可行的——但是对于一个不平凡的轮廓数（想想——几百到几千），它变得非常缓慢。
有没有一种从根本上更好的方法来做到这一点，或者确实有—有没有已知的算法来处理这一点如前所述-在我的情况下，关键是保持“是轮廓内”比较到最低限度。
编辑添加解决方案的基础上，吉姆的回答如下-谢谢吉姆！
这是第一次迭代-产生了良好的（10倍）改进。迭代2见下文。
一旦轮廓集变得非常大，这段代码与我的原始算法相比就快了10倍。请看下面的图像，它现在在几秒钟内被排序（v之前30多秒），并按顺序呈现。我认为有进一步改进的空间，添加一些启发式-例如，现在原始列表是按照面积排序的，那么每个新的候选必须是树中某个地方的叶节点困难在于确定哪些分支要遍历以测试现有的叶子——如果有许多分支/叶子，那么通过检查顶部的分支来降低搜索空间可能更快。想点别的！

    public static iso_area sort_iso_areas(List<iso_area> areas, iso_area root)
    {
        if (areas.Count == 0)
            return null;

        areas.Sort(new iso_comparer_descending());

        foreach (iso_area area in areas)
        {
            if (root.children.Count == 0)
                root.children.Add(area);
            else
            {
                bool found_child = false;
                foreach (iso_area child in root.children)
                {
                    // check if this iso_area is within the child
                    // if it is, follow the children down to find the insertion position
                    if (child.try_add_child(area))
                    {
                        found_child = true;
                        break;
                    }   
                }
                if (!found_child)
                    root.children.Add(area);
            }
        }
        return root;
    }

    // try and add the provided child to this area
    // if it fits, try adding to a subsequent child
    // keep trying until failure - then add to the previous child in which it fitted
    bool try_add_child(iso_area area)
    {
        if (within(area))
        {
            // do a recursive search through all children
            foreach (iso_area child in children)
            {
                if (child.try_add_child(area))
                    return true;
            }
            area.move_to(this);
            return true;
        }
        else
            return false;
    }

迭代二：仅与现有叶子进行比较
根据我以前的想法，新的轮廓只能适应现有的叶子，它使我想到，事实上，这将是更快得多，因为聚多聚试验将失败的第一边界检查以外的所有目标叶。第一个解决方案涉及遍历一个分支以找到目标，根据定义，沿途的每个多边形都将通过边界检查，并涉及一个完整的poly-in-poly测试，直到没有找到更多的叶子。
继Jim的评论和对代码的重新检查之后，第二个解决方案不幸地失败了。我想知道在树枝之前看看树中较低的元素是否还有一些优点，因为poly-in-poly测试应该很快失败，而且你知道如果你找到一个接受候选的叶子，就没有更多的poly需要检查了。
迭代二重温
虽然轮廓线不能只适合树叶，但它们几乎总是这样，而且它们通常会适合轮廓有序列表中最近的前辈。最后更新的代码是迄今为止最快的，并且完全抛弃了树遍历。它只需向后遍历最近的较大多边形并尝试每个多边形-来自其他分支的多边形可能会在边界检查时失败poly-in-poly测试，并且由于列表的优先排序，第一个发现包围候选多边形的多边形必须是直接父多边形这段代码将排序再次降到毫秒范围，比树遍历快约5倍（poly-in-poly test的速度也有了显著的提高，而poly-in-poly test占了速度的其余部分）。根现在从区域的排序列表中获取。注意，我现在在列表中提供了一个根，我知道它包含了所有轮廓（所有轮廓的边界框）。
谢谢你的帮助——特别是吉姆——帮助我思考这个问题关键是原始的等高线排序到一个列表中，在这个列表中保证没有等高线是列表中后面等高线的子级。

public static iso_area sort_iso_areas(List<iso_area> areas)
    {
        if (areas.Count == 0)
            return null;

        areas.Sort(new iso_comparer_descending());

        for (int i = 0; i < areas.Count; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (areas[j].try_add_child(areas[i]))
                    break;    
            }              
        }
        return areas[0];
    }

我最初的尝试：133秒
迭代1（遍历分支以查找叶）：9s
迭代2（按大小升序向后遍历轮廓）：25ms（还有其他pt-in-poly改进）。

Answer 1

我以前也做过类似的事情，先是按区域排序。
如果多边形B包含在多边形A中，则多边形A的边界框必须大于多边形B的边界框。如果将边界框指定为((x1, y1), (x2, y2))，则：

A.x1 < B.x1
A.y1 < B.y1
A.x2 > B.x2
A.y2 > B.y2

（如果多边形可以共享边或顶点，则这些关系可能是 <=和 >=。）
因此，首先要做的是计算边界框，并按边界框区域降序（因此最大的是第一个）对多边形进行排序。
创建一个基本上是多边形的结构及其子结构列表：

PolygonNode
{
    Polygon poly
    PolygonNode[] Children
}

因此，首先按照边界框区域、降序和 PolygonNode结构的初始空列表对多边形进行排序：

Polygon[] sortedPolygons
PolygonNode[] theTree

现在，从面积最大的多边形 sortedPolygons的第一个成员开始，检查它是否是 theTree的任何顶级成员的子成员。如果不是，则将多边形添加到 theTree。边界框在这里有帮助，因为如果边界框测试失败，则不必执行“多边形中的完整多边形”测试。
如果它是某个节点的子节点，请检查它是否是该节点的子节点之一的子节点，然后沿着子链向下移动，直到找到插入点。
对 sortedPolygons中的每个多边形重复该操作。
最坏的情况是，该算法是o（n^2），如果没有父/子关系，则会发生这种情况。但是假设有很多嵌套的父/子关系，搜索空间会很快被缩减。
您可以通过按位置对 theTree列表和子节点列表排序来稍微加快速度。然后可以使用二进制搜索更快地找到多边形的潜在父对象。这样做会使事情稍微复杂一些，但是如果有很多顶级多边形，那么这可能是值得的。不过，我不会在第一次切割时添加这种优化。很有可能，我概述的使用顺序搜索的版本将足够快。
编辑
了解数据的性质会有帮助。当我写下我最初的回复时，我并没有意识到你的典型案例是给定多边形的排序列表， p[i]是 p[i-1]的子实例， p[i-2]是 的子实例，等等。你的评论表明，情况并不总是这样，但却是经常发生的。
鉴于此，也许您应该对实现进行简单的修改，以便保存最后一个多边形并首先检查它，而不是从树开始。所以你的循环看起来像这样：

    iso_area last_area = null;    // <============
    foreach (iso_area area in areas)
    {
        if (root.children.Count == 0)
            root.children.Add(area);
        else if (!last_area.try_add_child(area))  // <=======
        {
            bool found_child = false;
            foreach (iso_area child in root.children)
            {
                // check if this iso_area is within the child
                // if it is, follow the children down to find the insertion position
                if (child.try_add_child(area))
                {
                    found_child = true;
                    break;
                }   
            }
            if (!found_child)
                root.children.Add(area);
        }
        last_area = area;      // <============
    }
    return root;

如果数据是如您所说的，那么这种优化应该会有很大帮助，因为它消除了通过树进行的大量搜索。