You can use the line-sweep algorithm with this problem.
In this case, the vertical lines are added or removed from the set of lines to take into account when moving up. Both start & end points o the lines are added to the sweepset and the horizontal lines are added in order to a list.

- step 1: line is added to activeVertical
- step 2: second line added to activeVertical
- step 3: third line added to activeVertical (note: they are in order of X).
- step 4a: fourth line added to activeVertical
- step 4b: Horizontal line found, time to create a rectangle which does not
have any height
- step 5: second horizontal line found, time to check finish previous rectangle
etc.
Below the code (C#). Yuo can find more details on line sweep algorithm here: https://en.wikipedia.org/wiki/Sweep_line_algorithm
using System;
using System.Collections.Generic;
using System.Linq;
namespace tt
{
public class Point
{
public Point(double X, double Y)
{
this.X = X;
this.Y = Y;
}
public double X { get; set; }
public double Y { get; set; }
}
public class Line
{
public Point Start { get; set; }
public Point End { get; set; }
}
public class Rectangle
{
public Rectangle()
{ }
public Rectangle(Point BottomLeft, Point TopRight)
{
this.BottomLeft = BottomLeft;
this.TopRight = TopRight;
}
public Point BottomLeft { get; set; }
public Point TopRight { get; set; }
}
public class XComparer : IComparer<Line>
{
public int Compare(Line x, Line y)
{
return x.Start.X.CompareTo(y.Start.X);
}
}
public class Program
{
public static int GetMinIndex(List<Line> Lines, Line Horizontal)
{
var xComp = new XComparer();
int minIndex = Lines.BinarySearch(Horizontal, xComp);
if (minIndex < 0) minIndex = ~minIndex;
return minIndex;
}
public static int GetMaxIndex(List<Line> Lines, Line Horizontal)
{
var xComp = new XComparer();
int maxIndex = Lines.BinarySearch(new Line() { Start = Horizontal.End }, xComp);
if (maxIndex < 0) maxIndex = ~maxIndex - 1;
return maxIndex;
}
public static void Main()
{
List<Line> lines = new List<Line>();
lines.Add(new Line() { Start = new Point(0.5, 12.5), End = new Point(10, 12.5) });
lines.Add(new Line() { Start = new Point(2.5, 9.5), End = new Point(15.8, 9.5) });
lines.Add(new Line() { Start = new Point(6, 8.5), End = new Point(16.3, 8.5) });
lines.Add(new Line() { Start = new Point(3.5, 8.5), End = new Point(3.5, 12.5) });
lines.Add(new Line() { Start = new Point(7, 4.2), End = new Point(7, 13.8) });
lines.Add(new Line() { Start = new Point(10, 5.8), End = new Point(10, 14.2) });
lines.Add(new Line() { Start = new Point(15.6, 0), End = new Point(15.6, 16) });
lines.Add(new Line() { Start = new Point(1.6, 20), End = new Point(15.6, 20) });
var activeVertical = new List<Line>();
SortedList<double, List<Line>> sweepSet = new SortedList<double, List<Line>>();
foreach (Line oneLine in lines.Where(x => x.Start.X == x.End.X))
{
if (!sweepSet.ContainsKey(oneLine.Start.Y)) sweepSet.Add(oneLine.Start.Y, new List<Line>());
sweepSet[oneLine.Start.Y].Add(oneLine);
if (!sweepSet.ContainsKey(oneLine.End.Y)) sweepSet.Add(oneLine.End.Y, new List<Line>());
sweepSet[oneLine.End.Y].Add(oneLine);
}
var linesHorizontal = lines.Where(x => x.Start.Y == x.End.Y).OrderBy(x => x.Start.Y).ToList();
List<Rectangle> rectangles = new List<Rectangle>();
List<Rectangle> completedRectangles = new List<Rectangle>();
var xComp = new XComparer();
int horIndex = 0;
int sweepIndex = 0;
while (sweepIndex < sweepSet.Count)
{
double y = Math.Min(sweepSet.Keys[sweepIndex], linesHorizontal[horIndex].Start.Y);
double verValue = linesHorizontal[horIndex].Start.Y;
if (sweepSet.ContainsKey(y))
{
foreach (Line oneLine in sweepSet[y].Where(x => x.Start.Y == y))
{
int index = activeVertical.BinarySearch(oneLine, xComp);
if (index < 0) index = ~index;
activeVertical.Insert(index, oneLine);
}
}
if (y == verValue)
{
int minIndex = GetMinIndex(activeVertical, linesHorizontal[horIndex]);
int maxIndex = GetMaxIndex(activeVertical, linesHorizontal[horIndex]);
if (minIndex != maxIndex && minIndex < activeVertical.Count && maxIndex < activeVertical.Count)
{
double minX = activeVertical[minIndex].Start.X;
double maxX = activeVertical[maxIndex].Start.X;
foreach (Rectangle oneRec in rectangles)
{
if (minX > oneRec.BottomLeft.X) oneRec.BottomLeft.X = minX;
if (maxX < oneRec.TopRight.X) oneRec.TopRight.X = maxX;
oneRec.TopRight.Y = verValue;
}
completedRectangles.AddRange(rectangles);
rectangles.Clear();
rectangles.Add(new Rectangle(new Point(activeVertical[minIndex].Start.X, verValue), new Point(activeVertical[maxIndex].Start.X, verValue)));
}
else rectangles.Clear();
}
if (sweepSet.ContainsKey(y))
{
foreach (Line oneLine in sweepSet[y].Where(x => x.End.Y == y))
{
activeVertical.Remove(oneLine);
}
}
if (y >= verValue)
{
horIndex++;
if (horIndex == linesHorizontal.Count) break;
if (y == sweepSet.Keys[sweepIndex]) sweepIndex++;
}
else
{
sweepIndex++;
}
}
}
}
}