(SQL) прямоугольники
От: Yagg Россия  
Дата: 26.12.19 13:18
Оценка: 5 (1)
Имеется множество прямоугольников, заданных координатами углов:
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 — время и оно зациклено.
Отредактировано 26.12.2019 15:56 Yagg . Предыдущая версия . Еще …
Отредактировано 26.12.2019 15:09 Yagg . Предыдущая версия .
Re: (SQL) прямоугольники
От: wildwind Россия  
Дата: 26.12.19 19:37
Оценка:
Здравствуйте, Yagg, Вы писали:

Y>Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.


Вот это "X приоритетнее" непонятно, уточни.
И может не стоит ставить условия для единственности решения, а получить их все?

И еще нужно уточнить, каким диалектом SQL можно пользоваться и какими vendor-specific фичами.
Re: (SQL) прямоугольники
От: Слава  
Дата: 26.12.19 20:06
Оценка:
Здравствуйте, Yagg, Вы писали:

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


Я бы шёл в сторону всяких гео-расширений для MS SQL и постгреса.
Re[2]: (SQL) прямоугольники
От: Yagg Россия  
Дата: 26.12.19 20:57
Оценка:
Здравствуйте, wildwind, Вы писали:

Y>>Решений несколько, поэтому считаем, что X приоритетнее и количество прямоугольников в результате должно быть минимально.


W>Вот это "X приоритетнее" непонятно, уточни.


Прямоугольник сверху — это что на входе. Разноцветные — это два минимальных решения, результат. Cлева с приоритетом по X, справа по Y.

W>И может не стоит ставить условия для единственности решения, а получить их все?

Количество прямоугольников в результате вырастет.

W>И еще нужно уточнить, каким диалектом SQL можно пользоваться и какими vendor-specific фичами.

Думаешь ANSI не достаточно для решения? Ну ок, пусть будет T-SQL.
Re[3]: (SQL) прямоугольники
От: wildwind Россия  
Дата: 27.12.19 07:32
Оценка:
Здравствуйте, Yagg, Вы писали:

Y>Image: rect_split.png

Y>Прямоугольник сверху — это что на входе. Разноцветные — это два минимальных решения, результат. Cлева с приоритетом по X, справа по Y.

А другие минимальные решения чем хуже? Это, например, какой "приоритет"?



А это решение подходит?



Если нет, нужно сформулировать почему.

По-моему нужно требовать либо "все", либо "любое", из минимальных. А среди них оценивать эффективность.

Y>Думаешь ANSI не достаточно для решения? Ну ок, пусть будет T-SQL.

ANSI тоже разный бывает.
Отредактировано 27.12.2019 7:33 wildwind . Предыдущая версия .
Re[4]: (SQL) прямоугольники
От: rg45 СССР  
Дата: 27.12.19 12:16
Оценка:
Здравствуйте, wildwind, Вы писали:

W>А другие минимальные решения чем хуже? Это, например, какой "приоритет"?

W>Image: text887.png

Это решение ничем не хуже. Просто в условии задачи содержится спойлер к красивому и эффективному решению. Которое заключается в том, что мы применяем определенный алгоритм дважды — сналчала по оси X, затем по оси Y.

W>А это решение подходит?

W>Image: text888.png

А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие. В этой задаче прямоугольники нужно только разбивать, но не объединять.
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 27.12.2019 12:22 rg45 . Предыдущая версия . Еще …
Отредактировано 27.12.2019 12:22 rg45 . Предыдущая версия .
Отредактировано 27.12.2019 12:19 rg45 . Предыдущая версия .
Отредактировано 27.12.2019 12:19 rg45 . Предыдущая версия .
Re[5]: (SQL) прямоугольники
От: wildwind Россия  
Дата: 27.12.19 12:56
Оценка:
Здравствуйте, rg45, Вы писали:

R>А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие.


Как и изначально существовавший прямоугольник (0, 0, 10, 10) во всех решениях, это ничего?

R>В этой задаче прямоугольники нужно только разбивать, но не объединять.


Если не объединять, количество прямоугольников не будет минимальным.
Re[6]: (SQL) прямоугольники
От: rg45 СССР  
Дата: 27.12.19 13:27
Оценка:
Здравствуйте, wildwind, Вы писали:

R>>А это решние не подходит, потому что изначально существовавший прямоугольник (1, 1, 5, 5) канул в небытие.

W>Как и изначально существовавший прямоугольник (0, 0, 10, 10) во всех решениях, это ничего?

Так да не так. Границы этого прямоугольника остались на месте, а в твоем решении они исчезли.

W>Если не объединять, количество прямоугольников не будет минимальным.


Минимальным в условиях задачи, естественно. Если бы можно было объединять, то в данном конкретном случае просто остался бы один большой прямоугольник (0, 0, 10, 10).
--
Не можешь достичь желаемого — пожелай достигнутого.
Re[7]: (SQL) прямоугольники
От: wildwind Россия  
Дата: 27.12.19 14:24
Оценка:
Здравствуйте, rg45, Вы писали:

W>>Если не объединять, количество прямоугольников не будет минимальным.

R>Минимальным в условиях задачи, естественно. Если бы можно было объединять, то в данном конкретном случае просто остался бы один большой прямоугольник (0, 0, 10, 10).

Ну о том и речь, что условия не четкие, их нужно лучше формализовать. Особенно если рассмотреть более сложные случаи. Например:



Тут решений уже больше. Какие предпочесть?
Re[8]: (SQL) прямоугольники
От: rg45 СССР  
Дата: 27.12.19 14:41
Оценка:
Здравствуйте, wildwind, Вы писали:

W>Ну о том и речь, что условия не четкие, их нужно лучше формализовать. Особенно если рассмотреть более сложные случаи. Например:


W>Image: Rects3.png


W>Тут решений уже больше. Какие предпочесть?


Ну если отталкиваться от оригинальной формулировки, то следует от каждой вершины, находящейся внутри желтого прямоугольника (таких вершин три) провести вертикальные отрезки вверх и вниз до первого пересечения с какой-либо стороной. После этого стереть все цвета, оставив одни лишь границы. Множество образовавшихся элементарных прямоугольников и будет решением. Доказательство минимальности полученного разбиения остается открытым вопросом

P.S. Одно я понял совершенно ясно: проводить новые линии можно, стирать существующие нельзя.

P.P.S А, ну и еще одну вершину я пропустил — находящуюся внутри синего прямоугольника. От нее нужно провести вертикальную линию вниз, до пересечения с нижней стороной синего прямоугольника.
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 27.12.2019 14:57 rg45 . Предыдущая версия . Еще …
Отредактировано 27.12.2019 14:56 rg45 . Предыдущая версия .
Отредактировано 27.12.2019 14:49 rg45 . Предыдущая версия .
Re[4]: (SQL) прямоугольники
От: Yagg Россия  
Дата: 27.12.19 16:03
Оценка:
Здравствуйте, wildwind, Вы писали:

W>Image: text887.png


W>А это решение подходит?

Да. В принципе любое минимальное решение подходит. Но мне кажется, что так разбить будет сложнее.

W>Image: text888.png


W>Если нет, нужно сформулировать почему.

Нет. 3 пересекается сразу с двумя исходными.
Re: (SQL) прямоугольники
От: Yagg Россия  
Дата: 27.12.19 16:10
Оценка:
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 rects
delete 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
Re[5]: (SQL) прямоугольники
От: wildwind Россия  
Дата: 27.12.19 16:45
Оценка: :)
Здравствуйте, Yagg, Вы писали:

W>>Если нет, нужно сформулировать почему.

Y>Нет. 3 пересекается сразу с двумя исходными.

Как и в твоих решениях.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.