确定几何形状层次结构所需的算法

Question

我一直在尝试开发一种算法，根据一个形状是否完全封闭在另一个形状的周边内，对一组封闭的几何图形进行排序，但运气不佳。完全分析后，我应该得到一个定义层次结构的树结构。

我可以进行实际比较，即一个形状是否完全在另一个形状的范围内。尽管对无组织的输入进行排序，但我遇到了困难。我怀疑解决方案涉及二叉树结构和递归代码，我从来都不擅长。

几何数据在生成排序的层次结构数据之前已经过清理，因此开放路径、重叠、部分重叠和自相交等问题不应该成为问题。

下面是我一直在使用的一组测试图，可能有助于说明我的问题。

作为人类，我能看出黄色不在蓝色之中，蓝色也不在黄色之中。它们都在绿色形状之内，绿色形状在红色之内……等等。（色盲者见谅）

结果树如下：

我正在使用 C#，但认为它与问题无关。

谢谢

编辑 1

一个更简洁的问题可能是 "How do I generate this tree with the correct order?"（给出的数据没有特别的顺序）。这只是你的基本教科书吗"binary search tree insertion"我可能想多了？

编辑 2

尝试将 Norlesh 的伪代码转换为 C# 并将其绑定到我现有的代码中，我最终得到以下结果：

        // Return list of shapes contained within container contour but no other
    private List<NPContour> DirectlyContained(NPContour container, List<NPContour> contours)
    {
        List<NPContour> result = new List<NPContour>();

        foreach (NPContour contour in contours)
        {
            if (container.Contains(contour))
            {
                foreach (NPContour other in contours)
                {
                    if (other.Contains(contour))
                        break;
                    result.Add(contour);
                }
            }
        }

        return result;
    }

    // Recursively build tree structure with each node being a list of its children
    private void BuildTree(NPContourTreeNode2 parent, List<NPContour> contours)
    {
        List<NPContour> children = DirectlyContained(parent.Contour, contours);

        if (children.Count > 0)
        {
            // TODO: There's probably a faster or more elegant way to do this but this is clear and good enough for now
            foreach (NPContour child in children)
            {
                contours.Remove(child);
                parent.Children.Add(new NPContourTreeNode2(child));
            }

            foreach (NPContourTreeNode2 child in parent.Children)
            {
                BuildTree(child, contours);
            }
        }
    }

...以及调用代码....

            List<NPContour> contours = new List<NPContour>();
        List<NPContour> _topLevelContours = new List<NPContour>();
        bool contained = false;

        foreach (NPChain chain in _chains)
        {
            if (chain.Closed)
            {
                NPContour newContour = new NPContour(chain);
                contours.Add(newContour);
            }
        }

        //foreach (NPContour contour in contours)
        for (int i = 0; i < contours.Count(); i++)
        {
            contained = false;
            foreach (NPContour container in contours)
            {
                if (container.Contains(contours[i]))
                {
                    contained = true;
                    continue;
                }
            }
            if (contained == false)
            {
                _topLevelContours.Add(contours[i]);
                contours.Remove(contours[i]);
            }
        }

        foreach (NPContour topLevelContour in _topLevelContours)
        {
            NPContourTreeNode2 topLevelNode = new NPContourTreeNode2(topLevelContour);
            BuildTree(topLevelNode, contours);
        }

我想我一定是误解了翻译中的某些内容，因为它不起作用。我将继续努力，但我想 post 此处的代码希望有人可以帮助指出我的错误。

请注意，伪代码中存在差异，因为 buildTree 没有 return 任何内容，但在调用代码中附加了一个 return 值......好吧，无论如何，我有点困惑它到底应该去哪里。我了解了该示例的总体思路，但我认为我可能遗漏了一些重要的要点。

到目前为止，在我的简短调试中，我似乎从下面的示例中获得了不止一个顶级形状（而应该只有一个）和各种子级的倍数（大约 55？）。希望以后能给出更多的调试信息

Answer 1

下面是一些伪代码，可以实现您的目标：

// return true if shape is enclosed completely inside container function contains(container, shape); // return list of shapes contained within container shape but no other. function directlyContained(container, shapes) { result = [] for (shape in shapes) { if (contains(container, shape)) { // check its not further down hierarchy for (other in shapes) { if (contains(other, shape)) { break // not the top level container } result.append(shape) } } } return result; } // recursively build tree structure with each node being a list of its children // - removes members of shapes list as they are claimed. function buildTree(parent, shapes) { children = directlyContained(parent, shapes) if (children.length > 0) { shapes.remove(children); parent.append(children); for (child in children) { // recall on each child buildTree(child, shapes); } } }function findTopLevel(shapes) { result = [] // find the one or more top level shapes that are not contained for shape in shapes { contained = false; for (container in shapes) { if (contains(container, shape)) { contained = true; continue; } } if (contained = false) { scene.append(shape); shapes.remove(shape); } } return result; } shapes = <...>; // list initialized with the unsorted shapes scene = findTopLevel(shapes); shapes.remove(scene); for (top in scene) { buildTree(top, shapes); }

确定几何形状层次结构所需的算法

Algorithm needed to determine heirarchy of geometric shapes

c#

algorithm

binary-search-tree