c# - 设置树的边界(数据结构)

Question

我们正在处理一个项目，该项目涉及一些基于树/森林算法的编码工作。

考虑在 2D 图形环境中绘制一组线 AB、BC 和 CD。这三个线段在B点和C点相连。

让我们想象一下，AB 和 BC 是水平的，但 CD 是垂直的。

现在，如果我将 AB 旋转 90 度(逆时针)，其余的线必须遵循相同的旋转度数。现在在我们的代码中 AB 和 BC 工作正常，但是当涉及到 CD 时它不遵循其余的行。

所以期待这样的事情:

似乎我们需要一个递归方法，但是不确定我们必须在这里考虑什么样的边界，因为 CD 可能最终会在其末尾得到另一行，例如DE 所以添加一个 bool 标志作为“bLastLine”在这里没有帮助。

那么我们如何才能知道一行何时结束？事实上，我需要知道如何为树指定边界。

谢谢。

Answer 1

好的，所以我要冒险了。您有节点(A、B、C、D)并且它们之间有线段。这可以被视为一个 Graph(V,E)，它可能比一棵树更适合你。

现在用于 WPF:

您的 Vertex 类将具有 ObservableCollection 类型的 Edges 属性您的 Vertex 类将具有 Point 类型的 Point 属性。您的 Edge 类将具有 ObservableCollection 类型的 Vertices 属性，该属性将为 2。

您的 ViewModel 将包含您将绑定(bind)到的所有边和所有顶点的列表。

您的 View 将 DataTemplate 您的边缘作为一条线。在 DataTemplate 中，您将钻取边上的两个顶点以获得线的任一端。 (您可以为顶点使用一个小椭圆。)

现在是数学:

private static Point[] Translate(Point[] points, double tX, double tY)
{
    return points.Select(p => new Point(p.X + tX, p.Y + tY)).ToArray();
}

private static Point[] Rotate(Point[] points, double theta)
{
    return points.Select(p =>
                        new Point(p.X * Math.Cos(theta) - p.Y * Math.Sin(theta),
                                    p.X * Math.Sin(theta) + p.Y * Math.Cos(theta)))
                    .ToArray();
}

public Point[] RotatePointsAroundPoint(Point[] points, Point origin, double theta)
{
    var tPoints = Translate(points, -origin.X, -origin.Y);
    tPoints = Rotate(tPoints, theta);
    return Translate(tPoints, origin.X, origin.Y);
}

public void RotateGraph(Vertex[] vertices, Point origin, double theta)
{
    var points = vertices.Select(v => v.Point).ToArray();

    var tPoints = RotatePointsAroundPoint(points, origin, theta);

    for(var i = 0; i < vertices.Length; i++)
        vertices[i].Point = tPoints[i]; 
}

有了这个，您只需确定原点和旋转度数。在 Vertex.Point 上调用 setter 后，NotifyPropertyChanged 事件将更新 View。