Имеется множество прямоугольников, заданных координатами углов:

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, 1, 5
5, 1, 5, 10
5, 0, 10, 10

Родилось по мотивам реальной задачи подбора ставок для контрактов, только у нас x1,x2 — даты, а y1,y2 — время и оно зациклено.

Имеется множество прямоугольников, заданных координатами углов:

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
5, 1, 5, 10
5, 0, 10, 10

Родилось по мотивам реальной задачи подбора ставок для контрактов, только у нас x1,x2 — даты, а y1,y2 — время и оно зациклено.