これが私の提案するアプローチです：
- 完全に含まれる「小さい」行がないように、両方のリストを消去します。
- 任意の行を選択します。
- この線に接する (交差する) すべての線を取ります。
- これらの線のそれぞれについて、それらに接するすべての線を取ります。
- 触れる線がなくなるまで続けます。
- これでグループができました。
- 残っている行から 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 を削除できます。これは、水平線に接続されていない垂直線がある場合に備えてあります。
