ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / задачка для развлечения :);
20 сообщений из 20, страница 1 из 1
задачка для развлечения :);
    #32062802
Dolon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dolon
Гость
Дать описание структуры базы данных (БД), в которой хранится набор геометрических фигур - ломанных и многоугольников. БД должна быть оптимизирована, для получения списка фигур, пересекающихся с заданным прямоугольником.
Фактически можно считать, что в БД хранится географическая карта, а задаваемый пользователем прямоугольник - "окошко", через которое он смотрит на карту.
Полный перебор не является решением.
...
Рейтинг: 0 / 0
29.10.2002, 16:02:58
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062805
Фотография hDrummer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hDrummer
Участник
Это уважаемый вам в теорию графов.
Развлекайтесь на здоровье.
...
Рейтинг: 0 / 0
29.10.2002, 16:06:09
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062808
Dolon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dolon
Гость
Я не себе , я кому-нить предлагаю ...:); глубоко уважаемый...
...
Рейтинг: 0 / 0
29.10.2002, 16:07:48
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062810
AAron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AAron
Участник
как я понимаю, здесь все же две задачи :)
1. БД для хранения фигур
2. Алгоритм для вычисления пересекающихся объектов

могу добавить к предыдущему - в компьютерную графику :) Например у издательства ДИАЛОГ (кажется) были книги на эту тему. Конечно без БД, только алгортимы :)
...
Рейтинг: 0 / 0
29.10.2002, 16:10:34
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062811
Dolon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dolon
Гость
Хе это тестовое задание для прог..-ров в колндайке :);
...
Рейтинг: 0 / 0
29.10.2002, 16:12:19
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062816
AAron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AAron
Участник
где?
...
Рейтинг: 0 / 0
29.10.2002, 16:17:30
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062818
Dolon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dolon
Гость
Блин это уже не по теме :);
http://www.klondike.ru/index.html?t=8
Конец связи
...
Рейтинг: 0 / 0
29.10.2002, 16:20:21
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062819
Фотография akuz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
akuz
Участник
Это там в Клондайке народ развлекается, а здесь по большей части люди серьёзные.

Так что не устраивайте балаган!
...
Рейтинг: 0 / 0
29.10.2002, 16:21:23
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062853
Фотография VVG_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VVG_
Участник
Какая теория графов? Все как дважды два:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
create table t (FigID int,Pos int,X int,Y int)
go
create index ix_t on t (x,y,figid)
go
insert into t values ( 1 , 1 , 5 , 10 )
insert into t values ( 1 , 2 , 3 , 5 )
insert into t values ( 1 , 3 , 6 , 1 )
insert into t values ( 1 , 4 , 7 , 5 )
insert into t values ( 1 , 5 , 5 , 6 )
insert into t values ( 1 , 6 , 6 , 8 )
go
select distinct figid from t 
where x between  5  and  10  
and y between  8  and  11 
go
drop table t
...
Рейтинг: 0 / 0
29.10.2002, 17:36:06
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062892
AAron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AAron
Участник
2VVG
все немного сложнее, т.к. надо найти не одну точку внутри прямоугольника, а фигуру (ломаную или многоугольник), но принцип будет тем же...
:).
надо найти все отрезки, которые пересекают стороны прямоугольника, а найдя отрезки, можно найти и фигуры.
...
Рейтинг: 0 / 0
29.10.2002, 19:00:36
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062990
Фотография hDrummer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hDrummer
Участник
И всё-таки, если к задаче подходить комплексно, как ГИСу, если я правильно понимаю, то без теории графов тут никак не обойтись. А этот тест лишнее свидетельство указывающее род занятий на той фирме ИМХО опять же.
...
Рейтинг: 0 / 0
30.10.2002, 10:18:56
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32062996
Фотография akuz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
akuz
Участник
Подкиньте хорошую ссылочку на теорию графов.
...
Рейтинг: 0 / 0
30.10.2002, 10:24:17
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063003
Фотография Jimmy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jimmy
Участник
Здесь есть по графам и не только:
Много разнообразных алгоритмов

Библиотека алгоритмов

Еще ссылки
...
Рейтинг: 0 / 0
30.10.2002, 10:31:50
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063020
Фотография hDrummer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hDrummer
Участник
По теории графов:
http://pgap.chat.ru/zap/zap261.htm#0
http://mportal.narod.ru/Graphs.html
...
Рейтинг: 0 / 0
30.10.2002, 10:58:53
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063030
Фотография akuz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
akuz
Участник
2 Jimmy & hDrummer

Спасибо, очень интересные ресурсы.
...
Рейтинг: 0 / 0
30.10.2002, 11:21:26
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063702
Фотография Nickolay
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nickolay
Участник
Структура БД будет примерно такой:
Таблица графических объектов
Код: plaintext
1.
2.
3.
CREATE TABLE Objects ( ID int IDENTITY ( 1 ,  1 ) NOT FOR REPLICATION NOT NULL, 
Color int NOT NULL, Pattern int,
Maxx int NOT NULL, Minx int NOT NULL, 
Maxy int NOT NULL, Miny int NOT NULL )

Таблица метрики:
Код: plaintext
1.
CREATE TABLE Metric ( ObjectID int NOT NULL, Pos int NOT NULL,
X int NOT NULL, Y int NOT NULL )

Запрос будет таким:
Код: plaintext
1.
2.
3.
SELECT M.Color, M.Pattern, M.* FROM Metric M
INNER JOIN Objects O ON O.ID = M.MetricID
WHERE ( O.Maxx >= @frameleft OR O.Minx <= @frameright ) AND 
        ( O.Maxy >= @frametop AND O.Miny <= @framebottom )

Про отсечение метрики нигде не говорится, так что теория графов здесь абсолютно ни при чем.
Да и сомневаюсь я что средствами SQL можно это сделать, хотя соблазн и велик
...
Рейтинг: 0 / 0
31.10.2002, 16:13:11
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063856
Алексей Кубенко
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Кубенко
Гость
Вообще не уверен правильно ли я понял задание.
Если правильно, то ниже описанный запрос выводит с какими фигурами пересекается трапеция (не обязательно квадрат можно брать любую фигуру вот для примера взял трапецию). Влом расчитывать координаты точек для тех случаев когда отрезок одной фигуры имеет общий отрезок с отрезком другой фигуры.

Код: plaintext
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.
99.
100.
101.
102.
103.
104.
105.
106.
 -- Фигурой является набор отрезков соединяющих точки начиная с Min(NPos) и оканчивая с Max(NPos)
 
create table t_points( 
x1 real Not NULL, 
y1 real Not NULL, 
NPos int Not NULL,  --Позиция точки
 
NFigure int Not NULL)

 -- нулевая фигура должна быть квадратом это необязательно я взял трепецию.
 
insert into t_points VALUES ( 4 , 3 , 0 , 0 )
insert into t_points VALUES ( 4 , 6 , 1 , 0 )
insert into t_points VALUES ( 6 , 6 , 2 , 0 )
insert into t_points VALUES ( 7 , 3 , 3 , 0 )
insert into t_points VALUES ( 4 , 3 , 4 , 0 )

 -- треугольник
 
insert into t_points VALUES (- 3 , 1 , 0 , 1 )
insert into t_points VALUES ( 1 , 4 , 1 , 1 )
insert into t_points VALUES ( 3 , 2 , 2 , 1 )
insert into t_points VALUES (- 3 , 1 , 3 , 1 )

 -- ломаная
 
insert into t_points VALUES ( 5 , 5 , 0 , 2 )
insert into t_points VALUES ( 7 , 2 , 1 , 2 )
insert into t_points VALUES ( 8 , 4 , 2 , 2 )
 -- отрезок
 
insert into t_points VALUES (- 3 , 7 , 0 , 3 )
insert into t_points VALUES ( 5 , 4 , 1 , 3 )

 -- отрезок содержащий в себе сторону трапеции
 
insert into t_points VALUES ( 8 , 0 , 0 , 4 )
insert into t_points VALUES ( 5 , 9 , 1 , 4 )



select  'Отрезок №' + convert(varchar( 10 ),t.LineKvadrat) + ' ' + convert(varchar( 10 ),t.NFigure1) + 
	'-ой фигуры пересекает отрезок №' + convert(varchar( 10 ),t.LineSomeFigure) + ' ' + 
	convert(varchar( 10 ),t.NFigure2) + '-ой фигуры в точке (' + 
	convert(varchar( 10 ),t.x11+(t.x21-t.x11)*( (t.y11-t.y12)*(t.x22-t.x12)+(t.x12-t.x11)*(t.y22-t.y12))/
		 (-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 )) + ',' + convert(varchar( 10 ),
t.y11+(t.y21-t.y11)*( (t.y11-t.y12)*(t.x22-t.x12)+(t.x12-t.x11)*(t.y22-t.y12))/
		 (-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 )) + ')'
from
(	
	select *
	from
	(
	select t1.x1 As x11,t1.y1 As y11,
		(select x1 from t_points tp1 where tp1.NFigure=t1.NFigure 
			and tp1.NPos= (select min(NPos) from t_points where NPos> t1.NPos)) As x21,
		(select y1 from t_points tp1 where tp1.NFigure=t1.NFigure 
			and tp1.NPos= (select min(NPos) from t_points where NPos> t1.NPos)) As y21,
		t2.x1 x12,t2.y1 y12,
		(select x1 from t_points tp2 where tp2.NFigure=t2.NFigure 
			and tp2.NPos= (select min(NPos) from t_points where NPos> t2.NPos)) As x22,
		(select y1 from t_points tp2 where tp2.NFigure=t2.NFigure 
			and tp2.NPos= (select min(NPos) from t_points where NPos> t2.NPos)) As y22,
		 t1.NFigure NFigure1,t2.NFigure NFigure2,t1.NPos+ 1  As LineKvadrat,t2.NPos+ 1  As LineSomeFigure
	from t_points t1,t_points t2
	where t1.NFigure= 0  and t2.NFigure> 0 
		and t1.NPos<(Select max(NPos) from t_Points where NFigure=t1.NFigure)
		and t2.NPos<(Select max(NPos) from t_Points where NFigure=t2.NFigure)
	) t
	where abs(-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 )>  0 . 00001 
) As t
where ( (t.y11-t.y12)*(t.x22-t.x12)+(t.x12-t.x11)*(t.y22-t.y12))/ (-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 ) between  0  and  1 
	and ( (t.y21-t.y11)*(t.x12-t.x11)+(t.y11-t.y12)*(t.x21-t.x11) )/ (-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 ) between  0  and  1 
union all
select  'Отрезок ' + convert(varchar( 10 ),tt.LineKvadrat) + ' фигуры ' + convert(varchar( 10 ),tt.NFigure1) 
	+ ' имеет общий отрезок с отрезком ' + convert(varchar( 10 ),tt.LineSomeFigure) + ' фигуры ' +
	convert(varchar( 10 ),tt.NFigure2) 
from
(	
	select *
	from
	(
	select t1.x1 As x11,t1.y1 As y11,
		(select x1 from t_points tp1 where tp1.NFigure=t1.NFigure 
			and tp1.NPos= (select min(NPos) from t_points where NPos> t1.NPos)) As x21,
		(select y1 from t_points tp1 where tp1.NFigure=t1.NFigure 
			and tp1.NPos= (select min(NPos) from t_points where NPos> t1.NPos)) As y21,
		t2.x1 x12,t2.y1 y12,
		(select x1 from t_points tp2 where tp2.NFigure=t2.NFigure 
			and tp2.NPos= (select min(NPos) from t_points where NPos> t2.NPos)) As x22,
		(select y1 from t_points tp2 where tp2.NFigure=t2.NFigure 
			and tp2.NPos= (select min(NPos) from t_points where NPos> t2.NPos)) As y22,
		 t1.NFigure NFigure1,t2.NFigure NFigure2,t1.NPos+ 1  As LineKvadrat,t2.NPos+ 1  As LineSomeFigure
	from t_points t1,t_points t2
	where t1.NFigure= 0  and t2.NFigure> 0 
		and t1.NPos<(Select max(NPos) from t_Points where NFigure=t1.NFigure)
		and t2.NPos<(Select max(NPos) from t_Points where NFigure=t2.NFigure)
	) t
	where abs(-t.x22*t.y21+t.x22*t.y11 + t.x12*t.y21-t.x12*t.y11 + t.y22*t.x21 
		+ t.y12*t.x11 - t.y22*t.x11-t.y12*t.x21 )<  0 . 00001  and
		abs( (t.y21-t.y11)*(t.x12-t.x11)+(t.y11-t.y12)*(t.x21-t.x11))< 0 . 00001 
) As tt
...
Рейтинг: 0 / 0
01.11.2002, 09:47:09
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063896
Алексей Кубенко
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Кубенко
Гость
Я немного результаты вывел неправильно, написав отрезо № k, просто до этого таблица имела немного другую структуру и в ней были отрезки. На самом же деле надо понимать запись "отрезок № k" как отрезок концом которого является точка с NPos=k, а началом предыдущая точка с максимальным NPos меньшим числа k.
...
Рейтинг: 0 / 0
01.11.2002, 11:04:07
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32063923
Фотография Nickolay
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nickolay
Участник
2Алексей Кубенко: Снимаю шляпу :)
Хотя в задаче требуется определить пересечение фигур а не отрезков, ограничивающих их. Так например если искомая фигура полностью лежит в заданном прямоугольнике, пересечений их границ вы не найдете, тем не менее пересечение самих фигур имеет место быть. То же самое возникает и в случае когда заданный прямоугольник полностью лежит в искомой фигуре. Тем не менее решение впечатляет, опять-же если исходить из условия задачи о том что отсечение происходит по прямоугольнику, то вычисления пересечений могли быть попроще...


PS-предложенный мною метод тоже далек от совершенства и не работает для невыпуклых фигур

PPS-искать точки пересечения отрезков только для того чтобы определить пересекаются фигуры или нет очень уж накладно, однако если кандидатов сначала отобрать с помощью запроса, предложенного мной, то думаю будет как раз то, что требуется в задаче, и может даже немного больше...
...
Рейтинг: 0 / 0
01.11.2002, 11:40:18
| Ответить | Цитировать | Написать  
задачка для развлечения :);
    #32064003
Алексей Кубенко
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алексей Кубенко
Гость
2 Nickolay.
>Хотя в задаче требуется определить пересечение фигур а не отрезков, ограничивающих их.

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



>PPS-искать точки пересечения отрезков только для того чтобы определить пересекаются фигуры или нет очень уж накладно...

А как вы себе представляете алгоритм определения того что два отрезка пересекаются, не найдя точки пересечения (я имею в виду не в буквальном смысле конкретных координат точек пересечения, которые у меня выводятся в селекте. )
...
Рейтинг: 0 / 0
01.11.2002, 13:33:37
| Ответить | Цитировать | Написать  
20 сообщений из 20, страница 1 из 1
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / задачка для развлечения :);
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=46&msg=32063856&tid=1819149]:
 0ms
get settings:
 8ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 32ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 48ms
get tp. blocked users:
 1ms
others: 215ms
total:  330ms
созд. / загр.: 330ms
x
x
Закрыть


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