Имеется множество прямоугольников, заданных координатами углов:
create table rect(x1 int, y1 int, x2 int, y2 int)
Часть их них пересекаются. Нужно получить таблицу, в которой прямоугольники разбиты по линиям пересечений. Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.
Здравствуйте, Yagg, Вы писали:
Y>Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.
Вот это "X приоритетнее" непонятно, уточни.
И может не стоит ставить условия для единственности решения, а получить их все?
И еще нужно уточнить, каким диалектом SQL можно пользоваться и какими vendor-specific фичами.
Здравствуйте, Yagg, Вы писали:
Y>Родилось по мотивам реальной задачи подбора ставок для контрактов, только у нас x1,x2 — даты, а y1,y2 — время и оно зациклено.
Я бы шёл в сторону всяких гео-расширений для MS SQL и постгреса.
Здравствуйте, wildwind, Вы писали:
Y>>Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.
W>Вот это "X приоритетнее" непонятно, уточни.
Прямоугольник сверху — это что на входе. Разноцветные — это два минимальных решения, результат. Cлева с приоритетом по X, справа по Y.
W>И может не стоит ставить условия для единственности решения, а получить их все?
Количество прямоугольников в результате вырастет.
W>И еще нужно уточнить, каким диалектом SQL можно пользоваться и какими vendor-specific фичами.
Думаешь ANSI не достаточно для решения? Ну ок, пусть будет T-SQL.
Здравствуйте, Yagg, Вы писали:
Y>Image: rect_split.png Y>Прямоугольник сверху — это что на входе. Разноцветные — это два минимальных решения, результат. Cлева с приоритетом по X, справа по Y.
А другие минимальные решения чем хуже? Это, например, какой "приоритет"?
А это решение подходит?
Если нет, нужно сформулировать почему.
По-моему нужно требовать либо "все", либо "любое", из минимальных. А среди них оценивать эффективность.
Y>Думаешь ANSI не достаточно для решения? Ну ок, пусть будет T-SQL.
ANSI тоже разный бывает.
Здравствуйте, wildwind, Вы писали:
W>А другие минимальные решения чем хуже? Это, например, какой "приоритет"? W>Image: text887.png
Это решение ничем не хуже. Просто в условии задачи содержится спойлер к красивому и эффективному решению. Которое заключается в том, что мы применяем определенный алгоритм дважды — сналчала по оси X, затем по оси Y.
W>А это решение подходит? W>Image: text888.png
А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие. В этой задаче прямоугольники нужно только разбивать, но не объединять.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие.
Как и изначально существовавший прямоугольник (0, 0, 10, 10) во всех решениях, это ничего?
R>В этой задаче прямоугольники нужно только разбивать, но не объединять.
Если не объединять, количество прямоугольников не будет минимальным.
Здравствуйте, wildwind, Вы писали:
R>>А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие. W>Как и изначально существовавший прямоугольник (0, 0, 10, 10) во всех решениях, это ничего?
Так да не так. Границы этого прямоугольника остались на месте, а в твоем решении они исчезли.
W>Если не объединять, количество прямоугольников не будет минимальным.
Минимальным в условиях задачи, естественно. Если бы можно было объединять, то в данном конкретном случае просто остался бы один большой прямоугольник (0, 0, 10, 10).
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
W>>Если не объединять, количество прямоугольников не будет минимальным. R>Минимальным в условиях задачи, естественно. Если бы можно было объединять, то в данном конкретном случае просто остался бы один большой прямоугольник (0, 0, 10, 10).
Ну о том и речь, что условия не четкие, их нужно лучше формализовать. Особенно если рассмотреть более сложные случаи. Например:
Здравствуйте, wildwind, Вы писали:
W>Ну о том и речь, что условия не четкие, их нужно лучше формализовать. Особенно если рассмотреть более сложные случаи. Например:
W>Image: Rects3.png
W>Тут решений уже больше. Какие предпочесть?
Ну если отталкиваться от оригинальной формулировки, то следует от каждой вершины, находящейся внутри желтого прямоугольника (таких вершин три) провести вертикальные отрезки вверх и вниз до первого пересечения с какой-либо стороной. После этого стереть все цвета, оставив одни лишь границы. Множество образовавшихся элементарных прямоугольников и будет решением. Доказательство минимальности полученного разбиения остается открытым вопросом
P.S. Одно я понял совершенно ясно: проводить новые линии можно, стирать существующие нельзя.
P.P.S А, ну и еще одну вершину я пропустил — находящуюся внутри синего прямоугольника. От нее нужно провести вертикальную линию вниз, до пересечения с нижней стороной синего прямоугольника.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, wildwind, Вы писали:
W>Image: text887.png
W>А это решение подходит?
Да. В принципе любое минимальное решение подходит. Но мне кажется, что так разбить будет сложнее.
W>Image: text888.png
W>Если нет, нужно сформулировать почему.
Нет. 3 пересекается сразу с двумя исходными.
Y>Имеется множество прямоугольников, заданных координатами углов: Y>Нужно получить таблицу, в которой прямоугольники разбиты по линиям пересечений.
Если что, вот моё решение, но не уверен, что пройдёт все тесты:
declare @rect table(id int, x1 int, y1 int, x2 int, y2 int, l int)
declare @result table(x1 int, y1 int, x2 int, y2 int)
insert into @rect(id, x1, y1, x2, y2, l)
values (1, 0, 0, 10, 10, 1),
(2, 1, 1, 5, 5, 2)
;with
x as-- all Xs
(
select x1 as x
from @rect
union
select x2
from @rect
),
xs as-- Xs pairs
(
select
row_number() over (order by x) n,
lag(x, 1, null) over(order by x) as x1, x as x2, (x+lag(x, 1, null) over(order by x))/2.0 m
from x
),
xy as-- all Ys for each pair of Xs
(
select x.n, r.y1 as y
from xs x
join @rect r on r.x1<=m and m<=r.x2
union
select x.n, r.y2
from xs x
join @rect r on r.x1<=m and m<=r.x2
),
res as-- pair of Ys for each pair of Xs as a result rectangles
(
select x.x1, lag(y, 1, null) over(partition by xy.n order by y) y1,
x.x2, y as y2
from xy xy
join xs x on x.n= xy.n
)
insert into @result(x1, y1, x2, y2)
select x1, y1, x2, y2
from res r
where y1 is not null-- delete new rectangles that placed out of source rectsdelete r from @result r
where not exists(select 1 from @rect rs where rs.x1 < (r.x2+r.x1)/2.0 and (r.x2+r.x1)/2.0< rs.x2 and rs.y1 < (r.y2+r.y1)/2.0 and (r.y2+r.y1)/2.0 < rs.y2)
select * from @result