从行集合中查找链的算法

Question

如果两条线有一个共同端点，则它们属于同一条链。例如，定义为 (0, 0)-(Rnd, Rnd) 的 10 条线是一个有效链，因为它们都有一个共同的端点。

我开发的算法在一些幸运的情况下非常快，在其他情况下非常慢。对于 10,000 行，它可能需要几秒到几个小时。

我正在寻找加快速度的建议。

链是由这样的循环创建的:

For Each Line in Lines
  If Chain.HasPointInCommonWith(Line) Then
    Chain.Add Line
    Lines.Remove Line
  End If
Next Line

为了避免多次运行测试，我对所有关于它们的 XMin 的行进行了排序，并在寻找曲线的循环中添加了这个测试:

If Line.XMin > Chain.XMax Then Exit For

当线条代表许多矩形(一个在另一个右侧)时，此测试效果很好，但如果它们是许多矩形，一个在另一个上方，则无济于事。

Answer 1

将所有线的端点放在线列表的网格中怎么样？然后您只需遍历您的网格，其中包含两行以上的任何列表都是匹配项。

    //Build the list
    For Each Line in Lines
      grid[line.ymin][line.xmin].add(line)
      grid[line.ymax][line.xmax].add(line)
    Next Line

    //find the chains
    For current_x and current_y in grid
      if(grid[current_x][current_y].size() != 1)
        continue
      //start a new chain
      line = grid[current_x][current_y][0]
      chain.add(line)
      grid[current_y][current_x][0].remove(line)
      other_endpoint = line.other_endpoint(current_x, current_y)
      grid[other_endpoint.y][other_endpoint.x].remove(line)
      while(grid[other_endpoint.y][other_endpoint.x].size() >= 1)
        line = grid[other_endpoint.y][other_endpoint.x][0]
        chain.add(line)
        grid[other_endpoint.y][other_endpoint.x][0].remove(line)
        other_endpoint = line.other_endpoint(other_endpoint.y,other_endpoint.x)

第二个循环在网格单元中找到一个单独的线段，然后检查该线另一端的网格(在此过程中将其自身从网格中移除)。如果该位置有另一条线，则将其添加到链中并检查该线的另一个端点，依此类推，直到没有其他线可添加到该链中。然后你继续搜索下一个链开始。
这不会捕获闭环(例如 A -> B -> C -> A)，因为检查 grid[current_x][current_y].size() != 1 对每一行都会失败这里。如果您不关心保留这些，您可以简单地完全删除检查，否则您将在没有检查的情况下进行第二次检查。

此外，如果这占用的内存量太高(现在内存量取决于你的行所在的范围而不是行数)那么你可以扩大每个单元格的大小以容纳一个范围每个单元格的位置。您现在必须遍历每个单元格的线条，以判断它们是否共享端点，但理想情况下，每个单元格都将包含所有线条的一个非常小的子集，因此这些循环不会太糟糕而无法处理。