1

一个简单的线类被定义为两个包含开始和结束坐标的 PointF 成员：

public class Line    {
    PointF s, e;
}

我有两个列表，其中包含出现在绘图画布上并形成一个或多个表格的所有水平和垂直线。

List<Line> AllHorizontalLines;
List<Line> AllVerticalLines;

我需要对这些行进行分组，以便将属于一个表的行捕获在一个组中，因此分组函数将具有如下签名：

List<List<Line>> GroupLines(List<Line> hor, List<Line> ver)
{ 

}

为简单起见，我们假设页面上只有“简单”表，即没有嵌套表。但是可以合并单元格，因此我们必须忽略小于父表全高的小的水平和垂直线。为进一步简单起见，假设两个输入列表都已排序（Y 轴上的水平线和 X 轴上的垂直线）。

有没有已知的算法来解决这个问题？或者谁能​​帮我设计一个？

4

3 回答 3

1

以下似乎有效：

  • 设置一个字典，将边界矩形映射到每个矩形中的线列表。
  • 对于两个输入列表中的每一行（我们不关心方向）
    • 在线外创建一个边界矩形
    • 检查线是否穿过任何现有的边界矩形。
      • 如果是这样，合并这些矩形中的线，添加当前线，删除触摸的矩形，计算一个新的边界矩形，然后再次检查。
      • 否则，将此新矩形添加到字典中并删除旧矩形。
  • 返回每个矩形的线列表。

这是我得到的代码：

public static IEnumerable<IEnumerable<Line>> GroupLines(IEnumerable<Line> lines)
{
    var grouped = new Dictionary<Rectangle, IEnumerable<Line>>();

    foreach (var line in lines)
    {
        var boundedLines = new List<Line>(new[] { line });
        IEnumerable<Rectangle> crossedRectangles;
        var boundingRectangle = CalculateRectangle(boundedLines);
        while (
            (crossedRectangles = grouped.Keys
                .Where(r => Crosses(boundingRectangle, r))
                .ToList()
            ).Any())
        {
            foreach (var crossedRectangle in crossedRectangles)
            {
                boundedLines.AddRange(grouped[crossedRectangle]);
                grouped.Remove(crossedRectangle);
            }
            boundingRectangle = CalculateRectangle(boundedLines);
        }
        grouped.Add(boundingRectangle, boundedLines);
    }
    return grouped.Values;
}

public static bool Crosses(Rectangle r1, Rectangle r2)
{
    return !(r2.Left > r1.Right ||
        r2.Right < r1.Left ||
        r2.Top > r1.Bottom ||
        r2.Bottom < r1.Top);
}

public static Rectangle CalculateRectangle(IEnumerable<Line> lines)
{
    Rectangle rtn = new Rectangle
    {
        Left = int.MaxValue,
        Right = int.MinValue,
        Top = int.MaxValue,
        Bottom = int.MinValue
    };

    foreach (var line in lines)
    {
        if (line.P1.X < rtn.Left) rtn.Left = line.P1.X;
        if (line.P2.X < rtn.Left) rtn.Left = line.P2.X;
        if (line.P1.X > rtn.Right) rtn.Right = line.P1.X;
        if (line.P2.X > rtn.Right) rtn.Right = line.P2.X;
        if (line.P1.Y < rtn.Top) rtn.Top = line.P1.Y;
        if (line.P2.Y < rtn.Top) rtn.Top = line.P2.Y;
        if (line.P1.Y > rtn.Bottom) rtn.Bottom = line.P1.Y;
        if (line.P2.Y > rtn.Bottom) rtn.Bottom = line.P2.Y;
    }

    return rtn;
}

我拼凑的 WinForms 应用程序

于 2012-09-14T12:31:39.433 回答
1

这是我建议的方法：

  • 清理这两个列表，这样就没有任何完全包含的“小”行。
  • 选择任何一条线。
  • 取所有接触（相交）这条线的线。
  • 对于这些线中的每一条，取所有接触它们的线。
  • 继续，直到你找不到更多的接触线。
  • 你现在有一个组。
  • 从剩下的行中选择一条并重复，直到没有更多的行。

代码：

public static IEnumerable<IEnumerable<Line>> Group(IEnumerable<Line> horizontalLines, IEnumerable<Line> verticalLines)
{
  // Clean the input lists here. I'll leave the implementation up to you.

  var ungroupedLines = new HashSet<Line>(horizontalLines.Concat(verticalLines));
  var groupedLines = new List<List<Line>>();

  while (ungroupedLines.Count > 0)
  {
    var group = new List<Line>();
    var unprocessedLines = new HashSet<Line>();
    unprocessedLines.Add(ungroupedLines.TakeFirst());

    while (unprocessedLines.Count > 0)
    {
      var line = unprocessedLines.TakeFirst();
      group.Add(line);
      unprocessedLines.AddRange(ungroupedLines.TakeIntersectingLines(line));
    }

    groupedLines.Add(group);
  }

  return groupedLines;
}

public static class GroupingExtensions
{
  public static T TakeFirst<T>(this HashSet<T> set)
  {
    var item = set.First();
    set.Remove(item);
    return item;
  }

  public static IEnumerable<Line> TakeIntersectingLines(this HashSet<Line> lines, Line line)
  {
    var intersectedLines = lines.Where(l => l.Intersects(line)).ToList();
    lines.RemoveRange(intersectedLines);
    return intersectedLines;
  }

  public static void RemoveRange<T>(this HashSet<T> set, IEnumerable<T> itemsToRemove)
  {
    foreach(var item in itemsToRemove)
    {
      set.Remove(item);
    }
  }

  public static void AddRange<T>(this HashSet<T> set, IEnumerable<T> itemsToAdd)
  {
    foreach(var item in itemsToAdd)
    {
      set.Add(item);
    }
  }
}

将此方法添加到 Line

public bool Intersects(Line other)
{
  // Whether this line intersects the other line or not.
  // I'll leave the implementation up to you.
}

笔记：

如果此代码运行速度太慢，您可能需要水平扫描，边走边拾取连接线。可能也值得一看。

专门：

public static IEnumerable<IEnumerable<Line>> Group(IEnumerable<Line> horizontalLines, IEnumerable<Line> verticalLines)
{
  // Clean the input lists here. I'll leave the implementation up to you.

  var ungroupedHorizontalLines = new HashSet<Line>(horizontalLines);
  var ungroupedVerticalLines = new HashSet<Line>(verticalLines);
  var groupedLines = new List<List<Line>>();

  while (ungroupedHorizontalLines.Count + ungroupedVerticalLines.Count > 0)
  {
    var group = new List<Line>();
    var unprocessedHorizontalLines = new HashSet<Line>();
    var unprocessedVerticalLines = new HashSet<Line>();

    if (ungroupedHorizontalLines.Count > 0)
    {
      unprocessedHorizontalLines.Add(ungroupedHorizontalLines.TakeFirst());
    }
    else
    {
      unprocessedVerticalLines.Add(ungroupedVerticalLines.TakeFirst());
    }

    while (unprocessedHorizontalLines.Count + unprocessedVerticalLines.Count > 0)
    {
      while (unprocessedHorizontalLines.Count > 0)
      {
        var line = unprocessedHorizontalLines.TakeFirst();
        group.Add(line);
                unprocessedVerticalLines.AddRange(ungroupedVerticalLines.TakeIntersectingLines(line));
      }
      while (unprocessedVerticalLines.Count > 0)
      {
        var line = unprocessedVerticalLines.TakeFirst();
        group.Add(line);
        unprocessedHorizontalLines.AddRange(ungroupedHorizontalLines.TakeIntersectingLines(line));
      }
    }
    groupedLines.Add(group);
  }

  return groupedLines;
}

这假设没有线重叠，因为它不检查水平线是否接触其他水平线（垂直相同）。

您可能可以删除 if-else。如果有垂直线未连接到水平线，那只是在那里。

于 2012-09-14T12:51:12.373 回答
0

好的。我终于自己设计了一个有效的算法。以下是任何未来读者的步骤。

  1. 定义一个大集合Tuple<List<Line>, List<Line>>。此集合中的每个元组将代表一个表（该表的所有水平和垂直线）。

  2. 查找所有垂直线在一端与水平线的起点相接触，而在另一端与另一水平线的起点相接触。这些将是每个表的最左边的行。

  3. 现在对于每个左行（称为 LV）：找到所有与 LV 具有相同起始和结束 Y 并因此属于同一个表的垂直线。将这些“姐妹”行添加到名为 MyVSisters 的列表中。

    湾。找到最右边的垂直姊妹线的 X 坐标（称为 RVX）。

    C。现在找到从 LV 的 X 延伸到 RVX 的所有水平线，并且它们的 Y 位于 LV 的 Y1 和 Y2 之间。将这些行添加到名为 MyHSisters 的集合中。

    d。将元组 MyHSisters 和 MyVSisters 添加到大集合中。

  4. 回归盛大收藏。

我还没有将其标记为答案。在决定哪一个是最佳答案之前，我将等待这两个家伙的响应并比较所有 3 个的性能和准确性。

于 2012-09-15T08:09:51.080 回答