Имеется множество прямоугольников, заданных координатами углов:
create table rect(x1 int, y1 int, x2 int, y2 int)
Часть их них пересекаются. Нужно получить таблицу, в которой прямоугольники разбиты по линиям пересечений. Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.
Пример.
На входе:
0, 0, 10, 10
1, 1, 5, 5
На выходе:
1, 1, 5, 5
0, 0, 1, 10
1, 0, 5, 1
1, 5, 5, 10
5, 0, 10, 10
Родилось по мотивам реальной задачи подбора ставок для контрактов, только у нас x1,x2 — даты, а y1,y2 — время и оно зациклено.