1

如果两条线有一个共同的端点，则它们属于同一条链。例如，定义为 (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

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

4

3 回答 3

1

将数据建模为图形，其中线的每个端点都是一个顶点，每条线是连接两个顶点的边。

然后，您可以使用任何标准的图遍历算法来访问连接到给定顶点的所有顶点。

编辑

定义图形后，选择一个顶点并执行 DFS 以构建连接顶点的树。

如果任何顶点不在此树中，则选择一个并执行另一个 DFS 以构建另一棵树。

重复直到所有顶点都被分配给一棵树。

每棵树定义一个“链”。

于 2013-06-17T14:50:44.257 回答
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此处的每一行的检查都将失败。如果您不关心保留这些，您可以简单地完全删除检查，否则您在没有检查的情况下进行第二次通过。

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

于 2013-06-17T18:27:43.743 回答
0

  1. M从Pointto创建一个空的哈希映射List<Line>

  2. 对于 each ，在andLine L插入空列表，如果它们尚不存在，则执行andM[L.A]M[L.B]M[L.A].Add(L)M[L.B].Add(L)

  3. M现在是从图节点（点）到事件图边（线）的映射

  4. 在此图上运行深度优先搜索M以发现所有链

于 2013-06-17T17:34:12.027 回答