|
26.12.2011, 17:14
|
#1
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
quadrotree or octree
прошу помощи..
1 поделить рекурсивно область ,порядка 5 и более вложений(создать "дерево")
2 все области изначально пусты(null)
3 проверить наличие объекта в области
4 вывести путь к объекту используя "дерево"
как-то так ...
вот код примерный :
Global mx,my
Type box Field x,y,xf,yf,n,name$ End Type
Type ent Field x,y,n End Type
Function enty(x,y,n)
e.ent = New ent
e\x=x
e\y=y
e\n=n
End Function
Function boxing(name$,x,y,xf,yf,n)
b.box = New box
b\x=x
b\y=y
b\xf=xf
b\yf=yf
b\n=n
b\name$=name$
End Function
enty(240,240,0)
enty(340,200,1)
enty(340,340,2)
boxing("A",200,100,100,100,0)
boxing("A",300,100,100,100,0)
boxing("A",300,200,100,100,0)
boxing("A",200,200,100,100,0)
Graphics 800,600,32,2
i=3
tx=240 : ty=240
SetBuffer BackBuffer()
While Not KeyDown(1)
mx=MouseX(): my=MouseY()
If i>=3 Then i=3
Cls
Rect 200,100,200,200,0
Plot mx,my
Oval tx-1,ty-1,3,3,1
For e.ent = Each ent
For b.box = Each box
Rect b\x,b\y,b\xf,b\yf,0
Text b\x+(b\xf/2),b\y+(b\yf/2),b\name$
If i>0 Then
If PointInRect(e\x,e\y,b\x,b\y,b\xf,b\yf) Then
i=i-1
boxing("B",b\x,b\y,b\xf/2,b\yf/2,0)
boxing("B",b\x+(b\xf/2),b\y,b\xf/2,b\yf/2,0)
boxing("B",b\x+(b\xf/2),b\y+(b\yf/2),b\xf/2,b\yf/2,0)
boxing("B",b\x,b\y+(b\yf/2),b\xf/2,b\yf/2,0)
Text 20,20,"IN rect"
EndIf
End If
Next
Next
Text 30,30,i
Flip
Wend
Delete Each box
End
Function PointInRect(iPointX,iPointY,iXPos1,iYPos1,iXPos2,iYPos2)
iXPos2=iXPos2 + iXPos1 : iYPos2=iYPos2 + iYPos1
Return ((((iPointX-iXPos1) Xor (iPointX-iXPos2)) And ((iPointY-iYPos1) Xor (iPointY-iYPos2))) And $80000000)
End Function
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
26.12.2011, 17:30
|
#2
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
Ответ: quadrotree or octree
принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.
Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.
Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.
|
|
(Offline)
|
|
27.12.2011, 08:39
|
#3
|
Мастер
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений (для 504 пользователей)
|
Ответ: quadrotree or octree
Сообщение от polopok
принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.
|
Ну такое:
добавить записи к боксам
Function boxing(name$,x,y,xf,yf,n,uptree,downtrees)
b.box = New box
b\x=x
b\y=y
b\xf=xf
b\yf=yf
b\n=n
b\name$=name$
b\uptree=uptree
b\downtrees=downtrees (массив из 4-х)
End Function
И вносить значения веток в:
boxing("B",b\x,b\y,b\xf/2,b\yf/2,0,Handle(b),??downtrees??)
Когда создаём новую ветку - вносим верхнюю.
Это в после
For e.ent = Each ent
For b.box = Each box
С downtrees косяк, там код доделывать.
Когда создаётся нижняя ветка - (другой может функцией) вносить нижнюю.
1 поделить рекурсивно область ,порядка 5 и более вложений(создать "дерево")
Ну и у тебя это работает. Просто увеличь i - там хоть 10
|
(Offline)
|
|
27.12.2011, 11:36
|
#5
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
Ответ: quadrotree or octree
Последний раз редактировалось polopok, 28.12.2011 в 09:55.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
30.12.2011, 18:44
|
#6
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
Ответ: quadrotree or octree
вот продолжаю разбирать пример ...
; кликайте мышью в смежных квадрантах
;
;
Global p1x,p1y
Global p2x,p2y
Global id,level ,xx#,yy#
; константы детей
Const CHILD00 = 0
Const CHILD01 = 1
Const CHILD11 = 2
Const CHILD10 = 3
; QUADTREE
Type QUADTREE
Field Child.QUADTREE[3] ;четыре потомка
Field xmin,ymin ; начальные координаты квадранта
Field xmax,ymax ; оконечные координаты квадранта
Field id ,lev
End Type
; ============= создаём квадро-дерево =================
Function Quadtree.QUADTREE(xmin,ymin,xmax,ymax,depth)
this.QUADTREE = New QUADTREE
this\xmin = xmin
this\xmax = xmax
this\ymin = ymin
this\ymax = ymax
id = id + 1
this\id = id
this\lev = 0
If (depth > 0)
; деление квадранта на 4-ре квадранта
xmoy = (xmin+xmax) / 2
ymoy = (ymin+ymax) / 2
depth = depth - 1
this\Child[CHILD00] = Quadtree(xmin,ymin,xmoy,ymoy,depth)
this\Child[CHILD01] = Quadtree(xmin,ymoy,xmoy,ymax,depth)
this\Child[CHILD11] = Quadtree(xmoy,ymoy,xmax,ymax,depth)
this\Child[CHILD10] = Quadtree(xmoy,ymin,xmax,ymoy,depth)
EndIf
Return this
End Function
; ==================== Рендер квадро-дерева =====================
Function RenderQuadtree(this.QUADTREE,depth)
If RectsOverlap (xx#,yy#,1,1,this\xmin,this\ymin,this\xmax-this\xmin,this\ymax-this\ymin)
If (depth > 1)
Color 188,188,188
Line (this\xmin+this\xmax)/2,this\ymin,(this\xmin+this\xmax)/2,this\ymax
Line this\xmin,(this\ymin+this\ymax)/2,this\xmax,(this\ymin+this\ymax)/2
depth = depth - 1
RenderQuadtree(this\Child[CHILD00],depth)
RenderQuadtree(this\Child[CHILD01],depth)
RenderQuadtree(this\Child[CHILD11],depth)
RenderQuadtree(this\Child[CHILD10],depth)
If this\Child[CHILD00]\lev = 1 And this\Child[CHILD01]\lev = 1 And this\Child[CHILD11]\lev = 1 And this\Child[CHILD10]\lev = 1 Then
this\lev = 1
EndIf
Else
If MouseHit(1) Then this\lev = 1
If this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill
Color 255,255,255
Text this\xmin+2,this\ymin+2, this\id +".id "+depth
EndIf
EndIf
If this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill
Color 255,255,255
Text this\xmin+2,this\ymin+12, this\lev
End Function
;==============================================================================================
; Сама Программа :
;==============================================================================================
AppTitle "квадро-дерево "
Graphics 512,512,0,2
SetBuffer BackBuffer()
ClsColor 122,122,122
QuadDepth = 5;число вложений (глубина ) : Level 's
QuadSize = 512 ; размеры квадранта
; создание основного квадранта
root.QUADTREE = Quadtree(0,0,QuadSize,QuadSize,QuadDepth)
While Not KeyHit(1)
Cls
xx# = MouseX()
yy# = MouseY()
Select True
Case KeyDown(200) ; Up
Case KeyDown(208) ; Down
Case KeyDown(203) ; Left
Case KeyDown(205) ; Right
End Select
; Рендер квадро-дерева
Color 255,255,255
Rect root\xmin,root\ymin,root\xmax,root\ymax,0
RenderQuadtree(root,QuadDepth)
Flip
Wend
Delete Each QUADTREE
End
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
30.12.2011, 19:56
|
#7
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
Ответ: quadrotree or octree
вместо кружков-квадратов можно загрузить своё изображение
; ведите мышью с зажатой левой кнопкой ,в смежных квадрантах
;и вы увидите их объединение
;полезно для редактора карт
Global p1x,p1y
Global p2x,p2y
Global id,level ,xx#,yy#
; константы детей
Const CHILD00 = 0
Const CHILD01 = 1
Const CHILD11 = 2
Const CHILD10 = 3
;
; QUADTREE
Type QUADTREE
Field Child.QUADTREE[3] ;четыре потомка
Field xmin,ymin ; начальные координаты квадранта
Field xmax,ymax ; оконечные координаты квадранта
Field id ,lev
End Type
; ============= создаём квадро-дерево =================
Function Quadtree.QUADTREE(xmin,ymin,xmax,ymax,depth)
this.QUADTREE = New QUADTREE
this\xmin = xmin
this\xmax = xmax
this\ymin = ymin
this\ymax = ymax
id = id + 1
this\id = id
this\lev = 0
If (depth > 0)
; деление квадранта на 4-ре квадранта
xmoy = (xmin+xmax) / 2
ymoy = (ymin+ymax) / 2
depth = depth - 1
this\Child[CHILD00] = Quadtree(xmin,ymin,xmoy,ymoy,depth)
this\Child[CHILD01] = Quadtree(xmin,ymoy,xmoy,ymax,depth)
this\Child[CHILD11] = Quadtree(xmoy,ymoy,xmax,ymax,depth)
this\Child[CHILD10] = Quadtree(xmoy,ymin,xmax,ymoy,depth)
EndIf
Return this
End Function
; ==================== Рендер квадро-дерева =====================
Function RenderQuadtree(this.QUADTREE,depth)
If RectsOverlap (xx#,yy#,1,1,this\xmin,this\ymin,this\xmax-this\xmin,this\ymax-this\ymin)
If (depth > 1)
Color 188,188,188
Line (this\xmin+this\xmax)/2,this\ymin,(this\xmin+this\xmax)/2,this\ymax
Line this\xmin,(this\ymin+this\ymax)/2,this\xmax,(this\ymin+this\ymax)/2
depth = depth - 1
RenderQuadtree(this\Child[CHILD00],depth)
RenderQuadtree(this\Child[CHILD01],depth)
RenderQuadtree(this\Child[CHILD11],depth)
RenderQuadtree(this\Child[CHILD10],depth)
If this\Child[CHILD00]\lev = 1 And this\Child[CHILD01]\lev = 1 And this\Child[CHILD11]\lev = 1 And this\Child[CHILD10]\lev = 1 Then this\lev = 2
If this\Child[CHILD00]\lev = 2 And this\Child[CHILD01]\lev = 2 And this\Child[CHILD11]\lev = 2 And this\Child[CHILD10]\lev = 2 Then this\lev = 3
If this\lev = 2 Then
this\Child[CHILD00]\lev = 0
this\Child[CHILD01]\lev = 0
this\Child[CHILD11]\lev = 0
this\Child[CHILD10]\lev = 0
EndIf
If this\lev = 3 Then
this\Child[CHILD00]\lev = 0
this\Child[CHILD01]\lev = 0
this\Child[CHILD11]\lev = 0
this\Child[CHILD10]\lev = 0
this\lev = 3
EndIf
Else
If MouseDown(1) Then this\lev = 1
If this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill
Color 255,255,255
Text this\xmin+2,this\ymin+2, this\id +".id "
Text this\xmin+2,this\ymin+12, this\lev
EndIf
EndIf
If this\lev = 1 Then Color 255,0,0 : fill = True Else Color 66,66,66 : fill = False
Rect this\xmin+1,this\ymin+1,this\xmax-this\xmin-1,this\ymax-this\ymin-1,fill
Color 255,255,255
Text this\xmin+2,this\ymin+12, this\lev
End Function
;==============================================================================================
; Сама Программа :
;==============================================================================================
AppTitle "квадро-дерево "
Graphics 512,512,0,2
;
gor2=CreateImage(64,64)
gor8=CreateImage(128,128)
gor1=CreateImage(32,32)
SetBuffer ImageBuffer(gor2)
Rect 10,10,34,34,1
Oval 34/2,34/2,32,32,0
SetBuffer ImageBuffer(gor1)
Rect 10,10,14,14,0
Oval 30/2,30/2,8,8,1
SetBuffer ImageBuffer(gor8)
Rect 0,0,124,124,0
Rect 20,20,82,82,1
;
SetBuffer BackBuffer()
ClsColor 122,122,122
QuadDepth = 5;число вложений (глубина ) : Level 's
QuadSize = 512 ; размеры квадранта
; создание основного квадранта
root.QUADTREE = Quadtree(0,0,QuadSize,QuadSize,QuadDepth)
While Not KeyHit(1)
Cls
xx# = MouseX()
yy# = MouseY()
;DrawImage gor1,200,200
Select True
Case KeyDown(200) ; Up
Case KeyDown(208) ; Down
Case KeyDown(203) ; Left
Case KeyDown(205) ; Right
End Select
; Рендер квадро-дерева
Color 255,255,255
Rect root\xmin,root\ymin,root\xmax,root\ymax,0
For wroot.QUADTREE = Each QUADTREE
If wroot\lev = 1 Then
Color 255,0,0
DrawImage gor1 ,wroot\xmin,wroot\ymin
;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
ElseIf wroot\lev = 2 Then
Color 255,0,0
DrawImage gor2 ,wroot\xmin,wroot\ymin
;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
ElseIf wroot\lev = 3 Then
Color 255,0,0
DrawImage gor8 ,wroot\xmin,wroot\ymin
;Rect wroot\xmin,wroot\ymin,wroot\xmax-wroot\xmin,wroot\ymax-wroot\ymin,1
EndIf
Next
RenderQuadtree(root,QuadDepth)
Flip
Wend
Delete Each QUADTREE
End
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
30.12.2011, 20:04
|
#8
|
ПроЭктировщик
Регистрация: 17.07.2009
Сообщений: 182
Написано 51 полезных сообщений (для 71 пользователей)
|
Ответ: quadrotree or octree
пункт 1,2,3 вроде выполнен а четвёртый хм...
|
(Offline)
|
|
24.01.2012, 20:47
|
#9
|
Мастер
Регистрация: 24.06.2009
Адрес: Набережные Челны
Сообщений: 930
Написано 292 полезных сообщений (для 504 пользователей)
|
Ответ: quadrotree or octree
|
(Offline)
|
|
13.02.2012, 17:45
|
#10
|
|
Ответ: quadrotree or octree
Вот только зачем qtree для 2Д ? имхо bsp-2d эффективнее.
|
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 20:01.
|