[Algoritme] "sorteren" van rechthoeken

[Verwijderd]

Ok, de titel zegt het al, ik wil dus een grote verzameling rechthoeken "sorteren".

Ik heb een hele grote verzameling van rechthoeken (ongeveer 40.000). Die hebben dus allemaal een coordinaat in het (x,y) vlak voor de linker boven- en rechter onderhoek. Die verzameling wil ik opdelen in kleinere verzamelingen van rechthoeken die bij elkaar liggen. Om dat te bewerkstellen heb ik een algoritme bedacht, waarvan ik redelijk overtuigd ben dat het goed zal werken, maar ik wil het jullie toch ook even voorleggen, misschien kunnen jullie mij voorzien van nuttige kritiek of mij attenderen op een betere methode.

Wat ik nu doe gaat als volgt:

Ik bepaal voor ieder rechthoek het middelpunt. Dan hou ik per rechthoek dus 1 (x,y)-coordinaat over. Dan bereken ik voor dat punt met pythagoras sqrt(x^2 + y^2) de afstand tot de oorsprong (0,0). En vervolgens sorteer ik de rechthoeken oplopend op afstand tot de oorsprong.

Dit lijkt me de makkelijkste methode en ik kan zo gauw geen andere verzinnen. Wat denken jullie?

(o ja, ik bepaal niet eerst voor iedere rechthoek het middelpunt, dit wordt gewoon 'on the fly' tijdens het sorteren gedaan om twee rechthoeken te vergelijken)

/edit
mijn coordinatenstelsel beperkt zich tot de positieve x- en de positieve y-as, anders zou dit natuurlijk al helemaal niet werken)

[ Voor 7% gewijzigd door Verwijderd op 03-04-2003 04:00 ]

[TaXaN]

Tja, het zal afhangen van wat je juist wilt doen met je gesorteerde verzameling; het ene sorteercriterium is het andere niet. Met jouw algoritme zitten de similar rechthoeken in een soort waaiervorm ten opzichte van de oorsprong uitgespreid. Als dat is wat je kunt gebruiken, dan lijkt het me geen slecht algoritme. Zoniet, moet je een andere methode proberen; bijvoorbeeld één van de verschillende clustering-algoritmen uit de machine learning (k-nearest-neighbour en dat soort dingen).

[Verwijderd]

TaXaN schreef op 03 april 2003 @ 04:33:
Tja, het zal afhangen van wat je juist wilt doen met je gesorteerde verzameling; het ene sorteercriterium is het andere niet. Met jouw algoritme zitten de similar rechthoeken in een soort waaiervorm ten opzichte van de oorsprong uitgespreid. Als dat is wat je kunt gebruiken, dan lijkt het me geen slecht algoritme. Zoniet, moet je een andere methode proberen; bijvoorbeeld één van de verschillende clustering-algoritmen uit de machine learning (k-nearest-neighbour en dat soort dingen).

Hey, door die opmerking van waaiervorm heb je me aan het denken gezet en volgens mij kan ik het beter anders op gaan lossen

Tnx voor de termen trouwens, had al zoekpogingen gedaan met Google, maar wist niet precies waarop ik nou moest gaan zoeken.

/me gaat google weer eens proberen

[Verwijderd]

Ok, ik heb eens een beetje door verschillende clustering algoritmen gebladerd, maar heb niet echt gevonden wat ik zoek. De clustering algoritmen die ik heb gevonden gaan ervan uit dat je in een dataset van punten/vlakken naar clusters opzoekt. Die zoeken dus naar punten/vlakken die dichtbij elkaar liggen.

Mijn situatie ligt iets anders. Ik heb een dataset met rechthoeken en weet precies hoeveel dat er zijn. Die wil ik opdelen in een aantal clusters. De clustergrootte (aantal rechthoeken) staat ook vast. Kort gezegd, mijn verzameling rechthoeken moet opgedeeld worden in een aantal clusters van dezelfde grootte. Dit is mogelijk, want de rechthoeken liggen allemaal gepositioneerd in een vaststaand patroon, namelijk een race-circuit.

De verzameling rechthoeken die ik heb 'beschrijven' de baan van een auto die een race-circuit aflegt over een x aantal rondes. Nu wil ik de rechthoeken die min of meer hetzelfde stuk circuit beschrijven dus bij elkaar hebben (los van het tijdsaspect). Dit zijn dus rechthoeken die elkaar vaak ook voor een groot deel zullen overlappen. Deze rechthoeken wil ik dus in clusters (bounding rectangles) opdelen.

De algoritmen die ik heb bekeken zijn daarvoor niet echt geschikt volgens mij. Iemand die misschien een dergelijk algoritme ooit eens voorbij heeft zien komen? Of misschien betere steekwoorden om op te zoeken dan alleen clustering? Want met de zoekopdrachten die ik tot nu toe heb gedaan zit ik vooralsnog niet echt in de goede richting.

[Verwijderd]

wat je suggereerd neigt gewoon naar het quicksort algoritme, heb je daar al naar gekeken?

[80000]

Misschien dat je eens moet zoeken naar quad trees, K tree and R trees. Indexen voor multidimensionale vlakken.
Trouwens, als ik het zo hoor, zou ik Oracle vanaf 8i + Oracle Spatial nemen. Oracle Spatial heeft al een R tree geimplementeerd, waarmee je gewoon queries kan uitvoeren op
je 40000 vlakken (en dus Order by)

[SWfreak]

Denk niet dat er veel mensen naar zo'n soort clusteringsprobleem hebben gekeken.
Wat je zou kunnen doen in dit probleem is een aantal belangrijke punten (punten in het vlak dus) vastleggen. Deze punten kun je met de hand invoeren, maar je kunt misschien ook een algoritme verzinnen dat het circuit een beetje volgt. Als je deze punten hebt, kun je door middel van een twee-dimensionale segment tree precies die rechthoeken opvragen die zo'n punt bevatten.
Een andere mogelijkheid is dat je een speciaal soort segment tree bouwt, gewoon een willekeurige rechthoek neemt en vanuit die rechthoek gaat clusteren totdat een soort van error-criterium voor het maximale aantal rechthoeken in een cluster overschreden wordt. Dit error-criterium kun je ook baseren op de afstand van de originele rechthoek. Als je speciale aannames mag maken over de ligging van de rechthoeken denk ik dat dit wel aardig zou kunnen werken...

[Soultaker]

Wat wil je precies doen? Ben je niet al tevreden als je per rechthoek de 10 dichtstbijzijnde andere rechthoeken vindt (vergeleken op middelpunt) of anders misschien alle rechthoeken die binnen een straal van 10 eenheden liggen?

Aangezien de middelpunten in een 2D vlak liggen, is het in het algemeen onmogelijk om ze te ordenen (op 1 dimensie te projecteren) zo, dat de punten die in de 1D ruimte dicht bij elkaar liggen, ook in de 2D ruimte dicht bij elkaar liggen, en vice versa (de eerste eigenschap alleen is, denk ik, beter haalbaar). Je zult dus een betere oplossing moeten verzinnen, want wat je omschrijft gaat met een simpele lineaire ordening niet lukken.

[Apollo_Futurae]

als je bereid er wat tijd in te steken, kun je dit prima oplossen met een genetisch algoritme, bij voorbeeld extreme optimisation. de eigenschap waar je op laat selecteren is dan de gemiddelde totale afstand van de rechthoeken in een cluster tot het middelpunt van hun cluster.

[.oisyn]

Een van de spatial partitioning algoritmen lijken me idd het beste. Welke ligt een beetje aan de onderverdeling van de rechthoeken. Als ze een beetje gelijkmatig verdeeld zijn is een quadtree goed te gebruiken. Bij een quadtree verdeel je de hele ruimte recursief in 4'en, tot een bepaalde diepte wordt bereikt. Je kunt hiervoor een vaste diepte gebruiken, maar da's over het algemeen niet zo handig. Beter kun je steeds onderverdelen tot het aantal rechthoeken binnen een subquadrant onder een bepaalde waarde komt (let wel op infinite loops als er een aantal rechthoeken zijn die elkaar op een bepaald punt overlappen, want dan kun je onderverdelen wat je wilt, in een bepaalde quadrant blijven er altijd dezelfde rechthoeken). Evt. kun je nog een adaptive quadtree gebruiken, waarbij je niet steeds precies in vieren deelt, maar de scheidslijnen schuift aan de hand van de rechthoeken die zich in dat kwadrant bevinden.

Een K-tree is vergelijkbaar met een adaptive quadtree, maar dan verdeel je de ruimte steeds in tweeën, en kun je bij elke stap bepalen of je de ruimte horizontaal of verticaal verdeeld, aan de hand van wat het best uit komt.

Maar waar wil je het eigenlijk voor gebruiken?

[ Voor 14% gewijzigd door .oisyn op 03-04-2003 14:47 ]

[frankvdtillaart]

Reply op een klein stukje wat ik hierboven lees.
Iets over het gaat over een racebaan, en de baan die de auto's afleggen. Het principe van x^2 en y^2 alleen werkt dan never nooit niet ... Euhm, ik ga ervan uit dat de baan rond is...

(1,10) en (10,1) komen dan bij elkaar in dezelfde cluster, terwijl deze toch een behoorlijk eind uit elkaar liggen ...
Maar misschien dat er al een oplossing voor aangedragen was, vele termen uit de replies ken ik toch niet (Spatial Partitioning Algotitmes )

[Soultaker]

RedSoniq schreef op 03 april 2003 @ 14:49:
Reply op een klein stukje wat ik hierboven lees.
Iets over het gaat over een racebaan, en de baan die de auto's afleggen. Het principe van x^2 en y^2 alleen werkt dan never nooit niet ... Euhm, ik ga ervan uit dat de baan rond is...

(1,10) en (10,1) komen dan bij elkaar in dezelfde cluster, terwijl deze toch een behoorlijk eind uit elkaar liggen ...
Maar misschien dat er al een oplossing voor aangedragen was, vele termen uit de replies ken ik toch niet (Spatial Partitioning Algotitmes )

Wat een kenmerkende combinatie van taalgebruik en het gebruik van MSN smilies toch weer.

[Verwijderd]

maar als je dan een heel grote rechthoek hebt dan ligt-ie toch dichter bij nog andere rechthoeke dan bijkleine rechthoeken dichtbij zijn middelpunt...

[Soultaker]

Verwijderd schreef op 03 April 2003 @ 17:59:
maar als je dan een heel grote rechthoek hebt dan ligt-ie toch dichter bij nog andere rechthoeke dan bijkleine rechthoeken dichtbij zijn middelpunt...

Dat is afhankelijk van hoe je de afstand tussen twee rechthoeken definieert. Als je de minimale afstand tussen twee zijden van de rechthoeken neemt, zou je inderdaad een probleem kunnen hebben. Dat hangt er ook maar net van af wat je precies wilt doen (of je een benadering goed genoeg vind of niet), hoe ver de vierkanten uit elkaar liggen en hoeveel ze verschillen in grootte.

[Verwijderd]

80000 schreef op 03 April 2003 @ 09:36:
Misschien dat je eens moet zoeken naar quad trees, K tree and R trees. Indexen voor multidimensionale vlakken.
Trouwens, als ik het zo hoor, zou ik Oracle vanaf 8i + Oracle Spatial nemen. Oracle Spatial heeft al een R tree geimplementeerd, waarmee je gewoon queries kan uitvoeren op
je 40000 vlakken (en dus Order by)

Ik ben op dit moment dus een R-Tree indexer aan het bouwen voor een database systeem. Kan niet zomaar dit systeem weggooien en Oracle gaan gebruiken. Dit systeem is speciaal geschreven voor het opslaan van moving objects die een unpredictable repetitive movement uitvoeren

[Verwijderd]

RedSoniq schreef op 03 april 2003 @ 14:49:
Reply op een klein stukje wat ik hierboven lees.
Iets over het gaat over een racebaan, en de baan die de auto's afleggen. Het principe van x^2 en y^2 alleen werkt dan never nooit niet ... Euhm, ik ga ervan uit dat de baan rond is...

(1,10) en (10,1) komen dan bij elkaar in dezelfde cluster, terwijl deze toch een behoorlijk eind uit elkaar liggen ...
Maar misschien dat er al een oplossing voor aangedragen was, vele termen uit de replies ken ik toch niet (Spatial Partitioning Algotitmes )

I know, daar ben ik dus ook achter gekomen. Had er niet helemaal goed over nagedacht

(en ik was niet eens dronken, kun je nagaan )

[Verwijderd]

Ik heb trouwens al een methode uitgedacht om de clustering uit te voeren. Ik weet hoeveel rechthoeken er zijn en ik heb alle punten die de track beschrijven. Nu ga ik dus gewoon voor ieder punt dat de track beschrijft de dichtstbijzijnde rechthoeken en de rechthoeken die dat punt bevatten clusteren. Dat doe ik dan voor ieder punt. Zo weet ik zeker dat ik alle rechthoeken in een cluster ga stoppen en voor mijn applicatie zal deze methode het gewenste effect hebben volgens mij

Bedankt voor alle reacties

/edit 1
Die smilie kennen ze hier niet (^O^)

/edit 2
O ja, het zal wel niet echt supersnel zijn, maar het gaat er alleen maar om dat er een index opgebouwd wordt en dat daar een aantal tests mee uitgevoerd gaan worden, er is al een veel betere en efficientere index, maar dat is alleen theoretisch aangetoond. Nu nog even praktisch aantonen dat mijn index gewoonweg bout is voor dit systeem

[ Voor 31% gewijzigd door Verwijderd op 04-04-2003 01:37 ]

[Soultaker]

Verwijderd schreef op 04 april 2003 @ 01:34:
/edit 1
Die smilie kennen ze hier niet (^O^)

Deze bedoel je?