forum.boolean.name - quadrotree or octree

forum.boolean.name (http://forum.boolean.name/index.php)

- Blitz3D (http://forum.boolean.name/forumdisplay.php?f=45)

- - quadrotree or octree (http://forum.boolean.name/showthread.php?t=16101)

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

Ответ: quadrotree or octree

принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.

Цитата:

Основной идеей Quadtree является последовательное разделение участков пространства на четыре части. Т.е. берем квадрат, делим его на четыре квадрата поменьше, каждый получившийся — еще на четыре, и так далее. Получается квадратное дерево, потому так и называется.

Основным объектом нашего Quadtree является как раз такой квадрат, или узел дерева. Он содержит список тех объектов, которые находятся непосредственно в нем, а также ссылки на четыре дочерних квадрата поменьше.

Ответ: quadrotree or octree

Цитата:

Сообщение от polopok (Сообщение 215288)

принцип понятен ,но никак не могу понять как выстаивать само "дерево" с ссылками на элементы уровнем ниже.

Ну такое:
добавить записи к боксам

Код:

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 :)

Ответ: quadrotree or octree

да работать то работает ,но в самом начале нужно рекурсивно создать пустое "дерево", а не по проверке пересечения.
сейчас пытаюсь завязать на связанных списках.
вот разбираю пример http://blitzetc.blitzmax.ru/index.php/%D0%94%D1%80%D0%B5%D0%B2%D0%BE%D0%B2%D0%B8%D0%B4%D 0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1 %82%D1%83%D1%80%D0%B0

Ответ: 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

Ответ: 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

Ответ: quadrotree or octree

пункт 1,2,3 вроде выполнен а четвёртый хм...

Ответ: quadrotree or octree

Нашёл рабочий quadtree 2D-пример:
http://bond357.free.fr/main/forums/viewtopic.php?id=10

Ответ: quadrotree or octree

Вот только зачем qtree для 2Д ? имхо bsp-2d эффективнее.