algorithm - 从线集合中查找链的算法

如果两条线有一个共同的端点，则它们属于同一个链例如，定义为（0，0）-（rnd，rnd）的10行是一个有效链，因为它们都有一个共同的端点。
我开发的算法在一些幸运的情况下非常快，在其他情况下非常慢。有10000条线路，几秒钟到几小时之间就可以完成。
我在寻求加快速度的建议。
这些链是由这样的循环创建的：

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

当直线表示多个矩形（一个在另一个的右边）时，这个测试工作得很好，但如果它们是多个矩形（一个在另一个的上面），则没有帮助。

最佳答案

把所有直线的端点放在一个直线列表的网格中怎么样然后您只需遍历您的网格，并且任何列表中有两行以上的内容都是匹配的。

    //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），因为这里的每一行的checkgrid[current_x][current_y].size() != 1将失败。如果你不在乎保存这些，你可以简单地完全删除支票，否则你做了第二次没有检查通过。
此外，如果占用的内存量太大（现在的内存量取决于行所处的范围，而不再取决于行的数量），则可以扩大每个单元格的大小，以保持每个单元格的位置范围现在必须循环遍历每个单元格的行，以判断它们是否共享端点，但理想情况下，每个单元格将拥有所有行的一个非常小的子集，因此这些循环不会太差，无法处理。

关于algorithm - 从线集合中查找链的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17150358/