如何构造这个二维几何星座的二元图

Question

考虑到 R 中的一些 x0 和 R^2 中的非水平随机线段不相交且成对的端点不共享相同的 y 值，我想（有效地）构造一个满足以下条件的二元图：

• 根是 x 区域（其端点之间的 x 间隔）包含 x0 的最上面的线段
• 每个线段最多有 2 个子线段，其中一个子线段（黑色）是从父线段的下端点到 x 轴绘制垂直线时第一个出现的线段
• 类似地，另一个孩子（蓝色）是我们在父线段的上端点之后得到的线段

为了便于说明，左侧是段 S1、...、S7，右侧是相应的树，其上端点子项标记为蓝色 线段和图表

我们显然必须以智能的方式对给定的段/端点进行排序，以便我们可以构建树，而无需天真地检查每个段是否是潜在的子段。 我们必须在 y 坐标之后以某种方式进行区分，因为端点比我们正在考虑的线段的两个端点都更高的线段不能是子线段。另外，如果两个线段端点之间的 x 坐标间隔不重叠，则它们无法在我们的图中连接。 由于我们不能同时在 x 和 y 之后进行排序，这可能表明我们需要两次（或更多）单独的排序。 进一步观察：如果一个段的下端点低于父段的端点，则该段只能是下端的子段。

虽然我付出了一些思考，但我似乎无法取得进一步的进展。是否有一些标准可以让我在有效的时间内构建我正在寻找的图表？

Answer 1

IIUC，这是一个带有 shapely/networkx 的命题。基本上，它首先定义一些自定义辅助函数来查找子行（如果有）：

YMIN, YMAX = list(zip(*[l.bounds[1::2] for l in lines]))

def make_vline(x):
    return LineString([(x, min(YMIN)), (x, max(YMAX))])

def get_ep(l):
    return sorted([(p.x, p.y) for p in l.boundary.geoms], key=lambda x: x[1])

def get_centro(l):
    return round(l.centroid.x, 2), round(l.centroid.y, 2)

在这里，我们创建一个边列表来准备图的构建：

def look_below(p):
    p = Point(p)
    vline = make_vline(p.x)
    ls = [l for l in lines if vline.intersects(l) and not l.touches(p)]
    distances = {}
    for l in ls:
        inter_p = vline.intersection(l)
        distances[l] = p.distance(inter_p)
    if distances:
        return next(iter(min(distances.items(), key=lambda x: x[1])), None)


edges = []
for l in lines:
    low, up = get_ep(l)
    if look_below(up):
        edges.append(
            [
                get_centro(l),
                get_centro(look_below(up)),
                {"color": "blue"},
            ]
        )

    if look_below(low):
        edges.append(
            [
                get_centro(l),
                get_centro(look_below(low)),
                {"color": "black"},
            ]
        )

最后，我们构建多图：

import networkx as nx

G = nx.MultiGraph()
G.add_edges_from(edges)

nx.set_node_attributes(
    G, {get_centro(l): {"name": f"S{i}"} for i, l in enumerate(lines, 1)}
)

剧情：