ReSQL.ru
     
powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Очень сложная задача, выбрать отрезки
9 сообщений из 9, страница 1 из 1
Очень сложная задача, выбрать отрезки
    #39398515
PCContra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PCContra
Участник
Есть таблица с черными участками (см рисунок), например
black
x1 y127915
Есть таблица с зелеными участками
green
x2y213468101314
Задача - найти красные участки. Те, которые входят в черные за исключением зеленых.
Должно получится:
red
x3y3346710131415

Я пробовал сам решить задачу, через сортировку и выборку, пока не получилось. Смотрел геометрические типы в документации, есть lseg (отрезок), но нет такой операции как разности одного массива отрезков и массива других отрезков (как в нашем случае). (((
Как составить выборку? Задача практическая, не теоретическая.
Заранее благодарю за ответы!


--
Россия - отличная страна!
...
Рейтинг: 0 / 0
04.02.2017, 03:41
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39398527
Alexius
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexius
Участник
PCContra,

создаете массив из всех вершин (и черных и зеленых), сортируете его и сканируете последовательно. дальше просто отбираете те вершины, которые удовлетворяют условиям и формируете отрезки из них.

наверняка есть способ получше, это первое что приходит в голову.
...
Рейтинг: 0 / 0
04.02.2017, 08:20
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39398558
ursido
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ursido
Гость
PCContra,

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
WITH
black AS (
      SELECT 2 AS x, 7 AS y
UNION SELECT 9 AS x, 15 AS y),

green AS (
      SELECT 1 AS x, 3 AS y
UNION SELECT 4 AS x, 6 AS y
UNION SELECT 8 AS x, 10 AS y
UNION SELECT 13 AS x, 14 AS y)

SELECT g.y AS rx,
       CASE WHEN b.y < lead(g.x, 1, b.y) OVER (ORDER BY g.x) THEN b.y ELSE lead(g.x, 1, b.y) OVER (ORDER BY g.x) END AS ry
FROM black b
LEFT JOIN green g ON g.y > b.x
                 AND g.x < b.y
ORDER BY b.x, g.x
...
Рейтинг: 0 / 0
04.02.2017, 11:46
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39399179
Фотография Legushka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Legushka
Участник
PCContra, поэксперементировал с диапазонными типами данных:
Код: sql
1.
2.
3.
4.
5.
6.
7.
with black(x, y) as (values (2,	7), (9,	15)),
green(x, y) as (values (1, 3), (4, 6), (8, 10), (13, 14)),
point as (select unnest(array[x,y]) as p from black union select unnest(array[x,y]) as p from green order by 1), -- находим все точки отрезков
allrange as (select row_number() over() as id, int4range(lag(p, 1) over(), p+1) r from point order by p) -- нарезали весь отрезок на точки

select lower(r.r), upper(r.r)-1 from allrange r left join green g on int4range(g.x, g.y+1)*r.r @> r.r 
where g.x is null and r.id<>1

--исключили из всех отрезков отрезки встречающие в green
...
Рейтинг: 0 / 0
06.02.2017, 12:34
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39402774
freeman611
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
freeman611
Гость
не очень оптимально и красиво, но смысл такой:

CREATE OR REPLACE FUNCTION public.calc_red (
)
RETURNS TABLE (
x integer,
y integer
) AS
$body$
DECLARE
black_x integer[100];
black_y integer[100];
red_x integer[100];
red_y integer[100];
green_x integer[100];
green_y integer[100];
r record;
i integer;
j integer;
k integer;
im integer;
jm integer;
km integer;

BEGIN
i=0;
for r in
SELECT 2 AS x, 7 AS y
UNION
SELECT 9 AS x, 15 AS y
LOOP
black_x[i]=r.x;
black_y[i]=r.y;
i=i+1;
im=i;
END LOOP;
j=0;
for r in
SELECT 1 AS x, 3 AS y
UNION SELECT 4 AS x, 6 AS y
UNION SELECT 8 AS x, 10 AS y
UNION SELECT 13 AS x, 14 AS y
LOOP
green_x[j]=r.x;
green_y[j]=r.y;
j=j+1;
jm=j;
END LOOP;
i=0;
while (i>=0) and (i<im)
LOOP
k=1;
red_x[i]=black_x[i];
red_y[i]=black_y[i];
for j in 0..jm-1
LOOP
if (red_x[i]>=green_x[j]) and (red_y[i]<=green_y[j])--черный внутри зеленого, удаляем
then
k=0;
raise notice 'черный %..% внутри зеленого %..%, удаляем', red_x[i], red_y[i], green_x[i], green_y[i];
else
if (red_x[i]>=green_x[j]) and (red_x[i]<=green_y[j]) --зеленый занимает левую часть черного, урезаем черный слева
then
red_x[i]=green_y[j];
raise notice 'зеленый % % занимает левую часть черного % %, урезаем черный слева', green_x[i], green_y[i], red_x[i], red_y[i];
else
if (red_y[i]>=green_x[j]) and (red_y[i]<=green_y[j]) --зеленый занимает правую часть черного, урезаем черный справа
then
red_y[i]=green_x[j];
raise notice 'зеленый % % занимает правую часть черного % %, урезаем черный справа', green_x[i], green_y[i], red_x[i], red_y[i];
else
if (red_x[i]<=green_x[j]) and (red_y[i]>=green_y[j])
then
--зеленый внутри черного, делим черный пополам, левый оставляем, правый добавляем в конец черных
raise notice 'зеленый % % внутри черного % %, делим черный пополам, левый оставляем, правый добавляем в конец черных', green_x[i], green_y[i], red_x[i], red_y[i];
im=im+1;
black_x[im-1]=green_y[j];
black_y[im-1]=red_y[i];
red_y[i]=green_x[j];
end if;
end if;
end if;
end if;
END LOOP;
if (red_x[i]<>red_y[i]) and (k=1)
then
x=red_x[i];
y=red_y[i];
return next;
end if;
i:=i+1;
end loop;
return;
END;
$body$
LANGUAGE 'plpgsql'
VOLATILE
CALLED ON NULL INPUT
SECURITY INVOKER
COST 100 ROWS 1000;
...
Рейтинг: 0 / 0
11.02.2017, 20:46
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39402793
Lonepsycho
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lonepsycho
Участник
PCContra,

если правильно понял задачу:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
WITH black AS (
  SELECT  
    int8range(t.x, t.y, '[)') AS r
  FROM (
    VALUES (2, 7), (9, 15)
    ) AS t(x, y)
),
green AS (
  SELECT
    int8range(t.x, t.y, '[)') AS r
  FROM (
    VALUES (1, 3), (4, 6), (8, 10), (13, 14)
    ) AS t(x, y)
),
red AS (
  SELECT
    int8range(t.x, t.y, '[)') AS r
  FROM (
    VALUES (3, 4), (6, 7), (10, 13), (14, 15)
    ) AS t(x, y)
) 
SELECT
  lower(red.r),
  upper(red.r)
FROM
  black
  INNER JOIN
  red
  ON black.r && red.r
WHERE 
  NOT EXISTS (
    SELECT NULL
    FROM
      green
    WHERE
      red.r && green.r
  )
...
Рейтинг: 0 / 0
11.02.2017, 21:29
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39402794
Lonepsycho
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lonepsycho
Участник
PCContra,

перечитал. понял не правильно.
...
Рейтинг: 0 / 0
11.02.2017, 21:30
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39402818
freeman611
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
freeman611
Гость
упс, не добавил подсветку
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
CREATE OR REPLACE FUNCTION public.calc_red (
)
RETURNS TABLE (
  x integer,
  y integer
) AS
$body$
DECLARE
  black_x integer[100];
  black_y integer[100];
  red_x integer[100];
  red_y integer[100];
  green_x integer[100];
  green_y integer[100];
  r record;  
  i integer; 
  j integer;
  k integer;
  im integer;
  jm integer;
  km integer;
  
BEGIN
  i=0;
  for r in 
      SELECT 2 AS x, 7 AS y
      UNION 
	  SELECT 9 AS x, 15 AS y
  LOOP
    black_x[i]=r.x;
	black_y[i]=r.y;
    i=i+1;
	im=i;
  END LOOP;
  j=0;
  for r in
      SELECT 1 AS x, 3 AS y
      UNION SELECT 4 AS x, 6 AS y
      UNION SELECT 8 AS x, 10 AS y
      UNION SELECT 13 AS x, 14 AS y
  LOOP
    green_x[j]=r.x;
	green_y[j]=r.y;
    j=j+1;
	jm=j;
  END LOOP;
  i=0;
  while (i>=0) and (i<im)
  LOOP
    k=1;
	red_x[i]=black_x[i];
	red_y[i]=black_y[i];
    for j in 0..jm-1
    LOOP
	  if (red_x[i]>=green_x[j]) and (red_y[i]<=green_y[j])--черный внутри зеленого, удаляем
	    then
		  k=0;
		  raise notice 'черный %..% внутри зеленого %..%, удаляем', red_x[i], red_y[i], green_x[i], green_y[i];
		else 
		  if (red_x[i]>=green_x[j]) and (red_x[i]<=green_y[j]) --зеленый занимает левую часть черного, урезаем черный слева
		    then
			  red_x[i]=green_y[j];
			  raise notice 'зеленый % % занимает левую часть черного % %, урезаем черный слева', green_x[i], green_y[i], red_x[i], red_y[i];
			else
			  if (red_y[i]>=green_x[j]) and (red_y[i]<=green_y[j]) --зеленый занимает правую часть черного, урезаем черный справа
		        then 
				  red_y[i]=green_x[j];
				  raise notice 'зеленый % % занимает правую часть черного % %, урезаем черный справа', green_x[i], green_y[i], red_x[i], red_y[i];
				else				  
                  if (red_x[i]<=green_x[j]) and (red_y[i]>=green_y[j])
				    then
					  --зеленый внутри черного, делим черный пополам, левый оставляем, правый добавляем в конец черных
					  raise notice 'зеленый % % внутри черного % %, делим черный пополам, левый оставляем, правый добавляем в конец черных', green_x[i], green_y[i], red_x[i], red_y[i];
					  im=im+1;
					  black_x[im-1]=green_y[j];
					  black_y[im-1]=red_y[i];
					  red_y[i]=green_x[j];
				  end if;	  
			  end if;
	      end if;		  	     
	  end if;		    
	END LOOP;  
	if (red_x[i]<>red_y[i]) and (k=1)
	  then
	    x=red_x[i];
		y=red_y[i];
		return next;
	end if;
	i:=i+1;    
  end loop;	    	
  return;  
END;
$body$
LANGUAGE 'plpgsql'
VOLATILE
CALLED ON NULL INPUT
SECURITY INVOKER
COST 100 ROWS 1000;
...
Рейтинг: 0 / 0
11.02.2017, 22:16
| Ответить | Цитировать | Написать  
Очень сложная задача, выбрать отрезки
    #39402932
Lonepsycho
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lonepsycho
Участник
PCContra,

как вариант
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
WITH black AS (
  SELECT  
    int8range(t.x, t.y, '[)') AS r
  FROM (
    VALUES (2, 7), (9, 15)
    ) AS t(x, y)
),
green AS (
  SELECT
    int8range(t.x, t.y, '[)') AS r
  FROM (
    VALUES (1, 3), (4, 6), (8, 10), (13, 14)
    ) AS t(x, y)
),
not_green AS (
  SELECT
    int8range(t2.x, t2.y, '[)') AS r
  FROM (
    SELECT
      upper(green.r) AS x,
      COALESCE(
        lower(lead(green.r) OVER w),
        (
          SELECT 
            max(upper(black.r))
          FROM
            black
        )
      ) AS y
    FROM
      green
    WINDOW w AS (ORDER BY green.r)

    UNION ALL

    SELECT
      t.x,
      t.y
    FROM (
      SELECT
        (
          SELECT
            min(lower(black.r))
          FROM
            black
        ) AS x,
        lower(g.r) AS y
      FROM
        green AS g
      ORDER BY 
        g.r
      LIMIT 1
      ) AS t
    ) AS t2
  WHERE
    t2.x < t2.y
)
SELECT
  ng.r * b.r AS red
FROM
  not_green AS ng
  INNER JOIN
  black AS b
  ON ng.r && b.r
...
Рейтинг: 0 / 0
12.02.2017, 13:04
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Очень сложная задача, выбрать отрезки
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=53&msg=39402774&tid=1996711]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 42ms
get topic data:
 12ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 2ms
others: 344ms
total:  489ms
созд. / загр.: 489ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]