查找地圖中最大的連接線

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 
    } 
} 

一旦做到這一點，你只需要遍歷你找到的對象並確定最大的對象（不過你確定）。