[Alg] Search in 2D-grid *

[Verwijderd]

Hoi,

Voor het tekenen van flows ben ik opzoek naar een mothode om zo snel mogelijk te bepalen wat er op een bepaald moment in het zichtbare scherm getoond moet worden. Dit als gevolg van het scrollen.
De flow bestaat simpel gezegd uit aantal rechthoeken en lijnen. Na het scrollen moet dus zo snel mogelijk bepaald worden wat er op dat moment getekend moet worden.
Wat ik had bedacht: eerst binair zoeken in de x-coordinaten in de tabel en vervolgens als er een geldige is gevonden vanaf deze naar achter en naar voren lezen zolang ik coordinaten tegenkomt die in het zichtbare gebied vallen. Vervolgens per gevonden object de y-coordinaten uit lezen op dezelfde wijze.

Een optie om de hele flow in het geheugen te tekenen (wat ik eerst deed) wil ik niet doen aangezien dit bij grote flows erg veel geheugen vreet.

Wellicht dat iemand nog ideeen heeft hoe het zoeken naar de objecten sneller kan???

alvast bedankt.

[Verwijderd]

Om het wellicht wat eenvoudiger te formuleren:

Ik heb een grote lijst met coordinaten (x,y). Vervolgens heb ik een rechthoek. Ik wil vervolgens erg snel kunnen bepalen welke coordinaten er binnen deze rechthoek vallen.
Ik dacht aan het maken van een 2d tabel alleen komen daardan ook de coordinaten in voor die niet van toepassing zijn en de tabel wordt dan al snel zeer groot omdat er erg veel loze punten inkomen.

[Ericston]

Dit is in principe gewoon zoeken welke getallen tussen een bepaalde onder- en bovengrens liggen, maar dan een dimensie hoger, toch?

Afhankelijk van het aantal punten dat je hebt zou je ervoor kunnen kiezen om een quadtree te gebruiken. Dat is dus je google search term.

Mogelijkerwijs zei je dat al op een andere manier in je eerste post, maar die is inderdaad nogal vaag (wat zijn flows anyway?).

[ATS]

Blader eens een keer door het boek "Design and Analysis of Spacial Data Access Structures" van Samet. Het beschrijft manieren op data op te slaan die betrekking hebben op ruimtes. Daar zijn veel methoden voor, elk met zijn eigen voor- en nadelen. Wat je het beste kan gebruiken hangt dus ook af van je overige eisen...

[Verwijderd]

Met flows bedoel ik schema's van bijvoorbeeld database etc...
Ik denk dat ik het eens ga proberen met gewoon een recordset.....dus alle objecten daarin gooien en dan met een SQL een selectie op de x en y coordinaten. Lijkt me een erg eenvoudige methode. Ben benieuwd hoe snel zo'n recordset is (gebruik visual basic 6 dan met adodb)

[ATS]

Als je op zowel X als Y een index aanmaakt zal dat best snel zijn denk ik. Overigens denk ik dat het handig is om voor je objecten (top, left, bottom, right) op te slaan. Zo kan je in één keer zoeken met een query of je object in je rechthoek past.

[Verwijderd]

Moet ik nog eens even zoeken hoe ik dynamisch een index kan toekennen aan een recordset.
Ik heb nog even gezocht op quadtree maar kan nog niet een goede uitleg vinden wat dit nu inhoud.
Sla zo wie zo de hoekpunten op omdat als een vlak al met 1 punt in het zichtbare vlak komt hij getekend moet worden.

[.oisyn]

Een quadtree, bsp-tree of kd-tree lijkt me hiervoor wel geschikt. Een bsp-tree misschien wat minder omdat je natuurlijk naar axis-aligned rechthoeken zoekt, en de splitslijnen van quadtrees en kd-trees zijn ook altijd axis-aligned.

Wat je ook kunt gebruiken is een segment-tree (bedoeld voor opslag van intervallen) voor de x-richting, met in elke node een 2e segment-tree voor de y-richting

Alle bovenstaande structuren hebben O(log n + k) zoektijd, O(n log n) geheugen en O(n log n) bouwtijd

[Verwijderd]

.oisyn schreef op 23 februari 2004 @ 13:17:
Een quadtree, bsp-tree of kd-tree lijkt me hiervoor wel geschikt. Een bsp-tree misschien wat minder omdat je natuurlijk naar axis-aligned rechthoeken zoekt, en de splitslijnen van quadtrees en kd-trees zijn ook altijd axis-aligned.

Wat je ook kunt gebruiken is een segment-tree (bedoeld voor opslag van intervallen) voor de x-richting, met in elke node een 2e segment-tree voor de y-richting

Alle bovenstaande structuren hebben O(log n + k) zoektijd, O(n log n) geheugen en O(n log n) bouwtijd

Weet je misschien waar ik informatie kan vinden over hoe een quadtree werkt? Het zegt me namelijk helemaal niks. Ik heb al gegoogled alleen kan niet een goede uitleg vinden.

[.oisyn]

Een quadtree is een boom waarbij je de ruimte steeds recursief verdeelt in 4 (al dan niet gelijke) stukken (quadranten). Je splitst dus steeds over de x- en y-as.

Je kunt ervoor kiezen om de objecten in de nodes of in de bladeren op te slaan. Als je ze in de nodes opslaat moet je ze zo diep mogelijk opslaan, pas als een onderverdeling van de node het object zou snijden dan stop je ze in de node, en anders bekijk je het opnieuw bij de kinderen.
Als je ze in de bladere opslaat moet je rekening houden met het feit dat 1 object in meerdere bladeren voor kan komen, tenzij je ze ook onderverdeelt in kleinere stukjes, maar dat lijkt me niet handig.

Verder kun je er nog voor zorgen dat de boom altijd een maximale diepte heeft, of dat je stopt als er in een node nog maar x objecten staan. Let er wel op dat als minstens x objecten elkaar overlappen dat je recursie dan oneindig door blijft gaan, dus hier moet je dan wel even een test voor inbouwen.

Het zoeken in de quadtree is vrij simpel, vooral in jouw geval. Je pakt je rechthoek waarop je zoekt, en je begint bij de root node. Snijdt deze node de rechthoek, test dan alle objecten die in deze nodes opgeslagen zitten (mits die er zijn), en doe daarna weer precies hetzelfde met de 4 kinderen. Als een node je rechthoek niet snijdt dan hoef je 'm ook niet verder te testen

[Verwijderd]

Zijn er code voorbeelden hoe zoiets geimplenteerd wordt. Zoals een tabel definitie??? Ik kan er niet echt een beeld van vormen hoe een quadtree eruit ziet in een tabel definitie....iets met recusiviteit????

[.oisyn]

Een boomstructuur in een relationele database is een beetje lastig, moet je ook niet willen proberen

[Verwijderd]

Dat kan ik begrijpen een boom structuur in een relationele database.....
Daarnaast weet ik niet of dit trouwens gaat werken.
Ik kan namelijk niet alles in een bepaald vlak plaatsen. Als ik het complete schema in eerste instantie in 4-en wil opdelen dan kan het voorkomen dat sommigen op de grens liggen van 2 ,3, of in het slechtse geval dus 4 vlakken.

Ik denk toch dat ik maar een database tabel in elkaar knoop met daarin de objecten met coordinaten dmv ADODB en het filer-commando.....dit zou met een stuk of 10.000 toch aardig snel moeten zijn???? Of vergis ik me??

[.oisyn]

Ik kan namelijk niet alles in een bepaald vlak plaatsen. Als ik het complete schema in eerste instantie in 4-en wil opdelen dan kan het voorkomen dat sommigen op de grens liggen van 2 ,3, of in het slechtse geval dus 4 vlakken.

da's ook logisch en helemaal niet erg. Zoals ik al zei kun je ze in dat geval in de node opslaan waarbij ze wel passen, of je slaat ze in beide kinderen op (in welk geval alle objecten dus helemaal onderin de boom staan). Een doorsnijding van je objecten is niet erg, de structuur wordt ook vrij nutteloos als dit niet voor mag komen

.edit: overigens heeft een goede database wel opslagmogelijkheden voor geometrische vormen, en ondersteunt ie intersection queries

[ Voor 11% gewijzigd door .oisyn op 23-02-2004 14:46 ]

[Verwijderd]

Maar is er ergens een voorbeeld van te vinden hoe een quadtree te implementeren in code?

[Verwijderd]

kick...

Heeft iemand een voorbeeld van hoe de definitief van een quadtree eruit ziet? Een soort tabel?? met hoeveel dimensies???

[.oisyn]

[google=quadtree example], 3e en 4e hit
Er is echt zat info over te vinden op internet daarover hoor

[Verwijderd]

oisyn,

Bedankt, ik zat te zoeken met een programmeertaal erbij.
Maar aangezien jij er nogal wat vanaf schijnt te weten heb ik een vraag.
IS het voor mij eventueel niet handiger gewoon alle objecten vierkanten/lijnen in een recordset te gooien en dmv van een filter op x en y coordinaten vervolgens te selecteren waarop ik heb geklikt of wat op dat moment visueel op het scherm getoodn moet worden? Qua programmering zou dit zeer eenvoudig zijn.
Maar hoe zal de snelheid hiervan zijn?? Het gaat dan om zo'n max 10000 objecten waarop tijdens het scrollen een query steeds wordt uitgevoerd...

Of misschien dat iemand anders hier antwoord op kan geven?

Wat ik snap is dat he tminder mooi is met een recordset want dat vergt weer een ado component maar dat maakt voor de applicatie opzich niks uit.

[.oisyn]

Hangt een beetje van je database af. Zoals ik al zei ondersteunen veel goede databases ook geometrische objecten waarop je verschillende queries kunt doen

Als je het idee gebruikt wat hierboven geopperd is, dus objecten opslaan adhv hun bounding box (x1, y1, x2, y2), en je zet daar indices op, dan krijg je volgens mij gewoon een 2d range-query die wel aardig snel is. Maar ik ben geen database-meneer dus daar zullen bepaalde andere mensen je wel een beter uitsluitsel over kunnen geven

[ATS]

Als je niet heel erg veel objecten hebt is zo'n database search snel zat denk ik. 10000 objecten is in dat verband niet extreem veel. Wel moet je zorgen dat je indices hebt op je coordinaten natuurlijk.
Voorbeelden van de quadtree (en vele andere opties) zijn te vinden in het al eerder door mij genoemde boek van Samet, compleet met listings.

[ Voor 23% gewijzigd door ATS op 24-02-2004 22:16 ]

[Verwijderd]

Ok dan ga ik dat met een access-database maar eens proberen.
Dus dan op beide coordinaten of op de 4 hoekpunten indexen aan te maken.
Jammer is wel doordat er indexen gedefinieerd moeten worden dan ik aan een recordset niet voldoende heb dan. Maar dan maar mdb-tje bij de applicatie.
In iedergeval bedankt.

[ATS]

Je hebt alleen van (x,y) van het punt linksboven en van het punt rechtsonder nodig. Geldt zowel voor lijnen als voor vlakken. Idee is vervolgens:

Stel je viewport (het stuk dat zichtbaar is) heeft linksboven coordinaten (VPx1,VPy1) en rechtsonder coordinaten (VPx2, VPy2).

Nu is het een kwestie van checken of je object (Ox1,Oy1),(Ox2,Oy2) hierbinnen te zien is. Dat is het geval als (uitgaande van een coordinatenstelsel met oorsprong links boven):
Ox1<VPx2 AND Ox2>VPx1 AND Oy1<VPy2 AND Oy2 > VPy1

Ziet er wat cryptisch uit, dat geef ik toe. Het idee is dat je test of de bovenkant van je object boven de onderkant van je viewport staat, en dat de onderkant van dat object onder de bovenkant is: in dat geval heb je namelijk een deel van je object binnen de grenzen. Het zelfde voor links/rechts.

[Verwijderd]

dank je wel, daar kom ik wel uit.
Heb wel enige SQL kennis ook dus dat moet wel lukken.
Ben niet zo'n wiskundige om effe in de algoritmes van een quadtree te duiken al hoewel dat tuurlijk wel erg mooi zou zijn.
Gaat me meer om de snelheid van het zoeken en opnieuw steeds aanmaken van de viewpoort via een geheugen bitmap en het via de SQL daarbij zoeken van de objecten wat dat voor snelheid haalt.
Als ik zover ben laat ik het wel effe weten.

[Verwijderd]

Hoi,

Ik heb effe simpel testje uitgevoerd met een adodb recordset en met een access database met 1 tabel x/y en een id met indexen op de x en het y attribuut.

Echter tot mijn verassing is de enkele recordset die ik definieer en vul in VB een stuk sneller:

mbt van database en indexen op velden : tijden : 0,188 / 0,172 seconden
met een simpele adodb.recordset : tijden : 0,109 / 0,094 seconden

Het scheelt dus behoorlijk relatief gezien. Met index zou toch juist sneller moeten zijn????

de coding die ik heb gebruikt: (command1 en command2 voor vullen/uitlezen van database, command3/command4 voor vullen/uitlezen van adodb.recordset)

code:

Dim cnn As ADODB.Connection
Dim rs As ADODB.Recordset
Dim rst As ADODB.Recordset

Private Sub Command1_Click()
  Set cnn = New Connection
  cnn.connectionstring = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" & _
            "D:\test\db1.mdb" & ";Persist Security Info=False"
  cnn.Open
  Set rs = New ADODB.Recordset
  rs.Open "delete * from tblObject", cnn
  rs.Open "select * from tblObject", cnn, adOpenKeyset, adLockOptimistic
  Dim i As Long
  For i = 1 To 100000
    rs.AddNew
    rs.Fields("x") = CStr(i)
    rs.Fields("y") = CStr(i)
    rs.Update
  Next i
  rs.Close
End Sub

Private Sub Command2_Click()
  Dim a
  Dim i
  Dim j
  a = Timer
  rs.Open "select * from tblObject where x > 15000 and y > 20000 and x > 19000", cnn, adOpenKeyset, adLockOptimistic
  For i = 1 To rs.RecordCount
    j = i
  Next
  Debug.Print Format(Timer - a, "0.000")
  rs.Close
End Sub

Private Sub Command3_Click()
  Set rst = New ADODB.Recordset
  rst.Fields.Append "x", adInteger
  rst.Fields.Append "y", adInteger
  rst.Open
  For i = 1 To 100000
    rst.AddNew
    rst.Fields("x").Value = i
    rst.Fields("y").Value = i
  Next
End Sub

Private Sub Command4_Click()
    Dim a
  Dim i
  Dim j
  a = Timer
  rst.Filter = "x > 15000 and y > 20000 and x > 19000"
  For i = 1 To rst.RecordCount
    j = i
  Next
  Debug.Print "test2 " & Format(Timer - a, "0.000")
End Sub

[Feyd-Rautha]

Verwijderd schreef op 25 februari 2004 @ 19:46:
Hoi,

Ik heb effe simpel testje uitgevoerd met een adodb recordset en met een access database met 1 tabel x/y en een id met indexen op de x en het y attribuut.

Echter tot mijn verassing is de enkele recordset die ik definieer en vul in VB een stuk sneller:

mbt van database en indexen op velden : tijden : 0,188 / 0,172 seconden
met een simpele adodb.recordset : tijden : 0,109 / 0,094 seconden

Het scheelt dus behoorlijk relatief gezien. Met index zou toch juist sneller moeten zijn????

de coding die ik heb gebruikt: (command1 en command2 voor vullen/uitlezen van database, command3/command4 voor vullen/uitlezen van adodb.recordset)

Natuurlijk, indexen zorgen ervoor dat je enkel sneller kunt ZOEKEN in een databank. Wanneer je records toevoegd, moeten de indexen ook aangevuld worden en dat vertraagd de boel natuurlijk. Daarom moet je ook goed afwegen op welke velden je indexen legt. Maar dat is natuurlijk een heel andere discussie...

[ATS]

Ik begrijp de code uberhaupt niet eigenlijk. Wat denk je te bereiken met een query met een WHERE statement x > 1500 AND x > 1900
Uiteraard gaat het vullen van de database langzamer als je indexen gebruikt, maar het zoeken gaat sneller.

[Verwijderd]

Die query was gewoon een test.
Maar zoals dus uit bovenstaande voorbeeld (zie coding) blijkt dat in die situatie het met een index juist langzamer is dan zonder index.
Dus dit is tegengesteld dat men zou verwachten........
Of heeft de index alleen zin als ik op 1 veld zou zoeken en niet zoek op meerdere verlden tegelijk?

[ATS]

Dat is een heel goede gedachte... Ik denk dat dat aan de database-engine ligt of dat werkt of niet. Het zou zomaar kunnen dat hij gewoon niet met meer dan één index tegelijk overweg kan. Ik weet het niet. Je zou eens de documentatie van de BD engine erop moeten naslaan. Als hij dat niet kan, dan kan je idd net zo goed zelf de lijst doorlopen.

[ Voor 3% gewijzigd door ATS op 26-02-2004 19:24 ]

[Verwijderd]

Yep maar zit er over te denken omdat toch mee met een tree te doen in het geheugen, niet met een quadtree maar met een soort twee-tree??? dus de vakken steeds op te delen in twee blokken en zo te zoeken. Aan de kleinste vierkanten de pointers anar de objecten te zetten. Ik denk dat dit vele malen sneller is dan dat met een recordset. De tijd neemt namelijk daarbij erg veel toe zodra er veel records bijkomen. En dan is zo'n tree sneller lijkt me.

[MSalters]

Niet om het een of ander, maar als je in een tekenroutine naar een DB moet heb je volgens mij een design probleem. Volgens mij zou je dat soort dingen in RAM moeten hebben.

[Verwijderd]

Daarom wil het juist ook via een tree gaan doen in het geheugen.
Echter heb ik vandaag nog wat andere leuke dingen gevonden om vector graphics te tonen.

[.oisyn]

Verwijderd schreef op 26 februari 2004 @ 20:00:
Yep maar zit er over te denken omdat toch mee met een tree te doen in het geheugen, niet met een quadtree maar met een soort twee-tree??? dus de vakken steeds op te delen in twee blokken en zo te zoeken. Aan de kleinste vierkanten de pointers anar de objecten te zetten. Ik denk dat dit vele malen sneller is dan dat met een recordset. De tijd neemt namelijk daarbij erg veel toe zodra er veel records bijkomen. En dan is zo'n tree sneller lijkt me.

Ja dat een tree sneller is was sowieso al duidelijk. Wat je daar zegt is trouwens een kd-tree of bsp-tree (een bsp-tree deelt de deelruimte steeds op aan de hand van een willekeurige lijn, bij een kd-tree gebruik je alleen as-parallelle lijnen en vaak doe je dat dan om en om), alleen als je dat snapt, waarom snap je een quadtree dan niet

[Verwijderd]

quadtree snap ik inmiddels ook maar om te zoeken lijkt een quadtree me ingewikkelder, is denk ik meer bedoeld voor een 3d omgeving. Bij een kd tree het simpel de ene kant op of de andere kant en bij een quadtree dus 4 mogelijkheden steeds.

[Ericston]

Nee, een quadtree is bedoeld voor een 2D omgeving. Bij 3D omgevingen hebben we het over octrees, 8 childs. Eén splitsing voor elke as. Het aantal childs is dus telkens 2ⁿ.

[.oisyn]

Verwijderd schreef op 27 februari 2004 @ 15:21:
quadtree snap ik inmiddels ook maar om te zoeken lijkt een quadtree me ingewikkelder, is denk ik meer bedoeld voor een 3d omgeving. Bij een kd tree het simpel de ene kant op of de andere kant en bij een quadtree dus 4 mogelijkheden steeds.

Ik maakte hierboven overigens een vergissing, een kd-tree heeft O(sqrt (n) + k) zoektijd.
Maar bedenk dat je bij een kd tree wel beide kanten moet doorzoeken als je zoekrechthoek de snijlijn snijdt. Hetzelfde verhaal bij een quadtree, alleen hier heb je 4 kinderen. Verder is er niet echt een probleem, je moet ze ook recursief doorzoeken, dat is het makkelijkst

Een quadtree wordt overigens vaak gebruikt voor het weergeven van 3d landschappen. Een landschap is ook eigenlijk niet 3d, er zijn niet echt verschillende hoogtes, vandaar dat dat prima werkt in een quadtree

[Verwijderd]

.oisyn schreef op 27 februari 2004 @ 23:50:
[...]


Ik maakte hierboven overigens een vergissing, een kd-tree heeft O(sqrt (n) + k) zoektijd.
Maar bedenk dat je bij een kd tree wel beide kanten moet doorzoeken als je zoekrechthoek de snijlijn snijdt. Hetzelfde verhaal bij een quadtree, alleen hier heb je 4 kinderen. Verder is er niet echt een probleem, je moet ze ook recursief doorzoeken, dat is het makkelijkst

Een quadtree wordt overigens vaak gebruikt voor het weergeven van 3d landschappen. Een landschap is ook eigenlijk niet 3d, er zijn niet echt verschillende hoogtes, vandaar dat dat prima werkt in een quadtree

En wat is de O / n en de k????
Gebruik van een kd-tree met 2 childs lijkt me makkelijker, gewoon de ene kant of andere kant op. Dacht eigenlijk gebruik te maken trouwens van adobe SVG viewer (plugin voor internet explorer) maar dat ding gaat flippen bij erg grote tekeningen, zoomen werkt niet meer het scrollen (pannen) helemaal naar links dan ontbreken er stukken van de plaat etcc.....had toch wel wat beters verwacht van adobe. grrrrrrrrrr

Maar zijn er geen voorbeelden om erg grote grafieken te tekenen in een 2d engine? Ik bedoel er moeten toch goede plugins voor zijn o.i.d. Ik wil eigenlijk toegevoegde waarde prorgammeren en niet weer het wiel voor de 2e keer uit gaan vinden.

[.oisyn]

De orde notatie is een assymptotisch gemiddelde snelheid van het algoritme. Als iets O(n) is wil dat zeggen dat het lineair schaalt, dus bij 10x zoveel elementen zou je kunnen zeggen dat het 10x zoveel tijd kost. De k wordt vaak gebruikt om het aantal resultaten weer te geven. Als je een algoritme hebt dat O(1+k) is, dan is het zoeken altijd een constante tijd, ongeacht het aantal elementen (vandaar de 1), maar is het wel afhankelijk van het aantal elementen dat gevonden is (de k).

O(sqrt(n) + k) wil dus zeggen dat bij 10x zoveel elementen het zoeken wortel 10 langer wordt, en bij 2x zoveel matches voor een gelijk aantal elementen zal het zoeken 2x zo lang duren


En nee, bij een kd-tree hoef je niet alleen maar de ene kant op, of alleen maar de andere kant. Als je zoek-rechthoek de splitslijn snijdt moet je dus beide kanten doorzoeken, aangezien je resultaten aan beide kanten van de lijn liggen

En je kunt imho pas toegevoegde waarde programmeren als je van jezelf weet dat je het wiel uit kunt vinden, en daar is tot nog toe nog niet echt veel van gebleken (imho zijn datastructuren erg belangrijk om degelijke programma's te schrijven, je kunt ze je dus maar beter eigen maken)