通过视线（直线）将节点连接到邻居

Question

我有一个类似于迷宫的结构，但有更多的开放空间。对于结构中的每个节点，我想找到它的所有“邻居”（如果节点在视线范围内，即没有墙壁阻挡它们之间的直线，则节点就是邻居）。

这里有一张小图片可以帮助解释我的意思。

• 黑线是墙。
• 红点是节点。
• 蓝线是连接邻居的线（注意没有蓝线与黑线交叉）。

我目前正在实施一种非常幼稚且成本极高的暴力方法。在其中我检查节点的每个组合是否与任何迷宫墙（存储在“边缘”中的墙）相交。

for n1 in nodes:
    for n2 in nodes:
        if not intersect(n1, n2, edges):
            n1.neighbours.append(n2)
            n2.neighbours.append(n1)

这对于像上面的例子这样的小型结构来说效果很好。但我希望它能够扩展到更大的结构。

所以我的问题是是否有任何方法可以更快/更有效地找到每个节点的所有邻居。

干杯:)

Answer 1

您可能想阅读蒙日关于射影几何的书:)

让我们在每个节点周围使用遮挡屏幕，正方形在计算上很容易，圆形需要更多的数学运算。屏幕是隐藏节点空间的边的集合。 screen.occlude() 方法将您的墙壁之一作为输入，计算屏幕上的投影，然后通过添加边缘或延伸边缘来扩展遮挡。

结果是遮挡边缘比墙壁少（很多？）。 然后我们反转遮挡边和节点上的循环以获得时间。请注意，方法 .remove_occlusion_by() 仅循环遍历剩余的候选邻居，这是一个收缩集合。我猜增益是从 O(n^2) 到 O(n*log(n))

您还可以在正方形的每一侧有 2 个点，它们是该方向上遮挡的极端，可能是虚拟正方形的角点。 4 个遮挡锥之外的每个节点都是可见的。不确定这会赢得时间。

for n1 in nodes:
    n1.occlusion = a_1_by_1_square_occlusion( centre = n1 )
    for e in edges:
        n1.occlusion.occlude( e )
    n1.neighbours = nodes - n1                # your choice
    n1.neigbours.remove_connected_walls( n1 ) # your choice
    for o in n1.occlusion.edges:
        n1.neighbours.remove_occluded_by( o )