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

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

Так что не устраивайте балаган!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.10.2002, 17:36:06
    #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, 19:00:36
    #32062892
AAron
AAron
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
2VVG
все немного сложнее, т.к. надо найти не одну точку внутри прямоугольника, а фигуру (ломаную или многоугольник), но принцип будет тем же...
:).
надо найти все отрезки, которые пересекают стороны прямоугольника, а найдя отрезки, можно найти и фигуры.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.10.2002, 10:18:56
    #32062990
hDrummer
hDrummer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
И всё-таки, если к задаче подходить комплексно, как ГИСу, если я правильно понимаю, то без теории графов тут никак не обойтись. А этот тест лишнее свидетельство указывающее род занятий на той фирме ИМХО опять же.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.10.2002, 10:24:17
    #32062996
akuz
akuz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
Подкиньте хорошую ссылочку на теорию графов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.10.2002, 10:31:50
    #32063003
Jimmy
Jimmy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
Здесь есть по графам и не только:
Много разнообразных алгоритмов

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

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

Спасибо, очень интересные ресурсы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.10.2002, 16:13:11
    #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
| Ответить | Цитировать | Написать  
01.11.2002, 09:47:09
    #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, 11:04:07
    #32063896
Алексей Кубенко
Алексей Кубенко
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
Я немного результаты вывел неправильно, написав отрезо № k, просто до этого таблица имела немного другую структуру и в ней были отрезки. На самом же деле надо понимать запись "отрезок № k" как отрезок концом которого является точка с NPos=k, а началом предыдущая точка с максимальным NPos меньшим числа k.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.11.2002, 11:40:18
    #32063923
Nickolay
Nickolay
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка для развлечения :);
2Алексей Кубенко: Снимаю шляпу :)
Хотя в задаче требуется определить пересечение фигур а не отрезков, ограничивающих их. Так например если искомая фигура полностью лежит в заданном прямоугольнике, пересечений их границ вы не найдете, тем не менее пересечение самих фигур имеет место быть. То же самое возникает и в случае когда заданный прямоугольник полностью лежит в искомой фигуре. Тем не менее решение впечатляет, опять-же если исходить из условия задачи о том что отсечение происходит по прямоугольнику, то вычисления пересечений могли быть попроще...


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

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

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



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

А как вы себе представляете алгоритм определения того что два отрезка пересекаются, не найдя точки пересечения (я имею в виду не в буквальном смысле конкретных координат точек пересечения, которые у меня выводятся в селекте. )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / задачка для развлечения :); / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 321ms
Закрыть
start [/forum/topic.php?fid=46&mobile=1&tid=1819149]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 42ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 191ms
total:  321ms
x
x
Закрыть


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