algorithm - 在地图中找到最大的连接线

Question

我有一张详细的地图（线条、矩形、圆圈）。

我想处理这些线并找出哪些是连接的。

例子：

{   
    Line1 : start =  x = 1  y = 2 , end =  x = 1  y = 10
    Line2 : start =  x = 5  y = 5 , end =  x = 5  y = 15
    Line3 : start =  x = 2  y = 4 , end =  x = 2  y = 8
    Line4 : start =  x = 2  y = 8 , end =  x = 1  y = 2
    ...
    ...
    ...
}

有些线是垂直的，不完全连接！

我为此编写了一个递归算法，但找不到所有这些（垂直线），我该怎么办？

Answer 1

未经测试，但我想你会想要这样的东西：

首先，您需要一些列表或字典，以识别特定点的所有连接。此外，您还需要一个列表来收集您已处理的积分：

connections = dictionary of coordinate lists indexed by coordinates

for each line in lines {
    add the end of line to connections[start of line]
    add the start of line to connections[end of line]
}

used_points = empty list of points

实际的算法应该很简单：

function add_point_function(point) {
    if point is in used_points {
        return
    }

    add point to current_object
    add point to used_points
    for each next_point in connections[point] {
        add_point_function(next_point)
    }
}

for each point being an index in connections {
    current_object = empty list of points
    call add_point_function
    if current_object has points {
        // you've got an object here so you might want to save it
    }
}

完成此操作后，您只需遍历找到的对象并确定最大的对象（无论如何确定）。