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

Question

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

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

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

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

作为一个人，我可以看到黄色不在蓝色中，蓝色也不在黄色中。它们都在绿色形状之内，绿色形状在红色之内……等等。 (色盲者见谅)

结果树如下:

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

谢谢

编辑 1

一个更简洁的问题可能是“我如何以正确的顺序生成这棵树？” (给出的数据没有特别的顺序)。这只是我想多了的基础教科书“二叉搜索树插入”吗？

编辑 2

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

        // 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);
        }

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

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

到目前为止，在我的简短调试中，我似乎从下面的示例中获得了不止一个顶级形状(而应该只有一个)和各种子级的倍数(大约 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);
}