3

我正在寻找一种算法来将项目的无序列表排序为树结构，尽可能使用最少数量的“是子”比较操作。

关于我的具体案例的一些背景知识，但我想我只是在寻找一种我无法找到的通用排序算法（这是一个很难改进的搜索词）。

我有一个无序列表的轮廓，它们只是描述闭合多边形的坐标列表。我想创建一棵树来表示这些轮廓之间的关系，这样最外面的就是根，下一层的每个轮廓都是子级，依此类推。因此，每个节点具有零对多子节点的树结构。

该算法的一个关键要求是确定一个轮廓是否是另一个轮廓的子项的测试保持在最低限度，因为此操作非常昂贵。轮廓可以（并且经常）共享许多顶点，但不应相交。这些共享顶点通常出现在达到地图限制的地方 - 描绘一组同心半圆对着地图的直边。如果我需要在得到明确的答案之前运行大量的在线点，那么多点测试会很慢。

这是我到目前为止提出的算法。毫无疑问，这很天真，但它确实有效。可能有一些启发式方法可能会有所帮助-例如，轮廓仅可能是具有一定范围内深度的另一个轮廓的子代-但我想先确定基本算法。第一个危险信号是它是指数的。

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 测试在第一次边界检查时会失败，而不是目标叶子。第一个解决方案涉及遍历分支以查找目标，根据定义，沿途的每个多边形都将通过边界检查，并涉及完整的多边形测试，直到找不到更多叶子为止。

在吉姆的评论和重新检查代码之后 - 不幸的是，第二个解决方案不起作用。我想知道在分支之前查看树中较低的元素是否仍有一些优点，因为多聚测试应该很快失败，而且你知道如果你找到一个接受候选者的叶子，那里不再需要检查的多边形了。

迭代二重温

虽然不是轮廓只能适合叶子，这是他们几乎总是这样做的情况 - 而且它们通常会适合轮廓有序列表中最近的前身。这个最终更新的代码是最快的，并且完全放弃了树遍历。它只是向后遍历最近较大的多边形并尝试每个多边形 - 来自其他分支的多边形可能会在边界检查中无法通过多边形中的多边形测试，并且发现围绕候选多边形的第一个多边形必须是直接父多边形，因为到列表的先前排序。此代码再次将排序降低到毫秒范围内，并且比树遍历快约 5 倍（对 poly-in-poly 测试也进行了显着的速度改进，这占了其余的加速）。根现在取自已排序的区域列表。知道包含所有轮廓（所有的边界框）。

感谢您的帮助——尤其是吉姆——帮助我思考这个问题。关键实际上是将轮廓原始排序到一个列表中，其中保证没有轮廓可以是列表中稍后轮廓的子级。

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 s 迭代 1（遍历分支以查找叶子）：9s 迭代 2（以升序大小顺序向后遍历轮廓）：25 毫秒（还有其他 pt-in-poly 改进）。

4

2 回答 2

2

不久前，我首先按区域排序，做了类似的事情。

如果多边形 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;

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

于 2013-11-07T19:19:05.900 回答
1

递归方法在处理树时效果很好。在您的形状分布相当均匀的情况下，以下算法应该是 O(N log(N))。如果您的形状在一个长的隧道状分布中都是同心的，那么情况会变得 O(N²) 更糟。

boolean tryAddToNode(Node possibleParent, Node toAdd)
{
    if not toAdd.isChildOf(possibleParent)
        return false
    for each child in possibleParent.children
        if(tryAddToNode(child, toAdd))
             return true
    // not a child of any of my children, but
    // it is a child of me.
    possibleParent.children.add(toAdd)
    return true
}
于 2013-11-07T18:59:33.583 回答