Here is my suggested approach:
- Clean both lists so there aren't any fully contained 'small' lines.
- Pick any line.
- Take all the lines that touch (intersect) this line.
- For each of these lines take all the lines that touch them.
- Continue until you can't find any more touching lines.
- You now have a group.
- Pick a line from those that remain and repeat until there are no more lines left.
Code:
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);
}
}
}
Add this method to Line
public bool Intersects(Line other)
{
// Whether this line intersects the other line or not.
// I'll leave the implementation up to you.
}
Notes:
If this code runs too slowly you might need to scan horizontally, picking up connected lines as you go. Might also be worth looking at this.
Specialised:
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;
}
This assumes no lines overlap as it doesn't check if horizontal lines touch other horizontal lines (same for vertical).
You can probably remove the if-else. That's just there in case there are vertical lines not attached to horizontal lines.
